Dynamically selecting and presenting content relevant to user input

• US 8,504,437 B1
• Filed: 11/04/2010
• Issued: 08/06/2013
• Est. Priority Date: 11/04/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Agarwal, Ashish, Baratloo, Arash, Raghunathan, Vivek, Ma, Qicheng, So, Chiu Wah Kelvin
• Primary Examiner(s): Choi, Peter
• Assistant Examiner(s): PALAVECINO, KATHLEEN GAGE
• Application Number:
  US12/939,983
• Time in Patent Office: 1,006 Days
• Field of Search: 705 261- 272, 705 144- 1449
• US Class Current: 705/26.3
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/08 Auctions

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media are provided. One example method includes receiving a textual input that forms a part of a user request, the textual input in the form of a prefix that when complete constitutes the request. The method further includes identifying completions based on the prefix, determining one or more content items associated with each completion, computing initial scores including a score for each content item-completion pair including determining a likelihood that a given completion represents the request and a quality of the content item as compared to the completion, computing final scores including scores for each prefix-content item pair using the initial scores, computing a bid for each content item, running an auction to select a content item based on the bids and final scores, and identifying display data associated with the selected content item.

Claims

1. A computer-implemented method comprising:

receiving a textual input that forms a part of a request by a user, the textual input in the form of a prefix that is included in the request;

identifying completions based on the prefix;

for each completion, determining an advertisement-completion pair including the completion and an advertisement matched to the completion;

for each advertisement-completion pair, computing a final score, by one or more data processors based at least in part on a likelihood that the completion of the pair represents the request and a quality measure of the advertisement of the pair matches the completion of the pair;

for each advertisement-completion pair, determining a bid for the advertisement of the advertisement-completion pair;

running an auction to select an advertisement from the advertisement-completion pairs based on the bids and final scores; and

identifying display data associated with the selected advertisement.

2. The method of claim 1, further comprising determining if the prefix is sufficient, and if not waiting for more textual input prior to identifying display data.

3. The method of claim 2, wherein determining if the prefix is sufficient includes determining completions and a likelihood of completion for each completion, and determining that the highest likelihood is less than a predetermined threshold.

4. The method of claim 1, wherein determining advertisement-completion pairs includes identifying advertisements stored in a cache associated with each completion.

5. The method of claim 1, wherein computing a final score for the advertisement-completion pair includes determining that the advertisement of the pair matches multiple completions different from the completion of the pair, and determining the final score for the advertisement-completion pair based on an aggregation of scores for the advertisement matching the multiple completions.

6. The method of claim 1, wherein determining the final scores includes filtering final scores based on one or more criteria.

7. The method of claim 6, wherein filtering final scores includes reducing final scores.

8. The method of claim 6, wherein filtering final scores results in disabling selection of an advertisement.

9. The method of claim 6, wherein filtering final scores includes promoting final scores based at least in part on one or more criteria.

10. The method of claim 1, further comprising determining whether a particular selected advertisement satisfies one or more additional selection criteria, and not identifying display data in response to a determination that the particular selected advertisement does not satisfy the additional selection criteria.

11. The method of claim 1, comprising determining, for each of the advertisement-completion pairs, whether the likelihood that a completion in the advertisement-completion pair represents the request exceeds a threshold, and in response to determining that none of the determined likelihoods exceed the threshold, waiting for more textual input.

12. The method of claim 1, comprising determining whether the prefix is ambiguous, and in response to determining that the prefix is ambiguous, waiting for more textual input.

13. The method of claim 1, comprising providing the display data to a user device for display to the user.

14. The method of claim 1, wherein determining the advertisement-completion pair comprises determining one or more advertisements matched to the completion of the pair, an age of each of the one or more advertisements and discarding each of the one or more advertisements that have an age that exceeds an age threshold.

15. A non-transitory computer-readable storage medium having instructions stored thereon, which, when executed by one or more data processors, cause the one or more data processors to:

receive a textual input that forms a part of a request by a user, the textual input in the form of a prefix that is included in the request;

identify completions based on the prefix;

for each completion, determine an advertisement-completion pair including the completion and an advertisement matched to the completion;

for each advertisement-completion pair, compute a final score based at least in part on a likelihood that the completion of the pair represents the request and a quality measure of the advertisement of the pair matches the completion of the pair;

for each advertisement-completion pair, determining a bid for the advertisement of the advertisement-completion pair;

run an auction to select an advertisement from the advertisement-completion pairs based on the bids and final scores; and

identify display data associated with the selected advertisement.

16. The computer-readable storage medium of claim 15, wherein computing a final score for the advertisement-completion pair includes determining that the advertisement of the pair matches multiple completions different from the completion of the pair, and determining the final score for the advertisement-completion pair based on an aggregation of scores for the advertisement matching the multiple completions.

17. An apparatus comprising:

means for receiving a textual input that forms a part of a request by a user, the textual input in the form of a prefix that is included in the request;

means for identifying completions based on the prefix;

means for determining, for each completion, an advertisement-completion pair including the completion and an advertisement matched to the completion;

means for computing, for each advertisement-completion pair, a final score based at least in part on a likelihood that the completion of the pair represents the request and a quality measure of the advertisement of the pair matches the completion of the pair;

means for determining, for each advertisement-completion pair, a bid for the advertisement of the advertisement-completion pair;

means for running an auction to select an advertisement from the advertisement-completion pairs based on the bids and final scores; and

means for identifying display data associated with the selected advertisement.

18. The apparatus of claim 17, wherein computing a final score for the advertisement-completion pair includes determining that the advertisement of the pair matches multiple completions different from the completion of the pair, and determining the final score for the advertisement-completion pair based on an aggregation of scores for the advertisement matching the multiple completions.