Data processing: database and file management or data structures – Database and file access – Preparing data for information retrieval
Reexamination Certificate
2011-02-01
2011-02-01
Wong, Don (Department: 2163)
Data processing: database and file management or data structures
Database and file access
Preparing data for information retrieval
C707S737000, C707S748000
Reexamination Certificate
active
07882106
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: 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: 5694593 (1997-12-01), Baclawski
patent: 5734893 (1998-03-01), Li et al.
patent: 5759369 (1998-06-01), Menchen et al.
patent: 5761685 (1998-06-01), Hutson
patent: 5813005 (1998-09-01), Tsuchida et al.
patent: 5864871 (1999-01-01), Kitain et al.
patent: 5876933 (1999-03-01), Perlin
patent: 5881311 (1999-03-01), Woods
patent: 5884320 (1999-03-01), Agrawal et al.
patent: 5926812 (1999-07-01), Hilsenrath et al.
patent: 6009435 (1999-12-01), Taubin et al.
patent: 6026397 (2000-02-01), Sheppard
patent: 6054268 (2000-04-01), Perlin
patent: 6100901 (2000-08-01), Mohda et al.
patent: 6121969 (2000-09-01), Jain 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: 6154765 (2000-11-01), Hart
patent: 6336106 (2002-01-01), Evans
patent: 6389451 (2002-05-01), Hart
patent: 6490582 (2002-12-01), Fayyad et al.
patent: 6578068 (2003-06-01), Bowman-Amuah
patent: 6581104 (2003-06-01), Bereiter
patent: 6584456 (2003-06-01), Dom et al.
patent: 6598054 (2003-07-01), Schuetze et al.
patent: 6633882 (2003-10-01), Fayyad et al.
patent: 6728959 (2004-04-01), Merkey
patent: 6750011 (2004-06-01), Perlin
patent: 6769033 (2004-07-01), Bass et al.
patent: 6807490 (2004-10-01), Perlin
patent: 6959300 (2005-10-01), Caldwell et al.
patent: 2002/0152035 (2002-10-01), Perlin
patent: 2003/0058277 (2003-03-01), Bowman-Amuah
patent: 2005/0046584 (2005-03-01), Breed
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, pp. 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, pp. 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.
Quinlan, J.R., Induction of decision trees, Machine Learning 1:81-106, 1986.
Berry, Michae 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 http://www.mpi-forum.org/docs/mpi-20-html/mpi2-report.html.
Schwartz et al., “Fluorescent 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 Forensics Stains Using DNA STR Profiling,” Forensic Science International, vol. 91, pp. 55-70 (1998).
Gill et al., Interpreting Simple STR Mixtures using Allele 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.
(1) Atsuo Yoshitaka, et al., “A Survey on Copntent-Based Retrieval for Multimedia Databases,” IEEE Transactions On Knowledge And Data Engineering, vol. 11, No. 1, Jan./Feb. 1999, pp. 81-93.
(2) Peter N. Yianilos, “Excluded Middle Vintage Point Forest for Nearest Neighbor Search,” Jul. 20, 1998 (revised Sep. 11, 1998), pp. 1-12.
(3) Peter N. Yianilos, “Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces,” 1993, 11 pages.
(4) Marvin Shapiro, “The Choice of Reference Points in Best-Match File Searching,” Communication of the ACM, vol. 20, No. 5, May 1977, pp. 339-343.
(5) 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.
(6) King-Ip Lin et al., “The TV-tree-an index structure for high-dimensional data,” 1994, pp. 1-30.
(7) Paolo Ciaccia et al., “M-tree: An Efficient Access Method for Similarity Search in Metric Spaces,” Proceedings of the 23rd VLDB Conference, Athens, Greece, 1997, 10 Pages.
(8) 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.
(9) Sergey Brin, “Near Neighbor Search in Large Metric Spaces,” Proceedings of the 21st VLDB Conference, Zurich, Switzerland, 1997, 11 Pages.
(10) Tolga Bozkaya et al., “Distance-Based Indexing For High-Dimensional Metric Spaces,” 1997, 12 Pages.
(11) Andrew Berman et al., “Selecting Good Keys for Triangle-Inequality-Based Pruning Algorithms,” IEEE, 1997, pp. 12-19.
(12) Norbert Beckmann et al., “The R*-tree: An Efficient and Robust Access Method for Points and Rectangles,” ACM, 1990, pp. 322-331.
(13) Richardo Baeza-Yates et al., “Proximity Matching Using Fixed-Queries Trees,” 1994, 13 Pages.
(14) Franz Aurenhammer, “Voronoi Diagrams—Survey of a Fundamental Geometric Dat
Birdwell John D.
Horn Roger D.
Icove David J.
Wang Tse-Wei
Yadav Puneet
Nguyen Merilyn P
PCT Law Group, PLLC
University of Tennessee Research Foundation
Wong Don
LandOfFree
Method of indexed storage and retrieval of multidimensional... 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 indexed storage and retrieval of multidimensional..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of indexed storage and retrieval of multidimensional... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2632909