Technique for ranking records of a database

• US 6,317,741 B1
• Filed: 08/07/2000
• Issued: 11/13/2001
• Est. Priority Date: 08/09/1996
• Status: Expired due to Term

• Current Assignee: Eureka Database Solutions, LLC (Dominion Harbor Enterprises, LLC)
• Original Assignee: AltaVista Company (Apollo Global Management, Inc.)
• Inventors: Burrows, Michael
• Primary Examiner(s): AMSBURY, WAYNE P
• Application Number:
  US09/634,465
• Time in Patent Office: 463 Days
• Field of Search: 707/5, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/3341 using boolean model
• 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/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• 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. The database records to be ranked are located during a search of an index to the database performed in response to a query received from a user. The index has a plurality of index entries, wherein each index entry has a weight. The query has a plurality of query terms, wherein each query term corresponds to an index entry. In one embodiment, the technique is realized by scoring each located record according to the number of times portions of information corresponding to each query term occur in each record and the weight of each index entry corresponding to each occurring query term. The score and an identifier of each located record are then stored in a respective entry of a ranking list. The ranking list has a limit on the number of entries that are stored therein. In response to the ranking list reaching the limit, it is determined 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. If not, the index is searched using query terms corresponding to index entries having weights higher than the low 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 received from a user, the index having a plurality of index entries, each index entry having a weight, the query having a plurality of query terms, each query term corresponding to an index entry, the method comprising the steps of:

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

storing the score and an identifier of each located record in a respective entry of a ranking list, the ranking list having a limit on the number of entries stored therein; and

in response to the ranking list reaching the limit, 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, and, if not, searching the index using query terms corresponding to index entries having weights higher than the low weight.

2. The method as defined in claim 1, wherein each index entry has a word entry corresponding 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.

3. The method as defined in claim 1, further comprising the step of:

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

4. The method as defined in claim 3, further comprising the step of:

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

5. The method as defined in claim 4, wherein the provided information associated with each located record is the score of each located record.

6. The method as defined in claim 4, wherein the provided information associated with each located record is the identifier of each located record.

7. A system for ranking records of a database located during a search of an index to the database performed in response to a query received from a user, the index having a plurality of index entries, each index entry having a weight, the query having a plurality of query terms, each query term corresponding to an index entry, the system comprising:

at least one processor configured to score each located record according to the number of times portions of information corresponding to each query term occur in each record and the weight of each index entry corresponding to each occurring query term; 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, the ranking list having a limit on the number of entries stored therein;

wherein, in response to the ranking list reaching the limit, 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, and, if not, search the index using query terms corresponding to index entries having weights higher than the low weight.

8. The system as defined in claim 7, wherein each index entry has a word entry corresponding 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.

9. The system as defined in claim 7, wherein the at least one processor is also configured to order the entries of the ranking list according to the scores.

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

11. The system as defined in claim 10, wherein the provided information associated with each located record is the score of each located record.

12. The system as defined in claim 10, wherein the provided information associated with each located record is the identifier of each located record.

13. An article of manufacture for ranking records of a database located during a search of an index to the database performed in response to a query received from a user, the index having a plurality of index entries, each index entry having a weight, the query having a plurality of query terms, each query term corresponding to an index entry, the article of manufacture comprising:

at least one processor readable carrier; and

instructions carried on the at least one carrier;

wherein the instructions are configured to be readable from the at least one carrier by at least one processor and thereby cause the at least one processor to operate so as to;

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

store the score and an identifier of each located record in a respective entry of a ranking list, the ranking list having a limit on the number of entries stored therein; and

in response to the ranking list reaching the limit, 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, and, if not, search the index using query terms corresponding to index entries having weights higher than the low weight.

14. The article of manufacture as defined in claim 13, wherein each index entry has a word entry corresponding a unique portion of information of the database, wherein the instructions are further configured to cause the at least one processor to operate so as 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.

15. The article of manufacture as defined in claim 13, wherein the instructions are further configured to cause the at least one processor to operate so as to:

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

16. The article of manufacture as defined in claim 15, wherein the instructions are further configured to cause the at least one processor to operate so as to:

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

17. The article of manufacture as defined in claim 16, wherein the provided information associated with each located record is the score of each located record.

18. The article of manufacture as defined in claim 16, wherein the provided information associated with each located record is the identifier of each located record.

19. A system for ranking records of a database located during a search of an index to the database performed in response to a query received from a user, the index having a plurality of index entries, each index entry having a weight, the query having a plurality of query terms, each query term corresponding to an index entry, the system comprising:

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

means for storing the score and an identifier of each located record in a respective entry of a ranking list, the ranking list having a limit on the number of entries stored therein;

means for 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 in response to the ranking list reaching the limit; 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.

20. The system as defined in claim 19, wherein the means for scoring comprises at least one processor.

21. The system as defined in claim 19, wherein the means for storing comprises at least one memory.

22. The system as defined in claim 19, wherein the means for determining comprises at least one processor.

23. The system as defined in claim 19, wherein the means for searching comprises at least one processor.

24. The system as defined in claim 19, wherein each index entry has a word entry corresponding a unique portion of information of the database, further comprising:

means for 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.

25. The system as defined in claim 24, wherein the means for assigning comprises at least one processor.

26. The system as defined in claim 19, further comprising:

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

27. The system as defined in claim 26, wherein the means for ordering comprises at least one processor.