Parallel data processing architecture

Details Parallel data processing architecture Parallel data processing architecture

2004-01-30

2008-11-18

Alam, Hosain T (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C707S793000

Reexamination Certificate

active

07454411

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: 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: 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: 6134541 (2000-10-01), Castelli et al.
patent: 6154765 (2000-11-01), Hart
patent: 6389451 (2002-05-01), Hart
patent: 6490582 (2002-12-01), Fayyad et al.
patent: 6581104 (2003-06-01), Bereiter
patent: 6598054 (2003-07-01), Schuetze 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: 2002/0152035 (2002-10-01), Perlin
patent: 2003/0058277 (2003-03-01), Bowman-Amuah
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 User's 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, C., 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.
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, 19

Affiliated with

Also associated with

Rating

Parallel data processing architecture 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 architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel data processing architecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4033479