Systems and methods for performing search and retrieval of electronic documents using a big index

Abstract

Methods and systems for providing a search engine capability for large datasets are disclosed. These methods and systems employ a Partition-by-Query index containing key-values pairs corresponding to keys reflecting concept-ordered search phrases and values reflecting ordered lists of document references that are responsive to the concept-ordered search phrase in a corresponding key. A large Partition-by-Query index may be partitioned across multiple servers depending on the size of the index, or the size of the index may be reduced by compressing query-references pairs into dusters. The methods and systems described herein may to provide suggestions and spelling corrections to the user, thereby improving the user's search engine experience while meeting user expectations for search quality and responsiveness.

1 . A method for providing suggestions or spelling corrections in response to a search engine search query, the method comprising:
 generating by a computing device a confusion set of spelling corrections for a plurality of tokens in a corpus stored on a server, the confusion set comprising a plurality of producer lists,
 wherein each producer list associated with a token is a set of potential spelling corrections for the token and comprises residual strings derived by one or more character variations of the token, each residual string associated with a weight based on the number of character variations between the token and the residual string, 
 wherein for at least one token in the corpus there is at least one residual string that is generated from the token and that varies from the token by having at least one character that is not present in the token, 
 and wherein each producer list associated with the token forms a variation list for the residual string providing potential spelling corrections for the residual string, the variation list comprising the tokens that can be formed from the residual string and the number of character variations between each such token and the residual string; 
   receiving, by a computing device, one or more characters as input to a search engine;   retrieving, by the computing device, an entry from the confusion set on the server corresponding to the one or more characters; and   presenting, by the computing device, spelling corrections or suggestions to a user based at least in part on the entry retrieved from the confusion set.   
     
     
         2 . The method of  claim 1 , wherein retrieving an entry from the confusion set further comprises using a Bloom filter to determine whether there exists in the confusion set an entry corresponding to the one or more characters. 
     
     
         3 . The method of  claim 1 , wherein a character variation comprises character additions, modifications, or removals relative to a token. 
     
     
         4 . The method of  claim 1 , wherein a confusion set comprises suggestions and spelling corrections reflecting small and large changes to a given token, the confusion set prioritizing small changes to the token over large changes to the token. 
     
     
         5 . The method of  claim 1 , wherein a residual string is associated with one or more weights, each weight associated with a different token. 
     
     
         6 . The method of  claim 1 , further comprising:
 generating a confusion matrix comprising combinations of elements of the confusion set.   
     
     
         7 . The method of  claim 6 , further comprising:
 determining suggestions for presenting to the user using a Bloom filter on the confusion matrix for a plurality of confusion sets.   
     
     
         8 . A computer readable non-transitory storage medium storing instructions for:
 generating by a computing device a confusion set of spelling corrections for a plurality of tokens in a corpus stored on a server, the confusion set comprising a plurality of producer lists,
 wherein each producer list associated with a token is a set of potential spelling corrections for the token and comprises residual strings derived by one or more character variations of the token, each residual string associated with a weight based on the number of character variations between the token and the residual string, 
 wherein for at least one token in the corpus there is at least one residual string that is generated from the token and that varies from the token by having at least one character that is not present in the token, 
 and wherein each producer list associated with the token forms a variation list for the residual string providing potential spelling corrections for the residual string, the variation list comprising the tokens that can be formed from the residual string and the number of character variations between each such token and the residual string; 
   receiving, by a computing device, one or more characters as input to a search engine;   retrieving, by the computing device, an entry from the confusion set on the server corresponding to the one or more characters; and   presenting, by the computing device, spelling corrections or suggestions to a user based at least in part on the entry retrieved from the confusion set.   
     
     
         9 . The computer readable non-transitory storage medium of  claim 8 , wherein retrieving an entry from the confusion set further comprises using a Bloom filter to determine whether there exists in the confusion set an entry corresponding to the one or more characters. 
     
     
         10 . The computer readable non-transitory storage medium of  claim 8 , wherein a character variation comprises character additions, modifications, or removals relative to a token. 
     
     
         11 . The computer readable non-transitory storage medium of  claim 8 , wherein a confusion set comprises suggestions and spelling corrections reflecting small and large changes to a given token, the confusion set prioritizing small changes to the token over large changes to the token. 
     
     
         12 . The computer readable non-transitory storage medium of  claim 8 , wherein a residual string is associated with one or more weights, each weight associated with a different token. 
     
     
         13 . The computer readable non-transitory storage medium of  claim 8 , wherein the instructions are further for:
 generating a confusion matrix comprising combinations of elements of the confusion set.   
     
     
         14 . The computer readable non-transitory storage medium of  claim 8 , wherein the instructions are further for:
 determining suggestions for presenting to the user using a Bloom filter on the confusion matrix for a plurality of confusion sets.   
     
     
         15 . A computer system comprising:
 one or more processors; and   a computer readable non-transitory storage medium storing instructions for:
 generating by a computing device a confusion set of spelling corrections for a plurality of tokens in a corpus stored on a server, the confusion set comprising a plurality of producer lists,
 wherein each producer list associated with a token is a set of potential spelling corrections for the token and comprises residual strings derived by one or more character variations of the token, each residual string associated with a weight based on the number of character variations between the token and the residual string, 
 wherein for at least one token in the corpus there is at least one residual string that is generated from the token and that varies from the token by having at least one character that is not present in the token, 
 and wherein each producer list associated with the token forms a variation list for the residual string providing potential spelling corrections for the residual string, the variation list comprising the tokens that can be formed from the residual string and the number of character variations between each such token and the residual string; 
 
   receiving, by a computing device, one or more characters as input to a search engine;   retrieving, by the computing device, an entry from the confusion set on the server corresponding to the one or more characters; and   presenting, by the computing device, spelling corrections or suggestions to a user based at least in part on the entry retrieved from the confusion set.   
     
     
         16 . The computer system of  claim 15 , wherein retrieving an entry from the confusion set further comprises using a Bloom filter to determine whether there exists in the confusion set an entry corresponding to the one or more characters. 
     
     
         17 . The computer system of  claim 15 , wherein a character variation comprises character additions, modifications, or removals relative to a token. 
     
     
         18 . The computer system of  claim 15 , wherein a confusion set comprises suggestions and spelling corrections reflecting small and large changes to a given token, the confusion set prioritizing small changes to the token over large changes to the token. 
     
     
         19 . The computer system of  claim 15 , wherein a residual string is associated with one or more weights, each weight associated with a different token. 
     
     
         20 . The computer system of  claim 15 , wherein the instructions are further for:
 generating a confusion matrix comprising combinations of elements of the confusion set.