System for discrete parallel processing of queries and updates

• US 6,983,322 B1
• Filed: 11/21/2000
• Issued: 01/03/2006
• Est. Priority Date: 10/14/1999
• Status: Expired due to Term

• Current Assignee: MEC Management, LLC (Three Affiliated Tribes of the Fort Berthold Reservation, North Dakota)
• Original Assignee: Al Acquisitions Incorporated
• Inventors: Tripp, Gary W., Meadway, Michael D.
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US09/718,526
• Time in Patent Office: 1,869 Days
• Field of Search: 709/102, 709/104, 709/203, 709/217, 709/219, 709/223, 709/313, 709/329, 709/225, 709/226, 707/3, 707/6, 707/8, 707/10, 707/104
• US Class Current: 709/225
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/959 Network
• 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/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

A data driven discrete parallel processing computing system for searches with a key-ordered list of data objects distributed over a plurality of servers. The invention is a data-driven architecture for distributed segmented databases consisting of lists of objects. The database is divided into segments based on content and distributed over a multiplicity of servers. Updates and queries are data driven and determine the segment and server to which they must be directed avoiding broadcasting. This is effective for systems such as search engines. Each object in the list of data objects must have a key on which the objects can be sorted relative to each other. Each segment is self-contained and doesn'"'"'t rely on a schema. Multiple simultaneous queries and simultaneous updates and queries on different segments on different servers result in parallel processing on the database taken as a whole.

Claims

1. A computing system with a key-ordered list of data objects distributed over a plurality of servers which allows discrete parallel processing on said servers, comprising:

(a) a self contained key-ordered list of data objects;

(b) a plurality of memories in a plurality of servers, each memory containing a segment of the self-contained key-ordered list of data objects where each segment consists of a contiguous subset of said objects having keys with a specified range; and

(c) a query processor which receives queries and, based on data content of the query, directs each received query to one of said plurality of servers by comparing the data content of the query to the specified range of keys for each segment,

wherein there are at least two copies of said memories for a segment of said segmented list, and one of the copies for a segment is available for updates, the other copies for the segment are available for queries.

2. The system of claim 1 where at least one segment includes two or more objects having the same key.

3. The system of claim 1 where independent processors serve at least two of the segments such that the segments can be accessed simultaneously.

4. The system of claim 1 where each segment is a proper subset of the key-ordered list.

5. The system of claim 1 where, for each object, the key is expressed in complete form such that look-ups can be performed directly based on data content of each query.

6. The system of claim 1 additionally comprising an update processor which receives updates and, based on data content of the update, directs each received update to one of said plurality of servers by comparing the data content of the update to the specified range of keys for each segment.

7. The system of claim 1 further including means for receiving multiple queries from a single source, directing each query to a different server, combining results of said multiple queries, and directing said results back to the source of the queries.

8. The system of claim 1 where each data object includes a key and one or more data constructs for each of a plurality of said objects.

9. The system of claim 1 where each object is comprised of a type and a value specifically stored as a pair.

10. The system of claim 1 where, for two or more of said objects, each object includes a reference to a location of an associated object on a network.

11. The system of claim 1 where updates and queries can occur simultaneously.

12. The system of claim 1 where at least one copy of each segment is available for query processing at all times.

13. A method of operating a computing system with a key-ordered list of objects distributed over a plurality of servers which allows discrete parallel processing on said servers, comprising:

(a) creating a self contained key-ordered list of data objects;

(b) operating a plurality of servers with a plurality of memories, each memory containing a segment of the self contained key-ordered list of data objects where each segment consists of a contiguous subset of said objects having keys with a specified range; and

(c) operating a query processor which receives queries and, based on data content of the query, directs each received query to one of said plurality of servers by comparing the data content of the query to the specified range of keys for each segment,

wherein there are at least two copies of said memories for a segment of said segmented list, and one of the copies for a segment is available for updates, the other copies for the segment are available for queries.

14. A set of computer data containing a set of computer programs which, resided in a plurality of servers, causes the servers to perform the method of claim 13.

15. The method of claim 13 where at least one segment includes two or more objects having the same key.

16. The set of computer data of claim 14 further including the limitations of claim 15.

17. The method of claim 13 where independent processors serve at least two of the segments such that the segments can be accessed simultaneously.

18. The set of computer data of claim 14 further including the limitations of claim 17.

19. The method of claim 13 where each segment is a proper subset of the key-ordered list.

20. The set of computer data of claim 14 further including the limitations of claim 19.

21. The method of claim 13 where, for each object, the key is expressed in complete form look-ups are performed directly based on data content of each query.

22. The set of computer data of claim 14 further including the limitations of claim 21.

23. The method of claim 13 further comprising of receiving updates and, based on data content of the update, directing each received update to one of said plurality of servers by comparing the data content of the update to the specified range of keys for each segment.

24. The set of computer data of claim 14 further including the limitations of claim 23.

25. The method of claim 13 further comprising receiving multiple queries from a single source, directing each query to a different server, combining results of said multiple queries, and directing said results back to the source of the queries.

26. The set of computer data of claim 14 further including the limitations of claim 25.

27. The method of claim 13 where each data object includes a key and one or more data constructs for each of a plurality of said objects.

28. The set of computer data of claim 14 further including the limitations of claim 27.

29. The method of claim 13 where each object is comprised of a type and a value specifically stored as a pair.

30. The set of computer data of claim 14 further including the limitations of claim 29.

31. The method of claim 13 where for two or more of said objects each object includes a reference to a location of an associated object on a network.

32. The set of computer data of claim 14 further including the limitations of claim 31.

33. The method of claim 13 where updating and querying can occur simultaneously.

34. The method of claim 13 where at least one copy of each segment is available for query processing at all times.