Search suggestion clustering and presentation

• US 8,631,004 B2
• Filed: 12/28/2009
• Issued: 01/14/2014
• 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: Mishne, Gilad, Jain, Alpa
• Primary Examiner(s): Richardson, James E
• Application Number:
  US12/648,220
• Publication Number:
  US 20110161311A1
• Time in Patent Office: 1,478 Days
• Field of Search: 707/727, 707/729, 707766-768, 715/816
• US Class Current: 707/727
• 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 in response to input of the segment of text via the search query section of the user interface, the segment of text being a portion of a search query that has not been submitted by a user;

obtaining a set of suggestions, each suggestion in the set of suggestions being a suggested completion of the search query such that the suggestion includes 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, wherein each of the two or more groups of suggestions corresponds to a different interpretation of the portion of the search query that has not been submitted by a user;

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;

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; and

for each one of the two or more groups of suggestions, identifying a sequence of characters that is at least a portion of each suggestion in 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 at least a portion of each suggestion in the corresponding subset of suggestions.

2. The method of claim 1, wherein

the label or image is provided 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 search results associated with each suggestion in the set of suggestions, each of the search results including a uniform research locator (URL);

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 associated with the corresponding suggestion, wherein the clickthrough data pertains to the URLs of the search results associated with the corresponding suggestion.

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; and

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

12. The method as recited in claim 1, wherein the portion of the search query is a sequence of characters typed by a user while formulating the search query.

13. The method as recited in claim 12, wherein the portion of the search query is a prefix, infix, or suffix.

14. The method as recited in claim 1, further comprising:

receiving a selection of a suggestion in one of the two or more groups of suggestions; and

executing the selected suggestion as a search query via one or more search applications.

15. A non-transitory computer-readable medium storing thereon computer-readable instructions, comprising:

instructions for obtaining a segment of text via a search query section of a user interface in response to input of the segment of text via the search query section of the user interface, the segment of text being a portion of a search query that has not been submitted by a user;

instructions for obtaining a set of suggestions, each suggestion in the set of suggestions being a suggested completion of the search query such that the suggestion includes the segment of text;

instructions for determining from the set of suggestions that the search query that has not been submitted by the user is an ambiguous query;

instructions for 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, wherein each of the two or more groups of suggestions corresponds to a different interpretation of the portion of the search query that has not been submitted by a user;

instructions for 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;

instructions for 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; and

instructions for identifying, for each one of the two or more groups of suggestions, a sequence of characters that is at least a portion of each suggestion in 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 at least a portion of each suggestion in the corresponding subset of suggestions.

16. The non-transitory computer-readable medium of claim 15,

wherein the label or image is provided such that the label or image is displayed in association with the corresponding partition of the search assistance segment of the user interface.

17. The non-transitory computer-readable medium of claim 15, further comprising:

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

18. The non-transitory computer-readable medium as recited in claim 15, wherein determining from the set of suggestions that the search query that has not been submitted by the user is an ambiguous query comprises determining that there is more than one possible interpretation of the portion of the search query that has not been submitted by the user.

19. An apparatus, comprising:

a processor; and

a memory, at least one of the processor and the memory being configured for;

obtaining a segment of text via a search query box of a user interface in response to input of the segment of text via the search query box of the user interface, the segment of text being a portion of a search query that has not been submitted by a user;

obtaining a set of suggestions, each suggestion in the set of suggestions being a suggested completion of the search query such that the suggestion includes the segment of text;

determining from the set of suggestions that the search query that has not been submitted by the user 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, wherein each of the two or more groups of suggestions corresponds to a different interpretation of the portion of the search query that has not been submitted by a user;

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;

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; and

for each one of the two or more groups of suggestions, identifying a sequence of characters that is at least a portion of each suggestion in 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 at least a portion of each suggestion in the corresponding subset of suggestions.

20. The apparatus of claim 19, 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.

21. The apparatus of claim 19, at least one of the processor or the memory being configured for performing steps, 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.

22. The apparatus of claim 21, wherein the representative suggestion is a most frequently occurring one of the subset of suggestions according to a query log.

23. The apparatus of claim 19, at least one of the processor or the memory being configured for performing steps, 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.

24. The apparatus of claim 23, 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.

25. The apparatus of claim 23, 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.

26. The apparatus of claim 19, at least one of the processor or the memory being configured for performing steps, 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.

27. The apparatus of claim 19, at least one of the processor or the memory being configured for performing steps, 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.