Parallel Data Processing System
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
64 Claims
-
1-41. -41. (canceled)
-
42. :
- 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 said client queries for said specific data of said database to create a search client object for a client query 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 the context of the search request; 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; 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; 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 a search request. - View Dependent Claims (43, 44, 45, 46, 47, 48)
- 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;
-
49. :
- 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; said root host processor being responsive to said client queries for said specific data of said database to create a search client object for a client query 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 the context of the search request; each said host processor maintaining a list of available processors and information about the capacity and load for each available processor in memory; a communication system coupling said processors, wherein at least two host processors communicate capacity and load information to other host processors; selected processors storing a database index for said database, each host processor 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. - View Dependent Claims (50, 51, 52, 53, 54)
- 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;
-
55. :
- A method of communicating a search request from 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, said method of communications a search parallel data processing system comprising;
said root host processor, responsive to a client query for said specific data of said database, creating a search client object for a client query 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 and information specifying the context of the search request; said root host processor, transmitting said at least one search request to at least one host processor via a communications system; 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 storing at least a portion of said database in an associated memory; at least two host processors communicating their processing capacity and search queue length information to another host processor; 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; at least one host processor transmitting at least one search request to another host processor and the receiving host processor transmitting one search request to the transmitting host processor, a search engine of said transmitting host processor removing said at least one search request from its search queue and a search engine of said receiving host processor adding said at least one search request to its search queue; and 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 a search request. - View Dependent Claims (56, 57, 58, 59, 60, 61, 62, 63)
- A method of communicating a search request from 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, said method of communications a search parallel data processing system comprising;
-
64. :
- A method of communicating a request from 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, said method of communications a search parallel data processing system comprising;
said root host processor creating an object for a request and establishing an initial search queue of at least one request to one of store and delete data from said database, the at least one request providing information specifying the context of the store/delete request; said root host processor, transmitting said at least one store/delete request to at least one host processor via a communications system; each said host processor maintaining a list of available processors and information about the processing capacity and search queue length of requests for each available processor in memory; each said host processor storing at least a portion of said database in an associated memory; at least two host processors communicating their processing capacity and search queue length information to another host processor; 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; at least one host processor transmitting at least one request to another host processor and the receiving host processor transmitting one request to the transmitting host processor, a search engine of said transmitting host processor removing said at least one request from its search queue and a search engine of said receiving host processor adding said at least one request to its search queue; and selected processors storing a database index for said database, the root host processor selecting a host processor to receive a store/delete request.
- A method of communicating a request from 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, said method of communications a search parallel data processing system comprising;
Specification