Method for searching an index

• US 5,832,500 A
• Filed: 08/09/1996
• Issued: 11/03/1998
• Est. Priority Date: 08/09/1996
• Status: Expired due to Term

• Current Assignee: Eureka Database Solutions, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Burrows, Michael
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US08/695,060
• Time in Patent Office: 816 Days
• Field of Search: 395/613, 395/610, 395/603, 395/615, 395/614, 707/103, 707/3, 707/10, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A computer implemented method searching an index of a database composed of records storing information. Each record has a unique address in the database. The database is indexed by storing index entries in a memory. Each index entry includes a word entry representing a unique portion of information of the database and one or more location entries pointing to occurrences of the unique portions in the database. The index entries are organized according to a collating order of the words. The location entries of each word are stored in a sequential order. A query is parsed into terms and operators, the operators relate the terms, and each term is associated with one of the index entries. A basic reader object is opened for each term. The basic reader object reads location entries of the index entry. A compound reader object is opened for each operator, the compound reader object reads locations of the index entries corresponding to the terms related by the operator. The index entries are searched to locate records qualified by the query.

Claims

1. A computer implemented method for searching an index of a database, the database including a plurality of records, each record having a unique address in the database, comprising:

indexing the database by storing index entries in a memory, each index entry including a word entry representing a unique portion of information of the database and one or more location entries pointing to occurrences of the unique portions in the database, the index entries organized according to a collating order of the words, and the location entries of each word stored in a sequential order;

parsing a query into terms and operators, the operators relating the terms, each term associated with one of the index entries;

opening a basic reader object for each term, the basic reader object to read location entries of the index entry;

opening a compound reader object for each operator, the compound reader object to read locations of the index entries corresponding to the terms related by the operator;

searching the index entries to locate records qualified by the query; and

presenting addresses of the located records to users in a predetermined order.