Fast ranked full-text searching

• US 20040267722A1
• Filed: 06/30/2003
• Published: 12/30/2004
• 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
• Granted Patent: US 7,630,963 B2
• Time in Patent Office: Days
• 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. In a system configured for identifying documents containing one or more key terms, a method for enabling fast ranked searching for documents containing the one or more key terms, the method comprising:

a step for creating an inverted index that identifies key terms and that identifies, for each key term, one or more documents that comprise the key term;

an act of creating a special list for at least one key term, the special list comprising a ranking of at least some of the documents that comprise the at least one key term; and

an act of searching the special list for documents containing the at least one key term and without searching the inverted index for each document comprising the at least one key term.

2. A method as recited in claim 1, wherein the ranking of the special list is determined with an algorithm that considers at least an occurrence of the at least one key term within the documents corresponding to the special list.

3. A method as recited in claim 2, wherein the ranking is performed with at least one of a probabilistic ranking algorithm, a vector ranking algorithm, a temporal ranking algorithm, and a page ranking algorithm.

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

5. A method as recited in claim 1, wherein the one or more documents include web pages.

6. A method as recited in claim 1, wherein a special list is created for each key term identified by the inverted index.

7. A method as recited in claim 1, wherein the special list identifies only a predetermined number of documents.

8. A method as recited in claim 1, wherein searching of the special list includes an application of one or more ranking algorithms to each document identified by the special list.

9. A method as recited in claim 1, further including an act of searching the inverted index for additional documents, subsequent to searching the special list, and corresponding to a single search.

10. A method as recited in claim 9, wherein a user can control an amount in which the inverted index is searched for additional documents.

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

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

13. A method as recited in claim 1, wherein the step for creating the inverted index includes:

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

an act of identifying key terms that occur within the identified documents; and

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

14. A method as recited in claim 13, wherein the step for creating the inverted index further includes an act of merging the one or more indices into a single inverted index.

15. A method as recited in claim 14, wherein ranking of the at least some of the documents is performed during merging.

16. 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.

17. A method as recited in claim 1, wherein the special list is stored separately from the inverted index.

18. In a system configured for identifying documents containing one or more key terms, a method for enabling fast ranked searching for documents containing the one or more key terms, the method comprising:

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

an act of identifying key terms that occur within the identified documents;

an act of creating an index that associates the identified key terms and, for each key term, documents that contain each key term;

an act of creating a special list for at least one key term, the special list comprising a ranking of at least some of the documents that comprise the at least one key term; and

an act of searching the special list for documents containing the at least one key term and without searching the index for each document comprising the at least one key term.

19. A method as recited in claim 18, wherein the ranking of the special list is determined with an algorithm that considers at least an occurrence of the at least one key term within the documents corresponding to the special list.

20. A method as recited in claim 19, wherein the ranking is performed during creation of the index.

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

22. A method as recited in claim 18, wherein the one or more documents include web pages.

23. A method as recited in claim 18, wherein a special list is created for each key term identified by the inverted index.

24. A method as recited in claim 23, wherein each key term includes at least one of a word, a letter, a number and a symbol.

25. A method as recited in claim 18, wherein the special list identifies only a predetermined number of documents.

26. A method as recited in claim 25, wherein the special list identifies a ranking value for each of the predetermined number of documents.

27. A method as recited in claim 18, further including an act of searching the inverted index for additional documents, subsequent to searching the special list, and corresponding to a single search.

28. A method as recited in claim 18, further including an act of modifying the special list after it has been created.

29. A method as recited in claim 18, wherein the special list is appended to a portion of the inverted index.

30. A method as recited in claim 18, wherein the special list is stored separately from the inverted index.

31. A computer program product for use in a system that is configured for identifying documents containing one or more key terms, the computer program product comprising one or more computer-readable media having computer-executable instructions for implementing a method for enabling fast ranked searching for documents containing the one or more key terms, the method including:

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

an act of identifying key terms that occur within the identified documents;

an act of creating an index that associates the identified key terms and, for each key term, documents that contain each key term;

an act of creating a special list for at least one key term, the special list comprising a ranking of at least some of the documents that comprise the at least one key term; and

an act of searching the special list for documents containing the at least one key term and without searching the index for each document comprising the at least one key term.

32. A computer program product as recited in claim 31, wherein the ranking of the special list is determined with an algorithm that considers at least an occurrence of the at least one key term within the documents corresponding to the special list.

33. A computer program product as recited in claim 31, wherein the one or more documents include a web page.

34. A computer program product as recited in claim 31, wherein the one or more documents include a document other than a web page.

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

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

37. A computer program product as recited in claim 31, wherein the method further includes an act of searching the inverted index for additional documents, subsequent to searching the special list, and corresponding to a single search.

38. A computer program product as recited in claim 31, wherein the method further includes an act of modifying the special list after it has been created.

39. A computer program product as recited in claim 31, wherein the special list is appended to a portion of the inverted index.

40. A computer program product as recited in claim 31, wherein the special

41. In a search engine configured for identifying documents containing one or more key terms, a method for enabling fast ranked searching for documents containing the one or more key terms, the method comprising:

an act identifying receiving one or more key terms corresponding to a search request;

an act of identifying an index of key terms and corresponding documents containing the key terms;

an act of identifying one or more special lists that identify only some of the corresponding documents containing the key terms; and

an act of searching the one or more special lists to identify one or more documents to return in response to the search request, and without searching the index to identify each document that contains the key terms.

42. A method as recited in claim 41, wherein each special list includes a ranking of the corresponding documents based at least in part on an occurrence of the one or more key terms within the documents.

43. A method as recited in claim 41, wherein the one or more key terms include at least two terms.

44. A method as recited in claim 43, wherein the at least two terms each include at least one of a word, a letter, a number and a symbol.

45. A method as recited in claim 41, further including an act of searching the inverted index for additional documents, subsequent to searching the special list, and corresponding to a search request.

46. A method as recited in claim 45, further including an act of enabling a user to control an amount in which the inverted index is searched for additional documents.

47. A method as recited in claim 46, further including an act of applying one or more ranking algorithms to any of the additional documents identified in the search.

48. A method as recited in claim 41, wherein the one or more special lists are stored separately from the inverted index.

49. A computer program product for use in a search engine configured for identifying documents containing one or more key terms, the computer program product including one or more computer-readable media having computer-executable instructions for implementing a method for enabling fast ranked searching for documents containing the one or more key terms, the method including:

an act identifying receiving one or more key terms corresponding to a search request;

an act of identifying an index of key terms and corresponding documents containing the key terms;

an act of identifying one or more special lists that identify only some of the corresponding documents containing the key terms; and

an act of searching the one or more special lists to identify one or more documents to return in response to the search request, and without searching the index to identify each document that contains the key terms.

50. A computer program product as recited in claim 49, wherein each special list includes ranking information for each of the only some corresponding documents and that is based at least in part on an occurrence of the one or more key terms within the documents.

51. A computer program product as recited in claim 50, wherein the ranking information is generated through the use of at least one of a probabilistic ranking algorithm, a temporal ranking algorithm, a vector ranking algorithm and a page rank algorithm.

52. A computer program product as recited in claim 49, wherein the method further includes an act of searching the inverted index for additional documents, subsequent to searching the special list, and corresponding to a search request.

53. A computer program product as recited in claim 49, wherein the method further includes an act of enabling a user to control an amount in which the inverted index is searched for additional documents.

54. A computer program product as recited in claim 53, wherein the method further includes an act of applying one or more ranking algorithms to any of the additional documents identified in the search.

55. A computer program product as recited in claim 49, wherein the one or more special lists are stored separately from the inverted index.

56. A computer program product as recited in claim 49, wherein the corresponding documents comprise web pages.

57. A computer program product as recited in claim 49, wherein the corresponding documents comprise at least one document that is not a web page.