US4870568A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for searching a database system including parallel processors
Assignee: Thinking Machines Corp
•
Filing: 1986-06-25
•
Granted: 1989-09-26
•
Expires: 2006-06-25
Abstract
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.
Inventors
- 👤 Brewster Kahle
- 👤 Craig W. Stanfill
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 03:22
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/901; G06F16/9014; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24532; G06F16/30; G06F16/33; G06F16/332; G06F16/3325; G06F16/3326; G06F16/903; G06F16/90335; G06F16/90339; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
197 words
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.
Claim 2
Dependent Claim
197 words
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.
Claim 3
Dependent Claim
54 words
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.
Claim 4
Dependent Claim
83 words
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.
Claim 5
Dependent Claim
111 words
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.
Claim 6
Dependent Claim
74 words
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.
Claim 7
Dependent Claim
110 words
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.
Claim 8
Dependent Claim
104 words
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.
Claim 9
Dependent Claim
89 words
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).
Claim 10
Dependent Claim
17 words
The method of claim 1 wherein different point values are assigned to at least some different words.
Claim 11
Dependent Claim
173 words
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.
Claim 12
Dependent Claim
173 words
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.
Claim 13
Dependent Claim
89 words
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.
Claim 14
Dependent Claim
92 words
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).
Claim 15
Dependent Claim
106 words
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.
Claim 16
Dependent Claim
17 words
The method of claim 10 wherein different point values are assigned to at least some different words.
Claim 17
Dependent Claim
137 words
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.
Claim 18
Dependent Claim
137 words
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.
References Cited (Backward Citations)
US4152762A
Cited
US4118788A
Cited
US4255796A
Cited
US4358824A
Cited
US4543630A
Cited
US4468728A
Cited
US4464650A
Cited
US4495566A
Cited
US4451901A
Cited
US4554631A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-09-25 | 1993-03-27 | 1993-09-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-09-25 | 1997-03-27 | 1997-09-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-09-25 | 2001-03-27 | 2001-09-26 | $7700.00 | Window Closed / Lapsed |