Query suggestions with high utility

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.

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.

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.

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.

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.