Data processing: database and file management or data structures – Database and file access – Record – file – and data search and comparisons
Reexamination Certificate
2008-08-27
2011-11-15
Saeed, Usmaan (Department: 2166)
Data processing: database and file management or data structures
Database and file access
Record, file, and data search and comparisons
Reexamination Certificate
active
08060522
ABSTRACT:
A tree-structured index to multidimensional data is created using naturally occurring patterns and clusters within the data which permit efficient search and retrieval strategies in a database of DNA profiles. A search engine utilizes hierarchical decomposition of the database by identifying clusters of similar DNA profiles and maps to parallel computer architecture, allowing scale up past previously feasible limits. Key benefits of the new method are logarithmic scale up and parallelization. These benefits are achieved by identification and utilization of naturally occurring patterns and clusters within stored data. The patterns and clusters enable the stored data to be partitioned into subsets of roughly equal size. The method can be applied recursively, resulting in a database tree that is balanced, meaning that all paths or branches through the tree have roughly the same length. The method achieves high performance by exploiting the natural structure of the data in a manner that maintains balanced trees. Implementation of the method maps naturally to parallel computer architectures, allowing scale up to very large databases.
REFERENCES:
patent: 5325466 (1994-06-01), Kornacker
patent: 5325525 (1994-06-01), Shan et al.
patent: 5442562 (1995-08-01), Hopkins et al.
patent: 5559940 (1996-09-01), Hutson
patent: 5761685 (1998-06-01), Hutson
patent: 5813005 (1998-09-01), Tsuchida et al.
patent: 5857180 (1999-01-01), Hallmark et al.
patent: 5864871 (1999-01-01), Kitain et al.
patent: 5881311 (1999-03-01), Woods
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5892945 (1999-04-01), Mirchandaney et al.
patent: 5926812 (1999-07-01), Hilsenrath et al.
patent: 5966704 (1999-10-01), Furegati et al.
patent: 6026397 (2000-02-01), Sheppard
patent: 6100901 (2000-08-01), Mohda et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6490582 (2002-12-01), Fayyad et al.
patent: 6578068 (2003-06-01), Bowman-Amuah
patent: 6598054 (2003-07-01), Schuetze et al.
patent: 6728959 (2004-04-01), Merkey
patent: 2005/0046584 (2005-03-01), Breed
Juha Karhunen et al., “Locally Linear Independent component analysis”, International Joint Conference on Neural Networks, 1999, vol. 2, pp. 882-887.
Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, MIT Press (Cambridge, MA) / McGraw-Hill (New York). 1990.
Guttman, A., R trees: a dynamic index structure for spatial searching, ACM, 1984, 47-57.
Sellis, T., et. al., The R-tree: a dynamic index for multi-dimensional objects, Tech. Rept. UMI-ACS TR 87 3, CS TR 1975, University of Maryland, Feb. 1987, 1-24.
Message Passing Interface Forum, MPI: A Message-Passing Interface Standard, version 1.1, Jun. 1995. Also at http://www-unix.mcs.anl.gov/mpi/and http://www.mpi-forum.org/docs/mpi-11-html/mpi-report.html.
Universal Data Option for Informix Dynamic Server, version 9.14 for Windows NT and UNIX. Also at http://www.informix.com/informix/techbriefs/udo/udo.pdf.
Geist, A., A. Begnelin, J. Dongarra, W. Jiang, R. Manchek, V. Sunderam, PVM: Parallel Virtual Machine: A Users' Guide and Tutorial for Networked Parallel Computing. MIT Press. 1994.
Beowulf Project at CESDIR, http://cesdis1.gsfc.nasa.gov/linux/beowulf/, Center of Excellence in Space Data and Information Sciences, NASA Goddard Space Flight Center. 1998.
Strang, G., Linear Algebra and its Applications, 2nd ed., Academic Press, New York, 1980.
Budowle, Bruce and Tamyra R. Moretti, “Genotype profiles for six population groups at the 13 CODIS short tandem repeat core loci and other PCR based loci,” Forensic Science Communications, FBI Laboratory Division Publication 99-06, U. S. Department of Justice, Federal Bureau of Investigation. Jul. 1999, V. 1, n. 2.
CODIS 5.1 GDIS Searching Specification (Draft), U.S. Department of Justice Federal Bureau of Investigation. Jul. 23, 1998.
Quinlan, J.R., Induction of decision trees, Machine Learning 1:81-106, 1986.
Berry, Michael W., Zlatko Drmac, and Elizabeth R. Jessup, “Matrices, vector spaces, and information retrieval,” SIAM Review 41:335-362, 1999.
Message Passing Interface Forum, MPI-2: Extensions to the Message-Passing Interface, Jul. 18, 1997. Also at http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html.
Thomas E. Anderson et al., “A Case for NOW (Networks of Workstations)”, IEEE, 1995, pp. 54-64.
Brian Tierney et al., “NetLogger: A Toolkit for Distributed System Performance Tuning and Debugging”, Dec. 10, 2002, pp. 1-8.
Rajkumar Buyya et al., “GARDMON: A Java-based Monitoring Tool for Gardens Non-dedicated Cluster Computing System”, 1999, p. 1-7.
Henri Casanova et al., “NetSolve: A Network Server for Solving Computational Science Problems”, Apr. 26, 1996, p. 1-14.
Luiz De Rose et al., “An Approach to Immersive Performance Visualization of Parallel and Wide-Area Distributed Applications”, 1999, 8 Pages.
The Falcon Monitoring and Steering System, printed from http://www.cc.gatech.edu/systems/projects/FALCON/ printed on Jan. 29, 2004, 3 Pages.
Ian Foster, et al., “Globus: A Metacomputing Infrastructure Toolkit”, 1997, pp. 1-16.
Daniel E. Reed et al., “Delphi: An Integrated, Language-Directed Performance Prediction, Measurement and Analysis Environment”, 1999, 4 pages.
Andrew S. Grimshaw et al., “Legion: The Next Logical Step Toward a Nationwide Virtual Computer”, Technical Report No. CS-94-21, Jun. 1994, pp. 1-23.
Weiming Gu et al., “Falcon: On-line Monitoring and Steering of Large-Scale Parallel Programs”, Technical Report No. GIT-CC-94-21, 1994, pp. 1-38.
Chung-Hsing Hsu et al., “IPERF: A Framework for Automatic Construction of Performance Prediction Models”, 1998, pp. 1-10.
Big Brother System and Network Monitor—About Us, printed from http://bb4.com/aboutus.html on Jan. 29, 2004, 2 Pages.
Big Brother System and Network Monitor—Welcome, printed from http://bb4.com/index.html on Jan. 29, 2004, 2 Pages.
Memory Utilization Tracking Tool (MUTT), printed from http://ext.lanl.gov/orgs/cic/cic8/para-dist-team/mutt/muttdoc.html on Jan. 29, 2004, 6 Pages.
NOVA: Networked Object-Based EnVironment for Analysis, printed from http://www.usatlas.bnl.gov/˜wenaus
ova on Jan. 29, 2004, 7 Pages.
Zhengyu Liang et al., “ClusterProbe: An Open, Flexible and Scalable Cluster Monitoring Tool”, 1999, pp. 1-10.
Barton P. Miller et al., “The Paradyn Parallel Performance Measurement Tools”, pp. 1-23.
G. A. Geist et al., “A User's Guide to PICL a Portable Instrumented Communication Library”, Oak Ridge National Laboratory, Mathematical Sciences Section, Oct. 1990, 22 Pages.
A. Espinosa et al., “Automatic Performance Analysis of Parallel Programs”, Computer Science Department, 7 Pages.
B. Tierney et al., “The NetLogger Methodology for High Performance Distributed Systems Performance Analysis”, IEEE, Jul. 1998, pp. 1-8.
Rich Wolski et al., “Implementing a Performance Forecasting System for Metacomputing: The Network Weather Service”, UCSD Technical Report TR-CS97-50, May 20, 1997, pp. 1-10.
Rich Wolski, “Dynamically Forecasting Network Performance Using the Network Weather Service”, UCSD Technical Report TR-CS96-494, Jan. 7, 1998, pp. 1-35.
Altschul et al., Gapped BLAST and PSI-BLAST: a new generation of protein database search programs, [online], (Jul. 16, 1997), Oxford University Press, Nucleic Acids Research, 1997, vol. 25, No. 17, pp. 3389-3402.
Bartlett et al., Fault Tolerance in Tandem Computer Systems, [online], (Dec. 1991), IEEE, Tandem TR 86.2, pp. 1-21.
Hong et al., Optimization of Parallel Query Execution Plans in XPRS, [online] (Dec. 1991), IEEE, pp. 218-225.
David Taniar et al., A High Performance Object-Oriented Distributed Parallel Database Architecture, [online] (Apr. 21, 1998, Springer, pp. 498-507.
Birdwell John D.
Horn Roger D.
Icove David J.
Wang Tse-Wei
Yadav Puneet
Ahluwalia Navneet K
Cameron LLP
Saeed Usmaan
University of Tennessee Research Foundation
LandOfFree
Parallel data processing system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel data processing system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel data processing system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4255683