# US 8,751,520 B1 · Query suggestions with high utility > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,751,520 B1 - Document ID: US8751520B1 - Status: Granted - Kind: B1 - Application number: 12/979,575 - Filed: 2010-12-28 - Granted: 2014-06-10 - Earliest claimed: 2010-06-23 - Assignees: Google Inc. - Applicants: Rajat Bhattacharjee; Aranyak Mehta; Benyu Zhang; Vivek Raghunathan - Inventors: Rajat Bhattacharjee; Aranyak Mehta; Benyu Zhang; Vivek Raghunathan - Web page: https://patentgrep.com/patent/US8751520B1 ## CPC - G06F 16/3322: {using system suggestions (G06F16/3325 takes precedence)} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) The method of claim 1, wherein the initial query includes one or more query terms. ### Claim 3 (depends on 1) The method of claim 1, wherein the additional query includes one or more terms from the initial query. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 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. ### Claim 7 (depends on 6) The method of claim 6, wherein determining a utility measure for an additional query comprises evaluating the query using one or more commerciality criteria. ### Claim 8 (depends on 6) 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 6) The method of claim 6, wherein the initial query includes one or more query terms. ### Claim 11 (depends on 6) The method of claim 6, wherein the additional query includes one or more terms from the initial query and one or more additional terms. ### Claim 12 (depends on 6) The method of claim 6, wherein each additional query includes at least a portion of the initial query. ### Claim 13 (depends on 6) The method of claim 6, wherein the additional queries are contextually relevant to the initial query. ### Claim 14 (depends on 6) The method of claim 6, wherein the additional queries represent queries that users have historically been entered after having entered the initial query. ### Claim 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. ### Claim 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. ### Claim 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. ### Claim 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.