Technique for indexing information stored as a plurality of records

• US 5,966,703 A
• Filed: 04/03/1998
• Issued: 10/12/1999
• Est. Priority Date: 08/09/1996
• Status: Expired due to Term

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Burrows, Michael
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/054,438
• Time in Patent Office: 557 Days
• Field of Search: 707/2, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

In a computer implemented method, a plurality of records are stored in a database at unique record addresses. The information of each record is parsed into a set of individual words where each word represents a portion of the information of a particular record. A unique sequential location is assigned to each word so that the location of a first word of a next record sequentially follows the location of a last word of a previous record. Pairs are formed from the words and their assigned location. For attributes common to a particular record, generate a record metaword, and assign the location of the last word of the record to the metaword. For attributes common to subsets of words, generate a first and second field metaword, and assign the location of the first and last word of the subset to the first and second field metaword to form pairs. The pairs are sorted in a memory, first according to the words and metawords, and second according to their locations so that each unique word and metaword is immediately followed by a sequential list of locations where the unique word and metaword occurs in the database.

Claims

1. A method for indexing information stored as a plurality of records, each of the plurality of records including a set of words, each word included in the set of words having an associated location representation, the method comprising the steps of:

identifying an attribute common to at least one subset of the set of words included in a first of the plurality of records, the at least one subset having a first word and a last word;

generating a metaword representing the identified attribute; and

associating the location representation associated with the last word of the at least one subset with the generated metaword.

2. The method of claim 1, wherein the generated metaword is a first generated metaword, further comprising the steps of:

generating a second metaword representing the identified attribute; and

associating the location representation associated with the first word of the at least one subset with the second generated metaword.

3. The method of claim 1, wherein the generated metaword is a first generated metaword, the identified attribute is a first identified attribute, and the at least one subset is a first subset, further comprising the steps of:

identifying a second attribute common to a second subset of the set of words included in a second of the plurality of records, the second subset having a first word and a last word;

generating a second metaword representing the second identified attribute; and

associating the location representation associated with the last word of the second subset with the second generated metaword.

4. The method of claim 3, wherein associating the location representation associated with the last word of the first subset with the first generated metaword creates a first pair and associating the location representation associated with the last word of the second subset with the second generated metaword creates a second pair, further comprising the step of:

sorting the pairs according to the first generated metaword and the second generated metaword.

5. The method of claim 1, wherein the generated metaword represents at least one of a record address, a description of record information, a record size, a date associated with the record, a record fingerprint, a record end, a record deletion indicator, and a record title.

6. The method of claim 1, wherein each word in the set of words is associated with a unique location.

7. An article of manufacture for indexing information stored as a plurality of records, each of the plurality of records including a set of words, each word included in the set of words having an associated location representation, the article of manufacture comprising:

at least one processor readable carrier; and

instructions contained on the carrier;

wherein the instructions are configured to be readable from the at least one carrier by one or more processors and thereby cause the one or more processors to operate so as to;

identify an attribute common to at least one subset of the set of words included in a first of the plurality of records, the at least one subset having a first word and a last word;

generate a metaword representing the identified attribute; and

associate the location representation associated with the last word of the at least one subset with the generated metaword.

8. The article of manufacture of claim 7, wherein the generated metaword is a first generated metaword, and wherein the instructions are configured to cause the one or more processors to further operate so as to:

generate a second metaword representing the identified attribute; and

associate the location representation associated with the first word of the at least one subset with the second generated metaword.

9. The article of manufacture of claim 8, wherein the instructions are configured to cause the one or more processors to further operate so as to:

create a first pair by associating the location representation of the last word of the first subset with the first generated metaword;

create a second pair by associating the location representation of the last word of the second subset with the second generated metaword; and

sort the pairs according to the first generated metaword and the second generated metaword.

10. The article of manufacture of claim 7, wherein the generated metaword is a first generated metaword, the identified attribute is a first identified attribute, and the at least one subset is a first subset, and wherein the instructions are configured to cause the one or more processors to further operate so as to:

identify a second attribute common to a second subset of the set of words included in a second of the plurality of records, the second subset having a first word and a last word;

generate a second metaword representing the second identified attribute; and

associate the location representation associated with the last word of the second subset with the second generated metaword.

11. The article of manufacture of claim 7, wherein the generated metaword represents at least one of a record address, a description of record information, a record size, a date associated with the record, a record fingerprint, a record end, a record deletion indicator, and a record title.

12. The article of manufacture of claim 7, wherein each word in the set of words is associated with a unique location.

13. A system for indexing information stored as a plurality of records, each of the plurality of records including a set of words, each word included in the set of words having an associated location representation, the system comprising:

a processor configured to;

identify an attribute common to at least one subset of the set of words included in a first of the plurality of records, the at least one subset having a first word and a last word;

generate a metaword representing the identified attribute; and

associate the location representation associated with the last word of the at least one subset with the generated metaword; and

a memory configured to store the generated metaword.

14. The system of claim 13, wherein the generated metaword is a first generated metaword, the processor further configured to:

generate a second metaword representing the identified attribute; and

associate the location representation associated with the first word of the at least one subset with the second generated metaword.

15. The system of claim 13, wherein the generated metaword is a first generated metaword, the identified attribute is a first identified attribute, and the at least one subset is a first subset, the processor further configured to:

identify a second attribute common to a second subset of the set of words included in a second of the plurality of records, the second subset having a first word and a last word;

generate a second metaword representing the second identified attribute; and

associate the location representation associated with the last word of the second subset with the second generated metaword.

16. The system of claim 15, wherein associating the location representation associated with the last word of the first subset with the first generated metaword creates a first pair and associating the location representation associated with the last word of the second subset with the second generated metaword creates a second pair, the processor further configured to:

sort the pairs according to the first generated metaword and the second generated metaword.

17. The system of claim 13, wherein the generated metaword represents at least one of a record address, a description of record information, a record size, a date associated with the record, a record fingerprint, a record end, a record deletion indicator, and a record title.

18. The system of claim 13, wherein each word in the set of words is associated with a unique location.