Fast ranked full-text searching

• US 7,630,963 B2
• Filed: 06/30/2003
• Issued: 12/08/2009
• Est. Priority Date: 06/30/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Larimore, Stefan Isbein, Nayak, Tapas Kumar
• Primary Examiner(s): Padmanabhan; Kavita
• Application Number:
  US10/609,933
• Publication Number:
  US 20040267722A1
• Time in Patent Office: 2,353 Days
• Field of Search: None
• 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/99943 Generating database or data structure, e.g. via user interface

Abstract

Special lists can be used to perform fast ranked searching of documents containing key terms. The special lists are distinguished from basic inverted indices because they contain a ranking of only a predetermined number of documents that may be identified in the index. During a search, search engines can utilize the special lists to perform fast ranked searching without having to redundantly search through the entire corpus or index of documents available to the search engine. Rather, the search engine can search only the documents listed in the special list, thereby saving the time and resources required to perform the search. The search engine can also be configured to search a combination of the special lists and the index to provide users selective control over the balance between the accuracy and speed of the search.

Claims

1. A method for use in a computing system containing a database of available documents that are to be searched using one or more key terms, the method searching the database to identify a plurality of documents for subsequent presentation in a ranked order, and comprising:

using a ranking algorithm on documents identified by an inverted index as containing one or more key terms to create a special list for at least one key term, the special list for the at least one key term ranking a predetermined number of highest ranked documents identified in the inverted index as containing the at least one key term, wherein the ranking algorithm ranks documents in the special list according to a form consisting of Rank=(tf/K+tf), where K=dl/avdl, and wherein tf is occurrence of a key term in a document, dl is document length, and avdl is an average document length;

appending the special list to the inverted index and storing the inverted index on one or more computer readable storage medium, the inverted index having separate portions for each key term, and the portion for the at least one key term including;

a listing of documents that contain the at least one key term;

within the listing of documents, occurrence data for each of those documents; and

the special list for the at least one key term, the special list being separate from the listing of documents;

at a server computing device, receiving a user request for a search of the at least one key term, the user request also including a speed and thoroughness level for searching for the at least one key term;

at the server computing device, accessing the inverted index and the portion of the inverted index corresponding to the at least one key term;

at the server computing device, searching one or both of the inverted index and the special list for documents containing the at least one key term, such that;

when the speed and thoroughness level is a minimum thoroughness, only the special list is searched;

when the speed and thoroughness level is a maximum thoroughness, all relevant entries in the listing of documents in the inverted index are searched; and

when the speed and thoroughness level is between the minimum and maximum thoroughness, the special list is searched along with only a portion of relevant entries in the listing of documents within the inverted index.

2. A method as recited in claim 1, wherein the act of searching the special list is performed with one or more search engines.

3. A method as recited in claim 1, wherein the documents include web pages.

4. A method as recited in claim 1, wherein a special list is created for each key term identified by the inverted index and that has at least a minimum number of documents associated therewith in the inverted index.

5. A method as recited in claim 1, further including searching the inverted index for additional documents, wherein searching the inverted index for additional documents corresponds to a single user initiated search query also used to search the special list for documents, and is performed subsequent to searching the special list.

6. A method as recited in claim 5, wherein a user can control to what extent the inverted index is searched for additional documents.

7. A method as recited in claim 5, wherein one or more ranking algorithms are applied to any additional documents that are identified in the search of the inverted index subsequent to searching the special list.

8. A method as recited in claim 1, further including modifying the special list after it has been created.

9. A method as recited in claim 1, further comprising creating the inverted index, and wherein creating the inverted index includes:

identifying documents to be indexed for subsequent searching by one or more search engines;

identifying key terms that occur within the identified documents; and

creating one or more indices that associate the identified key terms and, for each key term, documents that contain each key term.

10. A method as recited in claim 9, wherein creating the inverted index further includes merging the one or more indices into a single inverted index.

11. A method as recited in claim 10, wherein the ranking algorithm is applied to at least some of the documents during merging.

12. A method as recited in claim 1, wherein the special list is appended to a portion of the inverted index that relates to the at least one key term to which the special list corresponds.

13. A method as recited in claim 1, wherein the at least one key term is a symbol.

14. A method as recited in claim 1, wherein at least some of the information used in ranking documents for the special list is included in the occurrence data within the listing of documents.

15. A method as recited in claim 14, wherein there are multiple special lists for multiple key terms, and wherein portions of the inverted index corresponding each of the multiple key terms have a corresponding special list.

16. A method as recited in claim 1, wherein the minimum thoroughness corresponds to a maximum speed, and wherein the maximum thoroughness corresponds to a minimum speed.

17. A computer program product for use in a computing system containing a database of available documents that is to be searched using one or more key terms, the computer program product enabling the computing system to search the database to identify a plurality of documents for subsequent presentation in a ranked order, the computer program product comprising:

one or more computer-readable storage media having computer-executable instructions encoded thereon for causing a computing system to;

apply a ranking algorithm on documents identified by an inverted index as containing one or more key terms to create a special list for at least one key term, the special list for the at least one key term ranking a predetermined number of highest ranked documents identified in the inverted index as containing the at least one key term, wherein the ranking algorithm ranks documents in the special list according to a form consisting of;

Rank=(tf/K+tf), where K=dl/avdl, and wherein tf is occurrence of a key term in a document, dl is document length, and avdl is an average document length;

append the special list to the inverted index, the inverted index having separate portions for each key term and the portion for the at least one key term including;

a listing of documents that contain the at least one key term;

within the listing of documents, occurrence data for each of those documents; and

the special list for the at least one key term, the special list being separate from the listing of documents;

receive a user request for a search of the at least one key term, the user request also including a speed and thoroughness level for searching for the at least one key term;

access the inverted index and the portion of the inverted index corresponding to the at least one key term;

search one or both of the inverted index and the special list for documents containing the at least one key term, such that;

when the speed and thoroughness level is a minimum thoroughness, only the special list is searched;

when the speed and thoroughness level is a maximum thoroughness, all relevant entries in the listing of documents in the inverted index are searched; and

when the speed and thoroughness level is between the minimum and maximum thoroughness, the special list is searched along with only a portion of relevant entries in the listing of documents in the inverted index.

18. A computer program product as recited in claim 17, wherein the documents include a web page.

19. A computer program product as recited in claim 17, wherein the documents include a document other than a web page.

20. A computer program product as recited in claim 17, wherein a special list is created for each key term identified by the index.

21. A computer program product as recited in claim 20, wherein each key term includes at least one of a word, a letter, a number and a symbol.

22. A computer program product as recited in claim 17, wherein the computer-executable instructions are encoded to further cause the computing system to search the inverted index for additional documents, subsequent to searching the special list, and corresponding to a single user-initiated search query also used in the search of the special list for documents.

23. A computer program product as recited in claim 17, wherein the computer-executable instructions are encoded to further cause the computing system to modify the special list after it has been created.

24. A method for searching a database of available documents for later presentation to a user in a ranked order, the method comprising:

at a web-based search engine on a server computing device, receiving a user-initiated search request that identifies one or more key terms to be searched for in the database of available documents;

at the web-based search engine on a server computing device, receiving a user indication of a speed and thoroughness level for searching the database of available documents for the one or more key terms;

accessing an inverted index stored on computer-readable storage media, the inverted index having terms found within documents in the database, the inverted index having separate portions for each term and each portion of a respective term including;

a listing of those documents that contain the respective term;

within the listing of those documents that contain the respective term, occurrence data for each of those documents; and

a special list specific to the respective term and appended to the inverted index apart from the listing of those documents that contain the respective term, the special list identifying a predetermined number of highest ranked documents from the listing, the special list ranking corresponding documents according to a form consisting of Rank=(tf/K+tf), where K=dl/avdl, and wherein tf is occurrence of a key term in a document, dl is document length, and avdl is an average document length; and

accessing inverted index portions for terms corresponding to each of the one or more key terms, and;

when the user indication of the speed and thoroughness level is a first thoroughness, searching only the special lists corresponding to the one or more key terms;

when the user indication of the speed and thoroughness level is a second thoroughness, searching all relevant entries in the inverted index; and

when the user indication of the speed and thoroughness level is a third thoroughness between the fist thoroughness and the second thoroughness, searching the special lists corresponding to the one or more key terms and only a portion of other relevant entries in the inverted index.