Parallel data processing architecture

• US 7,769,803 B2
• Filed: 01/02/2008
• Issued: 08/03/2010
• Est. Priority Date: 09/28/1999
• Status: Active Grant

• Current Assignee: University of Tennessee Research Foundation (University of Teesside)
• Original Assignee: University of Tennessee Research Foundation (University of Teesside)
• Inventors: Birdwell, John D., Horn, Roger D., Icove, David J., Wang, Tse-Wei, Yadav, Puneet
• Primary Examiner(s): Pham, Khanh B
• Assistant Examiner(s): Ahluwalia, Navneet K
• Application Number:
  US11/968,364
• Publication Number:
  US 20080109461A1
• Time in Patent Office: 944 Days
• Field of Search: 709/201, 709/202, 707/713
• US Class Current: 709/201
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 40/30 Unsupervised data analysis
• CPC Class Codes: G16B 50/00 ICT programming tools or database systems specially adapted for bioinformatics
• CPC Class Codes: G16B 50/20 Heterogeneous data integration
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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 to 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.

Claims

1. A parallel data processing architecture for search, storage and retrieval of data of a database responsive to client queries for specific data of said database, said parallel data processing architecture comprising:

a plurality of host processors including a root host processor, said root host processor being responsive to said client queries for specific data of said database;

each of said host and root host processors maintaining a list of available host processors and information about the capacity and load for each available host processor in memory, each host processor maintaining a search queue of said client queries and broadcasting its capacity and search queue length load information to other host processors and each host processor bringing its search queue into balance according to a time constant with another host processor responsive to receipt of said broadcast capacity and search queue length load information, said balancing including exchanging unprocessed client queries with a recipient host processor responsive to a stochastic selection process; and

a communication system coupling said host and root host processors, wherein at least two host processors communicate capacity and load information to other host processors;

selected host processors storing a database index for said database comprising nodes of a database tree for said database and data accessible via said nodes of said database tree, the root host processor being responsive to a client query for said specific data of said database and using an initial search queue of at least said client query for said specific data of said database;

wherein said database comprises DNA profiles, said client query for said specific data of said database being generated in response to one of target, match stringency, mismatch, equivalence, number of alleles and measurement error specifications, said bringing its search queue into balance according to a time constant with another host processor minimizing the time required for performing a client query for DNA profiles satisfying a set of selected database search criteria.

2. The parallel data processing architecture of claim 1, the root host processor creating a search client object for handling each client query.

3. The parallel data processing architecture of claim 1, wherein said client query requests storage or retrieval of information to be performed and wherein work of said storage or retrieval is distributed among a cooperating group of host processors.

4. A parallel data processing architecture for search, storage and retrieval of data of a database responsive to client search queries for specific data of said database, said parallel data processing architecture comprising:

a plurality of host processors including a root host processor, said root host processor being responsive to said client search queries for said specific data of said database, each host processor maintaining a search queue of said client search queries and broadcasting its capacity and search queue length load information to other host processors and each host processor bringing its search queue into balance according to a time constant with another host processor responsive to receipt of said broadcast capacity and search queue length load information, said balancing including exchanging unprocessed client search queries with a recipient host processor responsive to a stochastic selection process;

each of said host and root host processors maintaining a list of available host processors and information about the capacity and load for each available host processor in memory; and

a communication system coupling said host and root host processors, wherein at least two host processors communicate capacity and load information to other host processors;

selected host processors storing a database index for said database comprising nodes of a database tree for said database and data accessible via said nodes of said database tree, the root host processor being responsive to a client search query for said specific data of said database and selecting a host processor to receive client search query information;

wherein said database comprises DNA profiles, said client search query for said specific data of said database being generated in response to one of target, match stringency, mismatch, equivalence, number of alleles and measurement error specifications, said bringing its search queue into balance according to a time constant with another host processor minimizing the time required for performing a client search query for DNA profiles satisfying a set of selected database search criteria.

5. The parallel data processing architecture of claim 4, wherein said client search query requests performance of one of storage or retrieval of information and wherein work of said storage or retrieval is distributed among a cooperating group of host processors.

6. A parallel data processing architecture for search, storage and retrieval of data of a database responsive to client search queries for specific data of said database, said client search queries being received from a plurality of distributed clients, said parallel data processing architecture comprising:

a plurality of host processors including a root host processor, said root host processor being responsive to said client search queries for said specific data of said database, said root host processor creating a search client object for handling each client search query;

each of said host and root host processors maintaining a list of available host processors and information about the capacity and load for each available host processor in memory; and

a communication system coupling said host and root host processors, wherein at least two host processors communicate capacity and load information to other host processors;

selected host processors storing a database index for said database comprising nodes of a database tree for said database and data accessible via said nodes of said database tree, the root host processor being responsive to a client search query for said specific data of said database, selecting a host processor to receive client search query information and using an initial search queue of at least said client search query for said specific data of said database, each host processor maintaining a search queue of said client search queries and broadcasting its capacity and search queue length load information to other host processors and each host processor bringing its search queue into balance according to a time constant with another host processor responsive to receipt of said broadcast capacity and search queue length load information, said balancing including exchanging unprocessed search requests with a recipient host processor responsive to a stochastic selection process, and wherein said client search query for said specific data of said database requests performance of one of storage or retrieval of information and wherein work of said storage or retrieval is distributed among a cooperating group of host processors;

wherein said database comprises DNA profiles, said client search query for said specific data of said database being generated in response to one of target, match stringency, mismatch, equivalence, number of alleles and measurement error specifications, said bringing its search queue into balance according to a time constant with another host processor minimizing the time required for performing a client search query for DNA profiles satisfying a set of selected database search criteria.