Method for searching a database system including parallel processors

• US 4,870,568 A
• Filed: 06/25/1986
• Issued: 09/26/1989
• Est. Priority Date: 06/25/1986
• Status: Expired due to Term

• Current Assignee: TM Patents LP
• Original Assignee: Thinking Machines Corporation (Oracle Corporation)
• Inventors: Stanfill, Craig W., Kahle, Brewster
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Ruiz, Adolfo
• Application Number:
  US06/878,532
• Time in Patent Office: 1,189 Days
• Field of Search: 364/200 MS File, 364/200, 364/900, 364/300
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method to operate on a single instruction multiple data (SIMD) computer for searching for relevant documents in a database which makes it possible to perform thousands of operations in parallel. The words of each document are stored by surrogate coding in tables in one or more of the processors of the SIMD computer. To determine which documents of the database contain a word that is the subject of a query, a query is broadcast from a central computer to all the processors and the query operations are simultaneously performed on the documents stored in each processor. The results of the query are then returned to the central computer. After all the search words have been broadcast to the processors and point values accumulated as appropriate, the point values associated with each document are reported to the central computer. The documents with the largest point values are then ascertained and their identification is provided to the user.

Claims

1. A process for searching for relevant documents in a database comprising the steps of:

(a) forming a database by storing for each of a plurality of documents at least one table of hash codes representing words in the document, the table(s) that represent the words in each different document being stored in a different digital data processor, each hash code comprising information at a plurality of bit locations;

(b) forming a query having at least one word and a point value of relevance assigned to each word;

(c) testing if the word in the query is in the database by;

(1) determining the bit locations in the table at which the hash code corresponding to the queried word is stored; and

(2) simultaneously testing in each of the processors the bit locations corresponding to the queried word;

(d) adding at each digital data processor the point value associated with the queried word to a total point value for the document if the hash code is found at all the bit locations corresponding to the queried word that are tested in that processor; and

(e) providing identification of those documents in the database with high total point values.

2. The process of claim 1 wherein the step of forming a query comprises:

(a) identifying a group of relevant documents;

(b) determining a frequency at which the words in the documents occur among all the relevant documents; and

(c) generating a query based on the frequency of occurrence of words in the relevant documents.

3. The process of claim 1 wherein the step of adding the point value of a queried word to the total point value of a document comprises:

(a) setting a flag in the processor to indicate the presence of the queried word in the table;

(b) communicating simultaneously from a central computer to each of the processors a command to add the point value assigned to the word to the total point value of the document if the flag in the processor is set.

4. The process according to claim 1 wherein a document is represented by a chain of tables, each of which stores a representation of a portion of the document, each chain of tables comprising a first table and one or more successive tables, the step of adding the point value associated with the queried word to the total point value of the document comprising the steps of:

(a) communicating the total point value of the portion of the document represented by each successive table in the chain to the preceding table in the chain; and

(b) accumulating the total point values of all the tables in the first table of the chain.

5. The process according to claim 1 wherein the storing of document data in the processors comprises the steps of:

(a) initializing to zero a table of bits in a memory of each processor;

(b) generating a plurality of independent hash codes for each word with values in an address range of the table; and

(c) for each hash code, setting a bit at an address in the table corresponding to each hash code value.

6. The process of claim 1 wherein the step of providing the identification of those documents with high total point values comprises identifying the documents in numeric order of total point value, said process comprising:

(a) testing the most significant bit of the point value stored in memory in each processor;

(b) setting a flag in the processor if the most significant bit is zero;

(c) repeating step (a) and (b), if necessary, until a non-zero bit is identified; and

(d) successively testing bits of the point values of lesser significance in those processors where a non-zero bit is identified until a document is identified with the highest total point value.

7. The process of claim 1 wherein the step of providing the identification of those documents with high total point values comprises identifying the documents in numeric order of total point value, said process comprising:

(a) testing the most significant bit of the point values stored in memory in each processor;

(b) setting a flag in the processor if the most significant bit is zero;

(c) testing the next most significant bit of the point values stored in memory at each processor where a flag is not set; and

(d) setting a second flag in the processor if the next most significant bit is zero.

8. The process of claim 1 wherein the step of providing the identification of documents with high total point values comprises:

(a) successively testing at each digital data processor bits of the total point values associated with each document beginning with the most significant bit and continuing to test bits of lesser significance until the highest total point value is identified; and

(b) repeating step (a) of this claim on the total point values remaining after the highest total point value is identified in the previous execution of step (a).

9. The method of claim 1 wherein different point values are assigned to at least some different words.

10. A process for searching in a database comprising the steps of:

(a) forming a database by storing in each of a plurality of digital data processors at least one table of hash codes, the hash codes in each table representing a group of related words;

(b) forming a query having at least one word and a point value of relevance assigned to each word;

(c) testing if the word in the query is in the database by;

(1) determining the bit locations in the table at which the hash code corresponding to the queried word is stored; and

(2) simultaneously testing in each of the processors the bit locations corresponding to the queried word;

(d) at each digital data processor, adding the point value associated with the queried word to a total point value for that group of related words if the hash code is found at all the bit locations tested in the table; and

(e) providing identification of those groups of related words in the database with high total point values.

11. The process of claim 10 wherein the step of adding the point value of a queried word to the total point value for a group of related words comprises:

(a) setting a flag in the processor to indicate the presence of the queried word in the table;

(b) communicating simultaneously from a central computer to each of the processors a command to add the point value of the queried word to the total point value for the group of related words if the flag in the processor is set.

12. The process of claim 10 wherein the step of providing the identification of those groups of related words with high total point values comprises:

(a) successively testing the bits of the total point values associated with each group of related words beginning with the most significant bit and continuing to test bits of lesser significance until the highest total point value is identified; and

(b) repeating step (a) of this claim on the total point values remaining after the highest total point values is identified in the previous execution of step (a).

13. The process of claim 10 wherein the step of providing the identification of those groups of related words with high total point values comprises identifying the groups in numeric order of total point value, said process comprising:

(a) testing the most significant bit of the point values stored in memory in each processor;

(b) setting a flag in the processor if the most significant bit is zero;

(c) testing the next most significant bit of the point values stored in memory at each processor where a flag is not set;

(d) setting a second flag in the processor if the next most significant bit is zero.

14. The method of claim 10 wherein different point values are assigned to at least some different words.

15. A process for searching in a database comprising the steps of:

(a) forming a database by storing in each of a plurality of digital data processors at least one table of hash codes, the hash codes in each table representing a group of related words;

(b) forming a query having at least one word;

(c) testing for the presence of the queried word in the database by;

(1) determining the bit locations in the table at which the hash code corresponding to the queried word is stored; and

(2) simultaneously testing in each of the processors the bit locations corresponding to the queried word; and

(d) scoring each group of related words, a score for a group of related words being increased if the hash code is found at all the bit locations tested in the table.