Query suggestions with high utility

• US 8,751,520 B1
• Filed: 12/28/2010
• Issued: 06/10/2014
• Est. Priority Date: 06/23/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bhattacharjee, Rajat, Mehta, Aranyak, Zhang, Benyu, Raghunathan, Vivek
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US12/979,575
• Time in Patent Office: 1,260 Days
• Field of Search: 707/728, 707/713, 707/706, 707/762, 707/722, 707/769, 707/710, 707/723, 707/759
• US Class Current: 707/767
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for enhancing selecting relevant and diverse advertisements. In one aspect, a method includes receiving an initial query, selecting one or more additional queries relating to the initial query, including selecting additional queries having a greatest utility, identifying one or more content items for each of the additional queries, the one or more content items forming a content block, and providing a content block and an associated additional query to a client device to be displayed along with search results associated with the initial query.

Claims

1. A method comprising:

receiving an initial query;

identifying one or more additional queries related to the initial query;

determining a respective utility measure for each of the one or more additional queries, wherein the utility measure represents a likelihood that an additional query would be a final query in a series of query refinements from the initial query issued in a query session;

selecting an additional query from the one or more identified additional queries having a highest utility measure among the one or more identified additional queries;

identifying one or more content items for the selected additional query;

generating a content block comprising one or more content items identified for the selected additional query; and

providing the content block to a client device to be displayed along with search results associated with the initial query.

2. The method of claim 1, wherein the initial query includes one or more query terms.

3. The method of claim 1, wherein the additional query includes one or more terms from the initial query.

4. The method of claim 1, wherein the utility measure is based on a probability that a particular additional query is a final destination in a in a random walk of a query graph.

5. The method of claim 1, further comprising:

obtaining a query graph representing one or more query refinements from the initial query to one of the additional queries, wherein the query graph comprises nodes that each represents a query refinement and edges having respective weights, wherein each weight represents a likelihood of a subsequent query refinement being submitted in a query session; and

using the query graph to determine the utility measure for the selected additional query.

6. A method comprising

receiving an initial query;

selecting one or more additional queries relating to the initial query;

determining a respective utility measure for each of the one or more additional queries, wherein the utility measure represents a likelihood that a respective additional query would be a final query submitted in a query session, wherein the utility measure is determined from a query graph that represents one or more query refinements from the initial query to one of the additional queries, wherein each particular query refinement in the graph has a respective associated weight that represents a likelihood of the particular query refinement being submitted in the query session;

selecting an additional query from the one or more additional queries having a highest utility measure; and

providing the selected additional query to a client device to be displayed along with search results associated with the initial query.

7. The method of claim 6, wherein determining a utility measure for an additional query comprises evaluating the query using one or more commerciality criteria.

8. The method of claim 6, further comprising:

determining a commerciality score for the selected additional query; and

determining that the commerciality score for the additional query satisfies a commerciality threshold.

9. The method of claim 8, wherein the commerciality score is based on one or more signals selected from the group comprising revenue generated from a respective additional query, a number of content items shown in response to each respective additional query, a long click or short click associated with a content item shown in response to each respective additional query, or commerce keywords associated with search results shown in response to each respective additional query.

10. The method of claim 6, wherein the initial query includes one or more query terms.

11. The method of claim 6, wherein the additional query includes one or more terms from the initial query and one or more additional terms.

12. The method of claim 6, wherein each additional query includes at least a portion of the initial query.

13. The method of claim 6, wherein the additional queries are contextually relevant to the initial query.

14. The method of claim 6, wherein the additional queries represent queries that users have historically been entered after having entered the initial query.

15. A system comprising:

one or more computers; and

a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving an initial query;

identifying one or more additional queries related to the initial query;

determining a respective utility measure for each of the one or more additional queries, wherein the utility measure represents a likelihood that an additional query would be a final query in a series of query refinements from the initial query issued in a query session;

selecting an additional query from the one or more identified additional queries having a highest utility measure among the one or more identified additional queries;

identifying one or more content items for the selected additional query;

generating a content block comprising one or more content items identified for the selected additional query; and

providing the content block to a client device to be displayed along with search results associated with the initial query.

16. A system comprising:

one or more computers; and

a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving an initial query;

selecting one or more additional queries relating to the initial query;

determining a respective utility measure for each of the one or more additional queries, wherein the utility measure represents a likelihood that a respective additional query would be a final query submitted in a query session, wherein the utility measure is determined from a query graph that represents one or more query refinements from the initial query to one of the additional queries, wherein each particular query refinement in the graph has a respective associated weight that represents a likelihood of the particular query refinement being submitted in the query session;

selecting an additional query from the one or more additional queries having a highest utility measure; and

providing the selected additional query to a client device to be displayed along with search results associated with the initial query.

17. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving an initial query;

identifying one or more additional queries related to the initial query;

determining a respective utility measure for each of the one or more additional queries, wherein the utility measure represents a likelihood that an additional query would be a final query in a series of query refinements from the initial query issued in a query session;

selecting an additional query from the one or more identified additional queries having a highest utility measure among the one or more identified additional queries;

identifying one or more content items for the selected additional query;

generating a content block comprising one or more content items identified for the selected additional query; and

providing the content block to a client device to be displayed along with search results associated with the initial query.

18. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving an initial query;

selecting one or more additional queries relating to the initial query;

determining a respective utility measure for each of the one or more additional queries, wherein the utility measure represents a likelihood that a respective additional query would be a final query submitted in a query session, wherein the utility measure is determined from a query graph that represents one or more query refinements from the initial query to one of the additional queries, wherein each particular query refinement in the graph has a respective associated weight that represents a likelihood of the particular query refinement being submitted in the query session;

selecting an additional query from the one or more additional queries having a highest utility measure; and

providing the selected additional query to a client device to be displayed along with search results associated with the initial query.