Predictive stemming for web search with statistical machine translation models

Abstract

Techniques for determining when and how to transform words in a query to return the most relevant search results while minimizing computational overhead are provided. A dictionary is generated based upon words used in a specified number of previous most frequent search queries and comprises lists of transformations that may include variants based upon the stems of words, synonyms, and abbreviation expansions. When a query is received from a user, candidate queries are generated based upon replacing particular words in the query with a transformation of the particular words. Candidate queries are selected that have a high probability of returning relevant results by computing values of the query using language model scoring and translation scoring. The selected candidate queries and the original query are executed to return search results. The search results are displayed to the user with the words in the original query and the transformed words in bold.

1. A method, comprising:
 receiving a particular query comprising a plurality of words; 
 determining stems to at least one of the words in the particular query; 
 based on the stems of the plurality of words in the particular query, determining whether one or more stems of particular words in the particular query occurs in a dictionary comprising one or more transformations based upon stems of words; 
 selecting, from the dictionary, one or more transformations of the one or more stems of the particular words; 
 generating at least one candidate query that includes a transformation of one or more particular words; 
 computing a value for each candidate query; 
 selecting at least one candidate query to execute based upon the computed value for each candidate query; 
 executing the particular query and the at least one selected candidate query to generate search results across a plurality of documents; and 
 displaying at least a portion of the search results, 
 wherein the method is performed by one or more computing devices. 
 
   
   
     2. The method of  claim 1 , wherein the dictionary is generated prior to receiving a particular query from the user. 
   
   
     3. The method of  claim 2 , wherein the dictionary is based upon words used in a certain number of previous most frequent search queries. 
   
   
     4. The method of  claim 1 , wherein the dictionary is from a third-party provider. 
   
   
     5. The method of  claim 1 , wherein the one or more transformations of words in the dictionary includes synonyms of the words. 
   
   
     6. The method of  claim 1 , wherein the one or more transformations of words in the dictionary includes abbreviations of the words. 
   
   
     7. The method of  claim 1 , wherein the one or more transformations of words in the dictionary includes expansions of the words. 
   
   
     8. The method of  claim 1 , wherein the computing step uses a language model scoring algorithm. 
   
   
     9. The method of  claim 1 , wherein the computing step uses a language transformation scoring algorithm. 
   
   
     10. The method of  claim 1 , wherein the computing step uses a click-through rate scoring algorithm. 
   
   
     11. The method of  claim 1 , wherein the computing step uses an N-best scoring algorithm. 
   
   
     12. The method of  claim 1 , wherein displaying at least a portion of the search results further comprises:
 displaying a portion of the search results that contain the one or more particular words of the particular query or the transformations of the stem of the one or more particular words of the particular query. 
 
   
   
     13. The method of  claim 12 , wherein the one or more particular words of the particular query or the transformation of the stem of the one or more particular words of the particular query shown in the portion of the result is highlighted. 
   
   
     14. The method of  claim 1 , wherein the results further comprises documents that contain the transformation of the one or more particular words in the context of one or more particular words, or transformations of the one or more particular words, of the particular query. 
   
   
     15. A method, comprising:
 receiving a particular query from a user; 
 based on the particular query, determining whether one or more particular words in the particular query is able to be transformed; 
 determining one or more transformed forms of the one or more particular words; 
 determining whether using the one or more transformed forms of the one or more particular words has a probability to produce relevant search results that is higher than a specified threshold; 
 in response to determining that transforming the one or more particular words has a probability to produce relevant search results that is higher than a specified threshold, using a particular word and a transformed word for the particular word within a version of the particular query; 
 generating search results across a plurality of documents based on executing the particular query and the version of the particular query; and 
 displaying at least a portion of the search results; 
 wherein the method is performed by one or more computing devices. 
 
   
   
     16. The method of  claim 15 , wherein the transformations are variants based upon stems of words. 
   
   
     17. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform a method comprising:
 receiving a particular query comprising a plurality of words; 
 determining stems to at least one of the words in the particular query; 
 based on the stems of the plurality of words in the particular query, determining whether one or more stems of particular words in the particular query occurs in a dictionary comprising one or more transformations based upon stems of words; 
 selecting, from the dictionary, one or more transformations of the one or more stems of the particular words; 
 generating at least one candidate query that includes a transformation of one or more particular words; 
 computing a value for each candidate query; 
 selecting at least one candidate query to execute based upon the computed value for each candidate query; 
 executing the particular query and the at least one selected candidate query to generate search results across a plurality of documents; and 
 displaying at least a portion of the search results. 
 
   
   
     18. The machine-readable storage medium of  claim 17 , wherein the dictionary is generated prior to receiving a particular query from the user. 
   
   
     19. The machine-readable storage medium of  claim 18 , wherein the dictionary is based upon words used in a certain number of previous most frequent search queries. 
   
   
     20. The machine-readable storage medium of  claim 17 , wherein the dictionary is from a third-party provider. 
   
   
     21. The machine-readable storage medium of  claim 17 , wherein the one or more transformations of words in the dictionary includes synonyms of the words. 
   
   
     22. The machine-readable storage medium of  claim 17 , wherein the one or more transformations of words in the dictionary includes abbreviations of the words. 
   
   
     23. The machine-readable storage medium of  claim 17 , wherein the one or more transformations of words in the dictionary includes expansions of the words. 
   
   
     24. The machine-readable storage medium of  claim 17 , wherein the computing step uses a language model scoring algorithm. 
   
   
     25. The machine-readable storage medium of  claim 17 , wherein the computing step uses a language transformation scoring algorithm. 
   
   
     26. The machine-readable storage medium of  claim 17 , wherein the computing step uses a click-through rate scoring algorithm. 
   
   
     27. The machine-readable storage medium of  claim 17 , wherein the computing step uses an N-best scoring algorithm. 
   
   
     28. The machine-readable storage medium of  claim 17 , wherein displaying at least a portion of the search results further comprises displaying a portion of the search results that contain the one or more particular words of the particular query or the transformations of the step of the one or more particular words of the particular query. 
   
   
     29. The machine-readable storage medium of  claim 28 , wherein the one or more particular words of the particular query or the transformations of the stem of the one or more particular words of the particular query shown in the portion of the result is highlighted. 
   
   
     30. The machine-readable storage medium of  claim 17 , wherein the results further comprises documents that contain the transformation of the one or more particular words in the context of one or more particular words, or transformations of the one or more particular words of the particular query. 
   
   
     31. A machine-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform a method comprising:
 receiving a particular query from a user; 
 based on the particular query, determining whether one or more particular words in the particular query is able to be transformed; 
 determining one or more transformed forms of the one or more particular words; 
 determining whether using the one or more transformed forms of the one or more particular words has a probability to produce relevant search results that is higher than a specified threshold; 
 in response to determining that transforming the one or more particular words has a probability to produce relevant search results that is higher than a specified threshold, using a particular word and a transformed word for the particular word within a version of the particular query; 
 generating search results across a plurality of documents based on executing the particular query and the version of the particular query; and 
 displaying at least a portion of the search results. 
 
   
   
     32. The machine-readable storage medium of  claim 31 , wherein the transformations are variants based upon stems of words.