Tiering of posting lists in search engine index

• US 9,529,908 B2
• Filed: 11/22/2010
• Issued: 12/27/2016
• Est. Priority Date: 11/22/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Risvik, Knut Magne, Hopcroft, Michael, Bennett, John G., Kalyanaraman, Karthik, Chilimbi, Trishul
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Kim, Paul
• Application Number:
  US12/951,799
• Publication Number:
  US 20120130996A1
• Time in Patent Office: 2,227 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

A search index includes tiered posting lists. Each posting list in the search index corresponds with a different atom and includes a list of documents containing the particular document. Additionally, a rank is stored with each document listed in a posting list for a given atom representing the relevance of the atom to the context of each document. At least some of the posting lists in the search index are tiered. A tiered posting list is divided into a number of tiers with the tiers being ordered by document while each tier is internally ordered by document. Employing tiered posting lists within the search index allows a search engine to evaluate search queries in a manner that allows for a number of efficiencies and precise stopping.

Claims

1. One or more computer storage media storing computer useable instructions that, when used by a computing device, cause the computing device to perform a method comprising:

receiving a search query comprising one or more terms;

analyzing the search query to identify one or more atoms from the one or more terms;

querying a search index using the one or more atoms identified from the search query, wherein the search index comprises a plurality of postings lists, each posting list corresponding with an atom and including a plurality of postings, wherein each posting within a given posting list corresponding with the atom identifies a document containing the atom and a rank representing a significance of the atom for the document, wherein at least one posting list is divided into a plurality of tiers ordered based on rank;

and wherein querying the search index comprises determining whether to perform additional processing, to identify a plurality of documents, based on comparing a combined rank of a first set of documents identified after a first tier with a calculated combined rank of the first set of documents of the first tier and one or more documents of at least a second tier;

identifying the plurality of documents from querying the search index based on the plurality of tiers ordered based on rank and the postings within each of the plurality of tiers; and

providing a plurality of search results for presentation to an end user based on the plurality of documents identified by querying the search index.

2. The one or more computer storage media of claim 1, wherein querying the search index comprises:

determining that a single atom is identified from the search query;

identifying a posting list corresponding with the single atom;

retrieving postings from only the first tier of the posting list; and

providing search results from the first tier of the posting list.

3. The one or more computer storage media of claim 2, wherein providing search results from the first tier of the posting list comprises providing search results corresponding with a predetermined number of postings with the highest ranks from the first tier of the posting list.

4. The one or more computer storage media of claim 2, wherein providing search results from the first tier of the posting list comprises providing search results corresponding with postings having a rank above a predetermined threshold.

5. The one or more computer storage media of claim 2, wherein providing search results from the first tier of the posting list comprises:

calculating a preliminary score using a simplified scoring function for documents within the first tier of the posting list;

selecting a subset of documents based on the preliminary scores;

calculating a final ranking score using a final ranking algorithm for each document in the subset of documents; and

providing search results based on the final ranking scores.

6. The one or more computer storage media of claim 1, wherein querying the search index comprises:

determining that two or more atoms are identified from the search query;

identifying posting lists corresponding with the two or more atoms; and

merging a first level of tiers of the posting lists to obtain a set of ranked documents.

7. The one or more computer storage media of claim 6, wherein:

if it is determined to not analyze additional levels of tiers, providing a set of search results from the set of ranked documents;

if it is determined to analyze additional levels of tiers;

(1) repeating;

merging a combination of a next level of tiers of the posting lists to update the set of ranked documents, and evaluating whether to perform analysis of additional levels of tiers of the posting lists, until it is determined to not analyze additional levels of tiers; and

(2) providing a set of search results from the set of ranked documents when it is determined to not analyze additional levels of tiers.

8. The one or more computer storage media of claim 7, wherein determining whether to perform analysis of additional levels of tiers comprises evaluating whether one or more posting lists are long, wherein if one or more long posting lists are identified then at least one lower level tier from the one or more long posting lists is ignored and matching between posting lists is performed by consideration of combinations of other posting lists such that the at least one lower level tier from the one or more long posting lists is assumed present and resulting matches are deemed usefully close to an intent of the search query.

9. The one or more computer storage media of claim 8, wherein the method further includes determining overall ranking values for documents by assuming presence of one or more atoms corresponding with the one or more long posting lists in documents from the other posting lists and assigning a nominal value to compute the overall ranking values for the documents.

10. The one or more computer storage media of claim 7, wherein providing search results from the set of ranked documents comprises providing search results corresponding with a predetermined number of documents with the highest ranks from the set of ranked documents.

11. The one or more computer storage media of claim 7, wherein providing search results from the set of ranked documents comprises:

calculating a preliminary score using a simplified scoring function for documents within the set of ranked documents;

selecting a subset of documents based on the preliminary scores;

calculating a final ranking score using a final ranking algorithm for each document in the subset of documents; and

providing search results based on the final ranking scores.

12. A computer-implemented method for providing search results, the method comprising:

receiving a search query comprising one or more terms;

analyzing the search query to identify one or more atoms from the one or more terms;

querying a search index using the one or more atoms identified from the search query, wherein the search index comprises a plurality of postings lists, each posting list corresponding with an atom and including a plurality of postings, wherein each posting within a given posting list corresponding with an atom identifies a document containing the atom and a rank representing a significance of the atom for the document, wherein at least one posting list is divided into a plurality of tiers ordered based on rank,

and wherein querying the search index comprises determining whether to perform additional processing, to identify a plurality of documents, based on comparing a combined rank of a first set of documents identified after a first tier with a calculated combined rank of the first set of documents of the first tier and one or more documents of at least a second tier;

identifying a plurality of documents from querying the search index based on the plurality of tiers ordered based on rank and the postings within each of the plurality of tiers; and

providing a plurality of search results for presentation to an end user based on the plurality of documents identified by querying the search index.

13. The computer-implemented method of claim 12, wherein a number of tiers for at least one positing list and a number of documents within each tier of the at least one positing list is determined based on the size of the document corpus used to generate the search index.

14. The computer-implemented method of claim 12, further comprising:

determining not to analyze additional tiers, such that the first tier is the cut-index; and

providing a set of search results from the set of ranked documents.

15. The computer-implemented method of claim 12, further comprising:

determining to analyze additional of tiers, such that the first tier level is not the cut-index;

update a set of ranked documents from the first tier with a set of ranked document from at least one additional tier;

providing a set of search results from the updated set of ranked documents from the first tier and the at least one additional tier.

16. The computer-implemented method of claim 12, wherein querying the search index comprises:

determining that two or more atoms are identified from the search query;

identifying posting lists corresponding with the two or more atoms;

merging a first level of tiers of the posting lists to obtain a set of ranked documents;

determining to perform analysis of additional combinations of levels of tiers of the posting lists;

merging a combination of a next level of tiers of the posting lists to update the set of ranked documents; and

providing a set of search results updated from the set of ranked documents.

17. The computer-implemented method of claim 16, determining to perform analysis of additional levels of tiers is based on rankings of documents in a set of ranked documents in a first tier level and ranks of documents that can be obtained using additional levels of tiers.

18. The computer-implemented method of claim 16, wherein determining to perform analysis of additional levels of tiers comprises:

evaluating whether one or more posting lists are long, wherein if one or more long posting lists are identified then at least one lower level tier from the one or more long posting lists is ignored; and

matching between posting lists is performed by consideration of combinations of other posting lists such that the at least one lower level tier from the one or more long posting lists is assumed present and resulting matches are deemed usefully close to an intent of the search query.

19. The computer-implemented method of claim 18, wherein the method further includes:

determining overall ranking values for documents by assuming presence of one or more atoms corresponding with the one or more long posting lists in documents from the other posting lists and assigning a nominal value to compute the overall ranking values for the documents.

20. The computer-implemented method of claim 16, wherein providing search results from the set of ranked documents comprises:

calculating a preliminary score using a simplified scoring function for documents within the set of ranked documents;

selecting a subset of documents based on the preliminary scores;

calculating a final ranking score using a final ranking algorithm for each document in the subset of documents; and

providing search results based on the final ranking scores.

21. A system for providing search results, the system comprising:

a search engine server, having a processor and a memory configured for providing computer program instructions to the processor, the search engine server configured for;

receiving a search query comprising one or more terms;

analyzing the search query to identify one or more atoms from the one or more terms;

querying a search index using the one or more atoms identified from the search query, wherein the search index comprises a plurality of postings lists, each posting list corresponding with an atom and including a plurality of postings, wherein each posting within a given posting list corresponding with an atom identifies a document containing the atom and a rank representing a significance of the atom for the document, wherein at least one posting list is divided into a plurality of tiers ordered based on rank,

and wherein querying the search index comprises determining whether to perform additional processing, to identify a plurality of documents, based on comparing a combined rank of a first set of documents identified after a first tier with a calculated combined rank of the first set of documents of the first tier and one or more documents of at least a second tier;

identifying a plurality of documents from querying the search index based on the plurality of tiers ordered based on rank and the postings within each of the plurality of tiers; and

providing a plurality of search results for presentation to an end user based on the plurality of documents identified by querying the search index.