Technique for ranking records of a database

• US 7,406,460 B2
• Filed: 04/20/2004
• Issued: 07/29/2008
• Est. Priority Date: 08/09/1996
• Status: Expired due to Fees

• Current Assignee: Eureka Database Solutions, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Burrows, Michael
• Primary Examiner(s): Chace; Christian P.
• Assistant Examiner(s): RADTKE, MARK A
• Application Number:
  US10/827,354
• Publication Number:
  US 20040243569A1
• Time in Patent Office: 1,561 Days
• Field of Search: 707/4, 707/5, 707/102, 707/7, 707/2, 707/3, 707/6, 707/10, 707/101, 709/217, 711/114
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/328 Management therefor
• 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/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A technique for ranking records of a database is disclosed. In one particular exemplary embodiment, the technique may be realized as a method for ranking records of a database located during a search of an index to the database performed in response to a query, wherein the index has a plurality of index entries, and wherein each index entry has a weight.

Claims

1. A method for ranking records of a database located during a search of an index to the database performed in response to a query, the index having a plurality of index entries, each index entry having a weight, the method comprising the steps of:

scoring each located record according to the number of times portions of information corresponding to query terms occur in each record and the weight of each index entry corresponding to occurring query terms;

storing the score and an identifier of each located record in a respective entry of a ranking list; and

in response to having searched a portion of the index, determining if any records yet to be located may achieve a score that is higher than the score of any of the records already located and stored in the ranking list based upon query terms corresponding to index entries having a low weight, wherein the low weight corresponds to the weight of the index entry having the lowest weight of the portion of the index searched, and if not, searching the index using query terms corresponding to index entries having weights higher than the low weight.

2. The method of claim 1, wherein the ranking list has a limit on the number of entries stored therein.

3. The method of claim 1, wherein each index entry has a word entry corresponding to a unique portion of information of the database, further comprising the step of:

assigning the weight to each index entry according to a difference between the number of records indexed and the number of records including the unique portion of information corresponding to the word entry of the index entry.

4. The method of claim 1, further comprising the step of:

ordering the entries of the ranking list according to the scores.

5. The method of claim 4, further comprising the step of:

providing information associated with each located record to a user in the order of the ranking list.

6. The method of claim 5, wherein the provided information associated with each located record is the score of each located record.

7. The method of claim 5, wherein the provided information associated with each located record is the identifier of each located record.

8. A system for ranking records of a database located during a search of an index to the database performed in response to a query, the index having a plurality of index entries, each index entry having a weight, the system comprising:

at least one processor configured to score each located record according to the number of times portions of information corresponding to query terms occur in each record and the weight of each index entry corresponding to occurring query terms; and

at least one memory configured to store the score and an identifier of each located record in a respective entry of a ranking list;

wherein, in response to having searched a portion of the index, the at least one processor is also configured to determine if any records yet to be located may achieve a score that is higher than the score of any of the records already located and stored in the ranking list based upon query terms corresponding to index entries having a low weight, wherein the low weight corresponds to the weight of the index entry having the lowest weight of the portion of the index searched, and if not, search the index using query terms corresponding to index entries having weights higher than the low weight.

9. The system of claim 8, wherein the ranking list has a limit on the number of entries stored therein.

10. The system of claim 8, wherein each index entry has a word entry corresponding to a unique portion of information of the database, wherein the at least one processor is also configured to assign the weight to each index entry according to a difference between the number of records indexed and the number of records including the unique portion of information corresponding to the word entry of the index entry.

11. The system of claim 8, wherein the at least one processor is also configured to order the entries of the ranking list according to the scores.

12. The system of claim 11, wherein the at least one processor is also configured to provide information associated with each located record to a user in the order of the ranking list.

13. The system of claim 12, wherein the provided information associated with each located record is the score of each located record.

14. The system of claim 12, wherein the provided information associated with each located record is the identifier of each located record.

15. A system for ranking records of a database located during a search of an index to the database performed in response to a query, the index having a plurality of index entries, each index entry having a weight, the system comprising:

means for scoring each located record according to the number of times portions of information corresponding to query terms occur in each record and the weight of each index entry corresponding to occurring query terms;

means for storing the score and an identifier of each located record in a respective entry of a ranking list; and

means for determining, in response to having searched a portion of the index, if any records yet to be located may achieve a score that is higher than the score of any of the records already located and stored in the ranking list based upon query terms corresponding to index entries having a low weight, wherein the low weight is corresponds to the weight of the index entry having the lowest weight of the portion of the index searched; and

means for searching the index using query terms corresponding to index entries having weights higher than the low weight if no records yet to be located may achieve a score that is higher than the score of any of the records already located and stored in the ranking list based upon query terms corresponding to index entries having the low weight.

16. The system of claim 15, wherein the means for scoring comprises at least one processor.

17. The system of claim 15, wherein the means for storing comprises at least one memory.

18. The system of claim 15, wherein the means for determining comprises at It one processor.

19. The system of claim 15, wherein the means for searching comprises at least one processor.

20. A computer readable medium storing executable instructions thereon, the instructions when read by a processing device are operative to:

a memory device having executable instructions stored therein; and

a processing device coupled to and receiving the executable instructions therefrom, the processing device, in response to the executable instructions, is operative to;

score each located record according to the number of times portions of information corresponding to query terms occur in each record and the weight of each index entry corresponding to occurring query terms;

store the score and an identifier of each located record in a respective entry of a ranking list; and

in response to having searched a portion of the index, determine if any records yet to be located may achieve a score that is higher than the score of any of the records already located and stored in the ranking list based upon query terms corresponding to index entries having a low weight, wherein the low weight corresponds to the weight of the index entry having the lowest weight of the portion of the index searched, and if not, search the index using query terms corresponding to index entries having weights higher than the low weight.