Object-oriented interface for an index

• US 5,809,502 A
• Filed: 08/09/1996
• Issued: 09/15/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/695,904
• Time in Patent Office: 767 Days
• Field of Search: 395/613, 395/610, 395/603, 395/615, 395/607, 395/614, 707/7, 707/103, 707/3, 707/10, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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/99937 Sorting
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A computer implemented method searches an index to locate records of a database using an object oriented interface. Each record has a unique address in the database. The index is organized as a plurality of index entries where each index entry including a word and an ordered list of locations where the word occurs in the database. The words represent a unique piece of information of the database. The index entries are ordered first according to the collating order of the words, and second according to the collating order of the locations of each associated word. A query is parsed into terms and operators. Each term is associated with a corresponding index entry, the operators relate the terms. A basic stream reader object is generated for each term of the query. The basic stream reader object sequentially reads the locations of the corresponding index entry to determine a target location. A compound stream reader object is generated for each operator. The compound stream reader object references the basic stream reader objects associated with the terms related by the operator. The compound stream reader object produces locations of words within a single record according to the operator. Each basic and compound stream reader object is an encapsulation of data references and method references with operate on the data references.

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 record address in the database, comprising:

organizing the index as a plurality of index entries, each index entry including a word and an ordered list of locations where the word occurs in the database, the word representing a unique piece of information of the database;

ordering the index entries first according to the collating order of the words, and second according to the collating order of the locations of each word;

parsing a query into terms and operators, each term associated with a corresponding index entry, the operators relating the terms;

generating a basic stream reader object for each term, the basic stream reader object to sequentially read the locations of the corresponding index entry to determine a target location;

generating a compound stream reader object for each operator, the compound stream reader object referencing the plurality of basic stream reader objects associated with the terms related by the operator, the compound stream reader object to produce locations of words within a single record according to the operator.

2. The method of claim 1 wherein each basic and compound stream reader object includes data references and method references.

3. The method of claim 2 wherein the data references of a basic stream reader object include a pointer to a file storing the index entry including the word associated with the term, a reference to the word of the index entry, a current location, a previous location, and an estimated over-shoot, and wherein the method references include a get word, get location, get next location, get location linit, get previous location, and close methods.

4. The method of claim 2 wherein the data references of a compound stream reader object includes pointers to the a plurality of related basic stream reader objects, a current word of a current basic stream reader object being read, a current location of the current word, a previous location of the current word, and an estimated over-shoot, and wherein the method references include a get word, get location, get next location, get location limit, get previous location, and close methods.

5. The method of claim 3 further comprising:

producing a current word when the get word method of a particular stream reader object is called.

6. The method of claim 3 further comprising:

producing a current location when the get location method of a particular stream reader object is called.

7. The method of claim 3 further comprising:

producing a next location when the get next location method of a particular stream reader object is called.

8. The method of claim 3 further comprising:

producing a next location which is at least a target location but not greater than a limit location when the get location limit method of a particular stream reader object is called.

9. The method of claim 3 further comprising:

producing a previous location when the get previo us method of a particular stream reader object is called.

10. The method of claim 3 further comprising:

closing the stre am reader object when the close method of a particular stream reader object is called.