SEARCH SUGGESTION CLUSTERING AND PRESENTATION

• US 20110161311A1
• Filed: 12/28/2009
• Published: 06/30/2011
• Est. Priority Date: 12/28/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Jain, Alpa, Mishne, Gilad
• Granted Patent: US 8,631,004 B2
• Time in Patent Office: Days
• US Class Current: 707/719
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation

Abstract

Disclosed are methods and apparatus for clustering and presenting search suggestions. A segment of text is obtained via a search query section of a user interface, the segment of text being a portion of a search query. A set of suggestions is obtained, each suggestion in the set of suggestions being a suggested search query relating to the segment of text. Two or more groups of suggestions are generated, each of the two or more groups of suggestions including a different subset of the set of suggestions. The two or more groups of suggestions are provided such that each of the two or more groups of suggestions is displayed in a separate partition of a search assistance segment of the user interface.

Claims

1. A method, comprising:

obtaining a segment of text via a search query section of a user interface, the segment of text being a portion of a search query;

obtaining a set of suggestions, each suggestion in the set of suggestions being a suggested search query relating to the segment of text;

generating two or more groups of suggestions, each of the two or more groups of suggestions including a different subset of the set of suggestions; and

providing the two or more groups of suggestions such that each of the two or more groups of suggestions is displayed in a separate section of a search assistance segment of the user interface.

2. The method of claim 1, wherein providing the two or more groups of suggestions comprises:

providing a label or image identifying each of the two or more groups of suggestions such that the label or image is displayed in association with the corresponding partition of the search assistance segment of the user interface.

3. The method of claim 1, wherein generating two or more groups of suggestions comprises:

obtaining a set of one or more features associated with each suggestion in the set of suggestions; and

applying the set of one or more features associated with each suggestion in the set of suggestions to generate the two or more groups of suggestions.

4. The method of claim 3, further comprising:

parsing each suggestion in the set of suggestions to obtain a set of one or more words for the corresponding suggestion;

wherein the set of one or more features associated with each suggestion in the set of suggestions includes a representative word in the corresponding set of one or more words.

5. The method of claim 3, further comprising:

obtaining a set of search results associated with each suggestion in the set of suggestions, each search result of the set of search results include a corresponding title, abstract and uniform research locator (URL);

wherein the set of one or more features associated with each suggestion in the set of suggestions includes or is based upon a set of words in the corresponding set of search results.

6. The method of claim 5, wherein the set of words in the corresponding set of search results includes at least one of words in the title of at least a portion of the set of search results, words in the abstract of at least a portion of the set of search results, or words in the URL of at least a portion of the set of search results.

7. The method of claim 3, further comprising:

obtaining clickthrough data associated with each suggestion in the set of suggestions;

wherein the set of one or more features associated with each suggestion in the set of suggestions includes the obtained clickthrough data.

8. The method of claim 1, further comprising:

determining whether to present the two or more groups of suggestions;

wherein providing the two or more groups of suggestions is performed according to whether it is determined that the two or more groups of suggestions are to be presented.

9. The method of claim 1, further comprising:

ascertaining an order in which the subset of the set of suggestions within each of the two or more groups of suggestions is to be provided;

wherein providing the two or more groups of suggestions is performed such that the subset of the set of suggestions of each of the two or more groups of suggestions are displayed in a corresponding partition of the search assistance segment of the user interface according to the ascertained order.

10. The method of claim 1, further comprising:

ascertaining an order in which the two or more groups of suggestions are to be provided prior to providing the two or more groups of suggestions;

wherein providing the two or more groups of suggestions is performed such that the two or more groups of suggestions are displayed in separate partitions of the search assistance segment of the user interface according to the ascertained order.

11. The method of claim 10, wherein ascertaining an order in which the two or more groups of suggestions are to be provided comprises:

applying a cost metric to generate a numerical value representing an expected cost of locating a suggestion from among the two or more groups of suggestions;

minimizing the expected cost of locating a suggestion from among the two or more groups of suggestions.

12. A method, comprising:

obtaining a segment of text via a search query section of a user interface, the segment of text being a portion of a search query;

obtaining a set of suggestions, each suggestion in the set of suggestions being a suggested search query relating to the segment of text;

determining from the set of suggestions that the search query is an ambiguous query;

generating two or more groups of suggestions, each of the two or more groups of suggestions including a different subset of the set of suggestions; and

providing the two or more groups of suggestions such that each of the two or more groups of suggestions is displayed in a separate partition of a search assistance segment of the user interface.

13. The method of claim 12, further comprising:

providing a label or image identifying each of the two or more groups of suggestions such that the label or image is displayed in association with the corresponding partition of the search assistance segment of the user interface.

14. The method of claim 12, further comprising:

generating a first set of two or more groups of suggestions, each of the first set of two or more groups of suggestions including a different subset of the set of suggestions;

wherein determining from the set of suggestions that the search query is an ambiguous query is performed based upon a number of suggestions in each of the first set of two or more groups of suggestions.

15. The method of claim 12, wherein each of the two or more groups of suggestions corresponds to a different interpretation of the portion of the search query.

16. A method, comprising:

obtaining a segment of text via a search query box of a user interface, the segment of text being a portion of a search query;

obtaining a set of suggestions, each suggestion in the set of suggestions being a suggested search query including the segment of text;

generating two or more groups of suggestions, each of the two or more groups of suggestions including a different subset of the set of suggestions;

providing the two or more groups of suggestions such that each of the two or more groups of suggestions is displayed in a separate segment of a search assistance segment of the user interface; and

providing a label or image in association with each of the two or more groups of suggestions such that the label or image is displayed in the user interface in close proximity to the corresponding one of the two or more groups of suggestions.

17. The method of claim 16, wherein the label or image associated with each of the two or more groups of suggestions is provided in the corresponding segment of the search assistance segment of the user interface.

18. The method of claim 16, further comprising:

identifying a representative suggestion from the subset of suggestions for each one of the two or more groups of suggestions; and

obtaining a representative label or image associated with the representative suggestion in the corresponding one of the two or more groups of suggestions;

wherein providing the label or image in association with each of the two or more groups of suggestions includes providing the representative label or image associated with the representative suggestion in the corresponding one of the two or more groups of suggestions.

19. The method of claim 18, wherein the representative suggestion is a most frequently occurring one of the subset of suggestions according to a query log.

20. The method of claim 16, further comprising:

for each one of the two or more groups of suggestions, identifying a sequence of characters that is common to the corresponding subset of the set of suggestions;

wherein providing the label or image in association with each of the two or more groups of suggestions includes providing a label or image associated with the sequence of characters that is common to the corresponding subset of suggestions.

21. The method of claim 16, further comprising:

for each of the two or more groups of suggestions, obtaining a set of search results associated with the corresponding subset of the set of suggestions, each search result of the set of search results include a corresponding title, abstract and uniform research locator (URL); and

identifying or generating a label for each of the two or more groups of suggestions using the corresponding set of search results.

22. The method of claim 21, wherein obtaining the set of search results is performed by executing a search query for one or more suggestions in the corresponding subset of the set of suggestions.

23. The method of claim 21, wherein obtaining the set of search results is performed by executing a search query using only portions of suggestions in the corresponding subset of the set of suggestions that are distinct within the corresponding one of the two or more groups of suggestions.

24. The method of claim 16, further comprising:

for each one of the two or more groups of suggestions;

identifying a topic or aspect that is shared by the subset of the set of suggestions in the one of the two or more groups of suggestions, wherein the topic or aspect is not shared by other subsets of suggestions in the set of suggestions; and

obtaining a label or image representing the topic or aspect, thereby enabling the label or image to be provided in association with the corresponding one of the two or more groups of suggestions.

25. The method of claim 16, further comprising:

for each one of the two or more groups of suggestions;

ascertaining a degree of cohesion of the one of the two or more groups of suggestions; and

obtaining a label or image associated with the one of the two or more groups of suggestions using information external to the one of the two or more groups of suggestions according to the degree of cohesion of the one of the two or more groups of suggestions.