Method of partitioning data records

Details Method of partitioning data records Method of partitioning data records

2007-09-18

2007-09-18

Wong, Don (Department: 2163)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000

Reexamination Certificate

active

10767730

ABSTRACT:
A tree-structured index to multidimensional data is created using 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 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 to parallel computer architectures, allowing scale up to very large databases.

REFERENCES:
patent: 5161204 (1992-11-01), Hutcheson et al.
patent: 5273632 (1993-12-01), Stockham et al.
patent: 5325466 (1994-06-01), Kornacker
patent: 5374527 (1994-12-01), Grossman
patent: 5442562 (1995-08-01), Hopkins et al.
patent: 5470710 (1995-11-01), Weiss et al.
patent: 5541067 (1996-07-01), Perlin
patent: 5559940 (1996-09-01), Hutson
patent: 5580728 (1996-12-01), Perlin
patent: 5734893 (1998-03-01), Li et al.
patent: 5759369 (1998-06-01), Menchen et al.
patent: 5761685 (1998-06-01), Hutson
patent: 5876933 (1999-03-01), Perlin
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5926812 (1999-07-01), Hilsenrath et al.
patent: 6026397 (2000-02-01), Sheppard
patent: 6054268 (2000-04-01), Perlin
patent: 6100901 (2000-08-01), Mohda et al.
patent: 6122628 (2000-09-01), Castelli et al.
patent: 6128587 (2000-10-01), Sjolander
patent: 6134541 (2000-10-01), Castelli et al.
patent: 6336106 (2002-01-01), Evans
patent: 6490582 (2002-12-01), Fayyad et al.
patent: 6584456 (2003-06-01), Dom et al.
patent: 6633882 (2003-10-01), Fayyad et al.
patent: 6750011 (2004-06-01), Perlin
patent: 6807490 (2004-10-01), Perlin
patent: 6959300 (2005-10-01), Caldwell et al.
patent: 2002/0152035 (2002-10-01), Perlin
Amir Ben-Dor and Zohar Yakhini (1999), Clustering Gene Expression Patterns, pp. 33-42.
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, Dec. 1998.
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://cesdisl.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.
Atsuo Yoshitaka, et al., “A Survey on Content-Bsed Retrieval for Multimedia Databases”, IEEE Transactions On Knowledge And Data Engineering, vol. 11, No. 1, Jan./Feb. 1999, pp. 81-93.
Peter N. Yianilos, “Excluded Middle Point Forests for Nearest Neighbor Search”, Jul. 20, 1998 (revised Sep. 11, 1998), pp. 1-12.
Peter N. Yianilos, “Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces”, 1993, 11 pages.
Marvin Shapiro, “The Choice of Reference Points in Best-Match File Searching”, Communications of the ACM, vol. 20, No. 5, May 1977, pp. 339-343.
Davood Rafiei et al., “Similarity-Based Queries for Time Series Data”, Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data, May 1997, pp. 1-13.
King-Ip Lin et al., “The TV-tree—an index structure for high-dimensional data”, 1994, pp. 1-30.
Paolo Ciaccia, et al., “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces”, Proceedings of the 23rdVLDB Conference, Athens, Greece, 1997, 10 Pages.
W. A. Burkhard et al., “Some Approaches to Best-Match File Searching”, Communications of the ACM, vol. 16, No. 4, Apr. 1973, pp. 230-236.
Sergey Brin, “Near Neighbor Search in Large Metric Spaces”, Proceedings of the 21stVLDB Conference, Zurich, Switzerland, 1995, 11 Pages.
Tolga Bozkaya et al., “Distance-Based Indexing For High-Dimensional Metric Spaces”, 1997, 12 pages.
Andrew Berman et al., “Selecting Good Keys for Triangle-Inequality-Based Pruning Algorithms”, IEEE, 1997, pp. 12-19.
Norbert Beckmann et al., “The R—tree: An Efficient and Robust Access Method for Points and Rectangles”, ACM, 1990, pp. 322-331.
Richardo Baeza-Yates et al., Proximity Matching Using Fixed-Queries Trees, 1994, 13 Pages.
Franz Aurenhammer, Voronoi Diagrams—Survey of a Fundamental Geometric Data Structure, ACM Computing Surveys, vol. 23, No. 3, Sep. 1991, pp. 345-405.
Schwartz et al., “Flourescent Multiplex linkage analysis and carrier detection for Duchenne/Becker Muscular Dystrophy”, Am. J. Human Genetics 51:721-729, 1992.
McConkey, E.H., Human Genetics, The Molecular Revolution Jones and Bartlett Publishers, 1993, pp. 92-112.
Clayton et al., “Analysis and Interpretation of Mixed Forensic Stains Using DNA STR Profiling”, Forensic Science International, vol. 91 pp. 55-70 (1998).
Gill et al. , Interpreting Simple STR Mixtures using Allela Peak Areas, 1998, Forensic Science International, vol. 91 pp. 41-53.
Evett et al., Taking Account of Peak Areas when Interpreting Mixed DNA Profiles, 1998, Journal of Forensic Sciences, vol. 43., No. 1, pp. 62-69.
Perlin et al., Toward Fully Automated Genotyping: Genotyping Microsatellite Markers by Deconvolution, 1995, AMerican Journal of Human Genet., vol. 57, pp. 1199-1210.

Affiliated with

Also associated with

Rating

Method of partitioning data records does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method of partitioning data records, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of partitioning data records will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3739744