Search and retrieval of electronic documents using key-value based partition-by-query indices
View Patent ↗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 clusters. 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 suggested search queries in response to a search query, the method comprising:
generating, by a computing device, a confusion set for each token in the search query, wherein each confusion set comprises a plurality of residual strings formed from a token of the search query by adding, modifying, or removing characters in each position of the token, and other tokens associated with the residual strings, wherein for at least one token in the search query there is at least one residual string in the confusion set that varies from the token by having at least one character that is not present in the token;
generating, by the computing device, a confusion matrix from the confusion sets, wherein the confusion matrix comprises entries that are the products of the residual strings and tokens in the confusion sets, wherein the entries form potential suggested search queries;
ranking, by the computing device, the suggested search queries in the confusion matrix by a vector space angle between the search query and the suggested search queries, wherein the search query and each suggested search query is associated with a vector;
selecting, by the computing device, each ranked suggested search query having a vector space angle between the search query and the ranked suggested search query that is less than a vector space angle between the search query and a document associated with a higher-ranked suggested search query; and
presenting the selected suggested search queries on a computing device.
2. The method of claim 1 , further comprising the step of generating, by the computing device, a Bloom filter for the confusion matrix, wherein each element of the Bloom filter corresponds to an entry in the confusion matrix, and removing entries from the confusion matrix using the Bloom filter.
3. The method of claim 1 , wherein the search query comprises a plurality of tokens including a first token and a second token, and the vector space angle between the search query and a particular document is determined based on:
a TF-IDF value of the first token,
a TF-IDF value of the second token,
a similarity between a particular token from the plurality of tokens and a suggestion for the particular token, and
a magnitude of a vector formed by the document.
4. The method of claim 1 , wherein the confusion matrix is a reduced form confusion matrix formed from a selected element of a confusion set while excluding the remaining elements of the confusion set.
5. The method of claim 4 , further comprising:
identifying a subset of rows of the reduced form confusion matrix by ranking the rows based on a similarity of each row of the confusion matrix to a combination of individually spell-corrected tokens; and
combining a plurality of single-word tokens to obtain a multi-word token.
6. An apparatus for generating a list of the most relevant suggestions or spelling corrections to a search engine user from a collection of suggestions or spelling corrections, the apparatus comprising:
means for generating, by a computing device, confusion sets for each token in a search query, wherein each confusion set comprises a plurality of residual strings formed from a token of the search query by adding, modifying, or removing characters in each position of the token, and other tokens associated with the residual strings;
means for generating, by the computing device, a confusion matrix from the confusion sets, wherein the confusion matrix comprises entries that are the products of the residual strings and tokens in the confusion sets, wherein the entries form potential suggested search queries;
means for ranking, by the computing device, the suggested search queries in the confusion matrix by a vector space angle between the search query and the suggested search queries, wherein the search query and each suggested search query is associated with a vector; and
means for selecting, by the computing device, each ranked suggested search query having a vector space angle between the search query and the ranked suggested search query that is less than a vector space angle between the search query and a document associated with a higher-ranked suggested search query.
7. The apparatus of claim 6 , further comprising the step of generating, by the computing device, a Bloom filter for the confusion matrix, wherein each element of the Bloom filter corresponds to an entry in the confusion matrix, and removing entries from the confusion matrix using the Bloom filter.
8. The apparatus of claim 6 , wherein the search query comprises a plurality of tokens including a first token and a second token, and the vector space angle between the search query and a particular document is determined based on:
a TF-IDF value of the first token,
a TF-IDF value of the second token,
a similarity between a particular token from the plurality of tokens and a suggestion for the particular token, and
a magnitude of a vector formed by the document.
9. The apparatus of claim 6 , wherein the confusion matrix is a reduced form confusion matrix formed from a selected element of a confusion set while excluding the remaining elements of the confusion set.
10. The apparatus of claim 9 , further comprising:
means for identifying a subset of rows of the reduced form confusion matrix by ranking the rows based on a similarity of each row of the confusion matrix to a combination of individually spell-corrected tokens; and
means for combining a plurality of single-word tokens to obtain a multi-word token.
11. A computer-readable memory, storing instructions for providing suggested search queries in response to a search query, the instructions performing steps comprising:
generating, by a computing device, a confusion set for each token in the search query, wherein each confusion set comprises a plurality of residual strings formed from a token of the search query by adding, modifying, or removing characters in each position of the token, and other tokens associated with the residual strings, wherein for at least one token in the search query there is at least one residual string in the confusion set that varies from the token by having at least one character that is not present in the token;
generating, by the computing device, a confusion matrix from the confusion sets, wherein the confusion matrix comprises entries that are the products of the residual strings and tokens in the confusion sets, wherein the entries form potential suggested search queries;
ranking, by the computing device, the suggested search queries in the confusion matrix by a vector space angle between the search query and the suggested search queries, wherein the search query and each suggested search query is associated with a vector;
selecting, by the computing device, each ranked suggested search query having a vector space angle between the search query and the ranked suggested search query that is less than a vector space angle between the search query and a document associated with a higher-ranked suggested search query; and
presenting the selected suggested search queries on a computing device.
12. The computer-readable memory of claim 11 , wherein the instructions further perform the step of generating, by the computing device, a Bloom filter for the confusion matrix, wherein each element of the Bloom filter corresponds to an entry in the confusion matrix, and removing entries from the confusion matrix using the Bloom filter.
13. The computer-readable memory of claim 11 , wherein the search query comprises a plurality of tokens including a first token and a second token, and the vector space angle between the search query and a particular document is determined based on:
a TF-IDF value of the first token,
a TF-IDF value of the second token,
a similarity between a particular token from the plurality of tokens and a suggestion for the particular token, and
a magnitude of a vector formed by the document.
14. The computer-readable memory of claim 11 , wherein the confusion matrix is a reduced form confusion matrix formed from a selected element of a confusion set while excluding the remaining elements of the confusion set.
15. The computer-readable memory of claim 14 , wherein the instructions are for further performing the steps of:
identifying a subset of rows of the reduced form confusion matrix by ranking the rows based on a similarity of each row of the confusion matrix to a combination of individually spell-corrected tokens; and
combining a plurality of single-word tokens to obtain a multi-word token.
16. A computer system comprising:
one or more processors; and
a computer-readable memory, storing instructions for providing suggested search queries in response to a search query, the instructions performing steps comprising:
generating, by a computing device, a confusion set for each token in the search query, wherein each confusion set comprises a plurality of residual strings formed from a token of the search query by adding, modifying, or removing characters in each position of the token, and other tokens associated with the residual strings, wherein for at least one token in the search query there is at least one residual string in the confusion set that varies from the token by having at least one character that is not present in the token;
generating, by the computing device, a confusion matrix from the confusion sets, wherein the confusion matrix comprises entries that are the products of the residual strings and tokens in the confusion sets, wherein the entries form potential suggested search queries;
ranking, by the computing device, the suggested search queries in the confusion matrix by a vector space angle between the search query and the suggested search queries, wherein the search query and each suggested search query is associated with a vector;
selecting, by the computing device, each ranked suggested search query having a vector space angle between the search query and the ranked suggested search query that is less than a vector space angle between the search query and a document associated with a higher-ranked suggested search query; and
presenting the selected suggested search queries on a computing device.
17. The computer system of claim 16 , wherein the computer-readable memory stores instructions for further performing the step of generating, by the computing device, a Bloom filter for the confusion matrix, wherein each element of the Bloom filter corresponds to an entry in the confusion matrix, and removing entries from the confusion matrix using the Bloom filter.
18. The computer system of claim 16 , wherein the search query comprises a plurality of tokens including a first token and a second token, and the vector space angle between the search query and a particular document is determined based on:
a TF-IDF value of the first token,
a TF-IDF value of the second token,
a similarity between a particular token from the plurality of tokens and a suggestion for the particular token, and
a magnitude of a vector formed by the document.
19. The computer system of claim 16 , wherein the confusion matrix is a reduced form confusion matrix formed from a selected element of a confusion set while excluding the remaining elements of the confusion set.
20. The computer system of claim 19 , wherein the computer-readable memory stores further instructions for performing the steps of:
identifying a subset of rows of the reduced form confusion matrix by ranking the rows based on a similarity of each row of the confusion matrix to a combination of individually spell-corrected tokens; and
combining a plurality of single-word tokens to obtain a multi-word token.