Parallel data processing system

• US 8,060,522 B2
• Filed: 08/27/2008
• Issued: 11/15/2011
• Est. Priority Date: 09/28/1999
• Status: Expired due to Term

• Current Assignee: University of Tennessee Research Foundation (University of Teesside)
• Original Assignee: University of Tennessee Research Foundation (University of Teesside)
• Inventors: Birdwell, John D., Wang, Tse-Wei, Horn, Roger D., Yadav, Puneet, Icove, David J.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Ahluwalia, Navneet K
• Application Number:
  US12/199,010
• Publication Number:
  US 20090055361A1
• Time in Patent Office: 1,175 Days
• Field of Search: 718/100, 718/102, 707/764, 707/720
• US Class Current: 707/764
• 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 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 system for search, storage and retrieval of data of a database responsive to a client query for specific data of said database, said parallel data processing system comprising:

a plurality of host processors including a root host processor, each of said plurality of host processors having at least one search engine;

said root host processor being responsive to a connection request by a client for said specific data of said database to instantiate a thread dedicated to servicing the client and to establish an initial search queue of at least one search request, the at least one search request providing information specifying a client submitting a client query and information specifying a node of a database tree at which a search is to begin and a context of the search request, each search request including a counter of mismatches allowed at a node of the database tree;

each said host processor maintaining a list of available processors and information about the processing capacity and search queue length of search requests for each available processor in memory;

each said host processor for storing at least a portion of said database in an associated memory;

each said host processor decrementing said counter when a miss is allowed at the node of the database tree; and

a communication system coupling said processors, wherein at least two host processors communicate said processing capacity and search queue length information to other host processors, one communicating host processor bringing its search queue into balance with a search queue of another host processor according to a time constant in response to receipt of communicated processing capacity and search queue length information, said bringing into balance comprising exchanging a block of search requests from host processors having long average waiting times to host processors having short waiting times and adjusting a size of a block of exchanged requests according to relative processing speeds of host processors and inter-processor communications protocol between the host processors;

at least one host processor transmitting at least one search request to another host processor, a search engine of said transmitting host processor removing said at least one search request from its search queue and a receiving host processor adding said at least one search request to its search queue;

selected processors storing a database index for said database, the root host processor being responsive to a client query and selecting a host processor to receive one of a search request and a block of search requests of adjusted size.

2. The parallel data processing system as recited in claim 1, all host processors storing substantially the same database index.

3. The parallel data processing system as recited in claim 1, said plurality of host processors including a root host processor comprising a plurality of root host processors being less than or equal to a number of said plurality of host processors.

4. The parallel data processing system as recited in claim 1, said database being partitioned into portions according to said database index, different portions being stored on different host processors, said root host processor communicating a search request to a specific host processor according to said partitioned database portion.

5. The parallel data processing system as recited in claim 1, said database being partitioned into portions according to said database index, at least two host processors for accessing the same portion of said database.

6. The parallel data processing system as recited in claim 1, one of said plurality of host processors reconfiguring its search queue of search requests in response to one of an addition and a failure of another host processor.

7. The parallel data processing system as recited in claim 1, said memory including memory shared among host processors for storing said database, a host processor connected to said communications system accessing said shared memory at a rate of at least ten gigabits per second.

8. A parallel data processing system for search, storage and retrieval of data of a database responsive to a client query for specific data of said database, said parallel data processing system comprising:

a plurality of host processors including a root host processor, each of said plurality of host processors having at least one search engine;

said root host processor being responsive to a connection request by a client for said specific data of said database to instantiate a thread dedicated to servicing the client and to establish an initial search queue of at least one search request, the at least one search request providing the identity of a client submitting a client query and information specifying a node of a database tree at which a search is to begin and a context of the search request, each search request including a counter of mismatches allowed at a node of the database tree;

each said host processor maintaining a list of available processors and information about the processing capacity, search queue length of search requests and load for each available processor in memory;

each said host processor for storing at least a portion of said database in an associated memory;

each said host processor decrementing said counter when a miss is allowed at the node of the database tree; and

a communication system coupling said processors, wherein at least two host processors communicate capacity, search queue length and load information to other host processors, one communicating host processor bringing its search queue into balance with a search queue of another host processor according to a time constant in response to receipt of communicated processing capacity and search queue length information, said bringing into balance comprising exchanging a block of search requests from host processors having long average waiting times to host processors having short average waiting times and adjusting a size of a block of exchanged requests according to relative processing speeds of host processors and inter-processor communications protocol between the host processors;

at least one host processor transmitting at least one search request to another host processor, a search engine of said transmitting host processor removing said at least one search request from its search queue and a receiving host processor adding said at least one search request to its search queue;

selected processors storing a database index for said database, each host processor being responsive to a client query and selecting a host processor to receive one of a search request and a block of search requests of adjusted size and reconfiguring said list of available processors and information about the capacity and load in response to one of addition and failure of a host processor.

9. The parallel data processing system as recited in claim 8, all host processors storing substantially the same database index.

10. The parallel data processing system as recited in claim 8, said plurality of host processors including a root host processor comprising a plurality of root host processors being less than or equal to a number of said plurality of host processors.

11. The parallel data processing system as recited in claim 8, said database being partitioned into portions according to said database index, different portions being stored on different host processors, said root host processor communicating a search request to a specific host processor according to said partitioned database portion.

12. The parallel data processing system as recited in claim 8, said database being partitioned into portions according to said database index, at least two host processors accessing the same portion of said database.

13. The parallel data processing system as recited in claim 8, a host processor adjusting data stored in memory representing one of said list of available processors, information about the processing capacity and information about the search queue length of search requests for another host processor responsive to receipt of a communication from said another host processor.

14. A method of communicating at least one search request from a plurality of host processors including a root host processor to at least one host processor of a parallel data processing system for search, storage and retrieval of data of a database responsive to a client query for specific data of said database, each of said plurality of host processors having at least one search engine, said method of communicating the at least one search request in a parallel data processing system comprising:

said root host processor, responsive to a connection request by a client for said specific data of said database, instantiating a thread dedicated to servicing the client and establishing an initial search queue of at least one search request, the at least one search request providing information specifying a client submitting the client query, information specifying a node of a database tree at which a search is to begin and specifying a context of the search request, each search request including a counter of mismatches allowed at a node of the database tree;

each said host processor maintaining a list of available processors and information about the processing capacity and search queue length of search requests for each available processor in memory;

each said host processor for storing at least a portion of said database in an associated memory;

each said host processor decrementing said counter when a miss is allowed at the node of the database tree;

said root host processor, transmitting said at least one search request to at least one host processor via a communications system;

the communication system coupling said processors, wherein at least two host processors communicate said processing capacity and search queue length information to other host processors, one communicating host processor bringing its search queue into balance with a search queue of another host processor according to a time constant in response to receipt of communicated processing capacity and search queue length information, said bringing into balance comprising exchanging a block of search requests from host processors having long average waiting times to host processors having short waiting times and adjusting a size of a block of exchanged requests according to relative processing speeds of host processors and inter-processor communications protocol between the host processors; and

at least one host processor transmitting at least one search request to another host processor, a search engine of said transmitting host processor removing said at least one search request from its search queue and a receiving host processor adding said at least one search request to its search queue;

selected processors storing a database index for said database, the root host processor being responsive to a client query and selecting a host processor to receive one of a search request and a block of search requests of adjusted size and each said host processor decrementing said counter when a miss is allowed at the node of the database tree.

15. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

all host processors storing substantially the same database index.

16. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

said root host processor partitioning said database into portions according to said database index, different portions being stored on different host processors, and

said root host processor communicating a search request to a specific host processor according to said partitioned database portion.

17. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

said root host processor partitioning said database into portions according to said database index, and

at least two different host processors accessing the same portion of said database.

18. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

one of said plurality of host processors reconfiguring its search queue of search requests in response to one of an addition and a failure of another host processor.

19. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

sharing database memory among said host processor and said root host processor and

said root host processor and said host processor accessing said database memory at a rate of at least ten gigabits per second.

20. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

minimizing cost of a resulting partition according to the equation:

Cost=Entropy+Weight×

Adjacency,

where the Weight is a non-negative number defining a relative importance assigned to adjacency.

21. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

partitioning said database into portions via multivariate statistical clustering.

22. The method of communicating a search request from a root host processor to at least one host processor of a parallel data processing system as recited in claim 14, the method further comprising

a host processor adjusting data stored in memory representing one of said list of available processors, information about the processing capacity and information about the search queue length of search requests for another host processor responsive to receipt of a communication from said another host processor.