Tiering of posting lists in search engine index

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.

What is claimed is: 
     
         1 . One or more computer storage media storing a data structure for a search index, the data structure comprising:
 a plurality of posting lists, each posting list being associated with a different atom and including a plurality of postings, each posting within each posting list corresponding with a given document and identifying the given document and a rank for the given document, wherein at least one posting list is divided into a plurality of tiers, the tiers within the at least one posting list being ordered by rank while the postings within each tier being internally ordered by document sequence, wherein the search index supports performing additional processing during a search query, 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.   
     
     
         2 . The one or more computer-storage media of  claim 1 , wherein the number of tiers for the at least one posting list and the number of documents within each tier of the at least one posting list are determined based on the size of the document corpus used to generate the search index. 
     
     
         3 . The one or more computer storage media of  claim 1 , wherein tiers of the at least one posting list are stored on different types of storage devices. 
     
     
         4 . 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:
 accessing document content for a plurality of documents;   identifying atoms within the document content of each document;   determining ranks for atoms found in the document content of each document, wherein the rank for a given atom found in a given document comprises a score representing the importance of the given atom within the context of the given document; and   generating a search index comprising a plurality of posting lists, each posting list corresponding with an atom identified within the document content of the plurality of documents, wherein each posting within a given posting list corresponding with a particular atom identifies a document containing the atom and a rank for the document and the atom, wherein at least one posting list is divided into a plurality of tiers ordered based on rank, and wherein postings within each tier are internally ordered based on document, wherein the search index supports performing additional processing during a search query, 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.   
     
     
         5 . The one or more computer-storage media of  claim 4 , wherein the number of tiers for the at least one posting list and the number of documents within each tier of the at least one posting list are determined based on the size of the document corpus used to generate the search index. 
     
     
         6 . The one or more computer-storage media of  claim 4 , wherein the rank for a document within a posting of a posting list for an atom comprises a score representing the importance of the atom within the context of the document. 
     
     
         7 . The one or more computer-storage media of  claim 4 , wherein generating the search index comprises storing only a portion of the atoms identified for at least one document in the search index. 
     
     
         8 . The one or more computer-storage media of  claim 4 , wherein generating the search index comprises generating the at least one posting list to include postings for only a portion of the documents identified as containing the atom for the at least one posting list. 
     
     
         9 . The one or more computer storage media of  claim 4 , wherein tiers of the at least one posting list are stored on different types of storage devices. 
     
     
         10 . 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:   accessing document content for a plurality of documents;   identifying atoms within the document content of each document;   determining ranks for atoms found in the document content of each document, wherein the rank for a given atom found in a given document comprises a score representing the importance of the given atom within the context of the given document; and   generating a search index comprising a plurality of posting lists, each posting list corresponding with an atom identified within the document content of the plurality of documents, wherein each posting within a given posting list corresponding with a particular atom identifies a document containing the atom and a rank for the document and the atom, wherein at least one posting list is divided into a plurality of tiers ordered based on rank, and wherein postings within each tier are internally ordered based on document, wherein the search index supports performing additional processing during a search query, 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.   
     
     
         11 . The system of  claim 10 , wherein the number of tiers for the at least one posting list and the number of documents within each tier of the at least one posting list are determined based on the size of the document corpus used to generate the search index. 
     
     
         12 . The system of  claim 10 , wherein the rank for a document within a posting of a posting list for an atom comprises a score representing the importance of the atom within the context of the document. 
     
     
         13 . The system of  claim 10 , wherein generating the search index comprises storing only a portion of the atoms identified for at least one document in the search index. 
     
     
         14 . The system of  claim 10 , wherein generating the search index comprises generating the at least one posting list to include postings for only a portion of the documents identified as containing the atom for the at least one posting list. 
     
     
         15 . The system of  claim 10 , wherein tiers of the at least one posting list are stored on different types of storage devices. 
     
     
         16 . The system of  claim 10 , wherein the search engine server is 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 the 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;   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.   
     
     
         17 . The system of  claim 16 , 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.   
     
     
         18 . The system of  claim 17 , 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.   
     
     
         19 . The system of  claim 18 , 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. 
     
     
         20 . The system of  claim 19 , wherein the search engine server is configured for:
 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.