Method for indexing information of a database

• US 5,745,899 A
• Filed: 08/09/1996
• Issued: 04/28/1998
• 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:
  US08/689,541
• Time in Patent Office: 627 Days
• Field of Search: 395/613, 395/610, 395/603, 395/615, 395/602, 707/102, 707/10, 707/3, 707/104, 707/2
• 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/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

An indexing method is provided for a database storing information as records at unique addresses. Pairs are generated for each record, each pair includes a word representing a portion of the information of the record and an associated location. The locations are assigned sequentially as the information is parsed into words. Pairs are also generated for attributes common to each record. In this case, each pair includes a metaword representing the attribute and the location of the last word of the record. Furthermore, two pairs are generated for one or more immediately adjacent words having a common attribute. Here, each pair includes the metaword representing the attribute. The location associated with the first of two pairs is the location of the first adjacent word, and the location of the second pair is the location the last adjacent word. The pairs are sorted first according to the words and metawords, and second according to the location assigned to the words. Each unique word and metaword is written to the index as word entries in their collated order to fully populate the index. Each word and metaword is immediately followed by all of the locations where the word and metaword occurs in the database.

Claims

1. A computer implemented method for indexing information stored as a plurality of records in a database, each of the plurality of records having a record address in the database, comprising:

generating, for each record, a set of pairs, each pair including a word representing a portion of the information of the record and an associated location of the portion of the information, the locations of the words assigned sequentially such that the location of a first word of a next record sequentially follows the location of a last word of a previous record;

identifying for each set of pairs common record attributes;

generating for each identified common record attribute another pair including a record metaword representing the common record attribute and the location of the last word of the set of pairs, one of the common record attributes being the record address;

identifying subsets of pairs of each record having common field attributes;

generating, for each common field attribute, a first field metaword and a second field metaword representing the common field attributes; and

assigning the location of the first word of the subset of pairs to the first field metaword, and assigning the location of the last word of the subset of pairs to the second field metaword;

sequentially writing index entries to an index stored in a memory, there being one index entry for each unique word and for each unique metaword, the index entries written in a collation order of the words and metawords, each index entry including a particular unique word or a particular unique metaword written in a prefix notation, the prefix notation of the particular unique word or metaword immediately followed by a word terminator, the terminator immediately followed by all of the locations assigned to the particular unique word or metaword in a collating order of the locations, each location written as a delta value, and the last location of the index entry followed by a location terminator to fully populate the compressed data structure.