Method for searching an index

• US 5,966,710 A
• Filed: 09/09/1998
• Issued: 10/12/1999
• 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:
  US09/150,349
• Time in Patent Office: 398 Days
• Field of Search: 707/103, 707/3, 707/104, 707/10
• 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 system for locating stored information using an index includes a memory and processor. The memory stores an index which includes a plurality of index entries. Each of the index entries corresponds to a respective one of a plurality of terms associated with the stored information and has one or more location identifiers. Each of the location identifiers represents a location within the information at which the corresponding term is associated with the information. The processor searches the stored index to identify the location identifiers of at least two index entries which correspond to terms of interest. The processor also determines the locations within the information which are represented by the identified location identifiers and at which the terms of interest have a relationship as indicated by a particular operator (e.g. "and").

Claims

1. A system for locating stored information using an index, comprising:

a memory configured to store an index including a plurality of index entries, each of the plurality of index entries representing either a unique portion of the stored information or an attribute related to a unique portion of the stored information and having one or more location identifiers, each of the one or more location identifiers representing a unique location within the stored information where a corresponding unique portion or attribute occurs within the stored information; and

a processor configured to search the stored index to identify the one or more location identifiers of particular ones of the plurality of index entries which correspond to particular ones of a plurality of search terms, and to determine a location within the stored information, based upon the identified one or more location identifiers, where the corresponding particular ones of the plurality of search terms have a relationship as indicated by a particular search operator.

6. A system according to claim 1, wherein:

the stored information is in the form of a plurality of records each including unique portions of the stored information; and

the determined location is the location of one of the plurality of records within the stored information.

7. A system according to claim 6, wherein:

each of the plurality of records has a unique address within the stored information; and

the determined location is represented by the unique address of the record having the determined location.

8. A system according to claim 7, wherein:

the processor is further configured to direct a presentation of the record having the determined location using the unique address of the record having the determined location.

9. A system according to claim 8, wherein:

the determined location is one of a plurality of determined locations within the stored information, each based upon the identified one or more location identifiers, where the corresponding particular ones of the plurality of search terms have the relationship as indicated by the particular search operator; and

the processor is further configured to direct a presentation of the records having the plurality of determined locations in a predetermined order using the unique addresses of the records having the plurality of determined locations.

11. A system according to claim 1, wherein the location entries of each index entry are organized in a sequential order.

2. A system according to claim 2, wherein the processor is further configured to search the stored index in response to a query.

3. A system according to claim 2, wherein:

the processor is further configured to parse the query into query terms and into query operators relating the query terms, each of the parsed query terms being associated with one of the plurality of index entries; and

the parsed query terms include the particular search terms and the parsed query operators include the particular search operator.

4. A system according to claim 3, wherein the processor is further configured to open a basic reader object for each of the particular search terms, the basic reader object to read location entries of the index entries corresponding to the particular search terms, and to open a compound reader object for the particular search operator, the compound reader object to read location entries of the index entries corresponding to the particular search terms related by the particular search operator.

5. A system according to claim 4, wherein:

basic reader object is a first index stream reader object;

the compound reader object is a second index stream reader object; and

each of the first index stream reader object and the second index stream reader object includes data references and method references.

10. A system according to claim 2, wherein the index entries are organized in an alphanumeric collating order.

12. A method for locating stored information using an index having a plurality of index entries, each of the plurality of index entries representing either a unique portion of the stored information or an attribute related to a unique portion of the stored information and having one or more location identifiers, each of the one or more location identifiers representing a unique location within the stored information where a corresponding unique portion or attribute occurs within the stored information, the method comprising the steps of:

identifying the one or more location identifiers of particular ones of the plurality of index entries which correspond to particular ones of a plurality of search terms; and

determining a location within the stored information, based upon the identified one or more location identifiers, where the corresponding particular ones of the plurality of search terms have a relationship as indicated by a particular search operator.

13. A method according to claim 12, further comprising the step of:

receiving a query including the particular search terms and the particular search operator.

14. A method according to claim 13, further comprising the step of:

parsing the query into query terms and into query operators relating the query terms, each of the parsed query terms being associated with one of the plurality of index entries;

wherein the parsed query terms include the particular search terms and the parsed query operators include the particular search operator.

15. A method according to claim 14, further comprising the steps of:

opening a basic reader object for each of the particular search terms, the basic reader object to read location entries of the index entries corresponding to the particular search terms; and

opening a compound reader object for the particular search operator, the compound reader object to read location entries of the index entries corresponding to the particular search terms related by the particular search operator.

16. A method according to claim 15, wherein:

the basic reader object is a first index stream reader object;

the compound reader object is a second index stream reader object; and

each of the first index stream reader object and the second index stream reader object includes data references and method references.

17. A method according to claim 12, wherein:

the information is stored as a plurality of records each including unique portions of the stored information; and

the determined location is the location of one of the plurality of records within the stored information.

18. A method according to claim 17, wherein:

each of the plurality of records has a unique address within the stored information; and

the determined location is represented by the unique address of the record having the determined location.

19. A method according to claim 18, further comprising the step of:

presenting the record having the determined location using the unique address of the record having the determined location.

20. A method according to claim 19, wherein:

the determined location is one of a plurality of determined locations within the stored information, each based upon the identified one or more location identifiers, where the corresponding particular ones of the plurality of search terms have the relationship as indicated by the particular search operator; and

the step of presenting includes presenting the records having the plurality of determined locations in a predetermined order using the unique addresses of the records having the plurality of determined locations.