Method for optimizing entries for searching an index

• US 6,047,286 A
• Filed: 08/21/1998
• Issued: 04/04/2000
• 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:
  US09/138,088
• Time in Patent Office: 592 Days
• Field of Search: 707/4, 707/3, 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/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A system for indexing information includes a memory and processor. The memory stores an index to information. The processor receives a first signal representing a query for a phrase corresponding to a concatenation of adjacent portions of the information. The processor processes the first signal so as to generate a second signal representing an entry for the phrase to be stored as part of the index in the memory.

Claims

1. A method for indexing information, comprising the steps of:

processing a query having a phrase corresponding to concatenation of adjacent portions of the information;

generating an index entry for the phrase;

processing the query to identify one or more locations at which the phrase occurs within the information; and

measuring an amount of time required to process the query to identify the one or more locations;

wherein the index entry for the phrase is generated if the measured time exceeds a threshold.

2. A method according to claim 1, wherein generating the index entry includes encoding the concatenation of adjacent portions of the information.

3. A method according to claim 1, wherein the index entry includes a metaword.

4. A method according to claim 3, wherein the metaword is identical to the concatenation of adjacent portions of the information.

5. A method according to claim 1, wherein the index entry includes a first entry representing the phrase and one or more second entries each representing a respective location of the phrase within the information.

6. A method according to claim 5, wherein the first entry is immediately followed by the one or more second entries in the index entry.

7. A method according to claim 5, wherein generating the index entry includes:

encoding the concatenation of adjacent portions of the information to form the first entry; and

encoding each respective location of the phrase within the information to form the one or more second entries.

8. A method according to claim 7, wherein encoding each respective location of the phrase within the information to form the one or more second entries includes:

encoding a first portion of each respective location of the phrase within the information to form each of the one or more second entries.

9. A method according to claim 8, wherein the phrase includes at least one of a punctuation mark and a numeral.

10. A method according to claim 1, wherein the query having the phrase is a first query having the phrase, and further comprising the steps of:

receiving a second query having the phrase after generation of the index entry; and

parsing the second query based upon the index entry.

11. A system for indexing information, comprising:

a memory configured to store an index to the information; and

a processor configured to receive a first signal representing a query and having a phrase corresponding to a concatenation of adjacent portions of the information, and to process the first signal so as to generate a second signal representing an index entry for the phrase to be stored as part of the index within the memory;

wherein the processor is further configured to process the first signal to identify one or more locations at which the phrase occurs within the information, to measure an amount of time required to process the first signal to identify the one or more locations, and to generate the second signal if the measured time exceeds the threshold.

12. A system according to claim 11, wherein the is further configured to generate the index entry by the concatenation of adjacent portions of the information.

13. A system according to claim 11, wherein processor is further configured to generate a metaword as part of the index entry.

14. A system according to claim 13, wherein the processor is further configured to generate the metaword to be identical to the concatenation of adjacent portions of the information.

15. A system according to claim 11, wherein the processor is further configured to generate the index entry so as to include a first entry representing the phrase and one or more second entries each representing a respective location of the phrase within the information.

16. A system according to claim 15, wherein the processor is further configured to generate the index entry such that the first entry is immediately followed by the one or more second entries.

17. A system according to claim 15, wherein the processor is further configured to generate the index entry by encoding the concatenation of adjacent portions of the information to form the first entry and encoding each of the respective locations of the phrase within the information to form each the one or more second entries.

18. A system according to claim 17, wherein the processor is further configured to generate the index entry by encoding a first portion of each respective location of the phrase within the information to form each of the one or more second entries.

19. A system according to claim 11, wherein the phrase includes at least one of a punctuation mark and a numeral.

20. A system according to claim 11, wherein the processor is further configured to receive, after generation of the second signal, a third signal representing a second query for the phrase and to parse the third signal based upon the index entry.

21. A system according to claim 11, further comprising:

a plurality of server stations configured to store the information;

a plurality of client stations configured to generate queries; and

a communications network configured to interconnect the processor, the client stations and the server stations;

wherein the first signal is received by the processor from one of the client stations via the network, and the processor is further configured to process the first signal using the index to identify one or more locations at which the phrase occurs within the information stored at the plurality of server stations and to generate a third signal for the one client station representing the identified one or more locations.

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

a memory configured to store an index to information;

a processor configured to receive a query having a phrase corresponding to a concatenation of adjacent portions of the information, and to process the query to generate a single object oriented index interface corresponding to the phrase;

wherein an entry within the index corresponding to the phrase is identifiable based upon the single object oriented index interface, and one or more locations of the phrase within the information are identifiable based upon the identified index entry.

23. A method for indexing information, comprising the steps of:

processing a query having a phrase corresponding to concatenation of adjacent portions of the information;

generating an index entry for the phrase;

processing the query to identify one or more locations at which the phrase occurs within the information; and

measuring a cost required to process the query to identify the one or more locations;

wherein the index entry for the phrase is generated if the measure cost exceeds a threshold.