Predictive Stemming for Web Search with Statistical Machine Translation Models

• US 20090055380A1
• Filed: 08/22/2007
• Published: 02/26/2009
• Est. Priority Date: 08/22/2007
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Lu, Yumao, Ahmed, Nawaaz, Zagha, Marco J., PENG, Fuchun
• Granted Patent: US 7,788,276 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/374 Thesaurus

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.

Claims

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 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.

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 or the transformation of the one or more particular words 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.

19. 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 the method recited in claim 1.

20. 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 the method recited in claim 2.

21. 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 the method recited in claim 3.

22. 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 the method recited in claim 4.

23. 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 the method recited in claim 5.

24. 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 the method recited in claim 6.

25. 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 the method recited in claim 7.

26. 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 the method recited in claim 8.

27. 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 the method recited in claim 9.

28. 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 the method recited in claim 10.

29. 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 the method recited in claim 11.

30. 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 the method recited in claim 12.

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 the method recited in claim 13.

32. 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 the method recited in claim 14.

15. A method, comprising:

obtaining a vocabulary of all words used in a specified number of most frequently entered search queries submitted by users;

generating, based on the vocabulary, a dictionary comprising one or more transformations of words;

receiving a particular query from a user;

based on the particular query, determining whether one or more particular words in the particular query occur in the dictionary;

selecting, from the dictionary, a different form of a particular word that is indicated by a transformation in which the particular word occurs;

generating search results across a plurality of documents based on executing a version of the particular query that includes both the original and the different form of the one or more particular words; and

displaying at least a portion of the search results.

16. The method of claim 15, wherein the transformations are variants based upon stems of words.

33. 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 the method recited in claim 15.

34. 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 the method recited in claim 16.

17. 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 high probability to produce relevant search results;

in response to determining that transforming the one or more particular words has a high probability to produce relevant search results, using a particular word and a transformed word for the particular word within a version of the particular query; and

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.

18. The method of claim 17, wherein the transformations are variants based upon stems of words.

35. 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 the method recited in claim 17.

36. 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 the method recited in claim 18.