Sequential searching of a database index using constraints on word-location pairs

Abstract

Abstract A computer implemented method performs constrained searching of an index of a database. The information of the database is stored as a plurality of records. A unique location is assigned to each indexable portion of information of the database. Index entries are written to a memory where each index entry includes a word entry representing a unique indexable portion of information, and one or more location entries for each occurrence of the unique indexable portion information. The index entries are sorted according to a collating order of the word entries, and sequentially according to the location entries of each index entry. A query is parsed to generate a first term and a second term related by an AND logical operator, the AND operator requires that a first index entry corresponding to the first term and a second index entry corresponding to the second term both have locations in the same record to satisfy a query. The location entries of the first and second index entries are searched subject to one or more constraints which must be satisfied. The constraints are expressed as C(a)≦C(b)+K, where C(a) means a current location of the first index entry, C(b) means a current location of the second index entry, and K is a predetermined constant.

Inventors

• 👤 Michael Burrows

Bibliographic Details