Providing query suggestions

• US 9,275,147 B2
• Filed: 06/18/2012
• Issued: 03/01/2016
• Est. Priority Date: 06/18/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Meschkat, Steffen
• Primary Examiner(s): Le, Miranda
• Application Number:
  US13/525,524
• Publication Number:
  US 20130339380A1
• Time in Patent Office: 1,352 Days
• Field of Search: 707/724, 707/730, 707/767
• US Class Current: 1/1
• 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

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for providing query suggestions. In one aspect, a method includes receiving a search string from a user device. A measure of query completeness is determined for the search string. The measure of query completeness is compared to a threshold measure of query completeness. One or more specific query suggestions are provided to the user device, selected from a plurality of specific query suggestions for the search string, when the measure of query completeness exceeds the threshold measure of query completeness; or one or more general query suggestions are provided to the user device, selected from a plurality of general query suggestions for the search string, when the measure of query completeness does not exceed the threshold measure of query completeness.

Claims

1. A method performed by one or more computers, the method comprising:

receiving a search string from a user device;

selecting a plurality of candidate query suggestions based on the search string;

determining, for each candidate query suggestion, a probability for the candidate query suggestion based on a count in a query log of the number of times that the plurality of candidate query suggestions were submitted as search queries and a count in the query log of the number of times that the candidate query was submitted as a search query;

determining a measure of query completeness for the search string based on an aggregation of the determined probabilities, including determining a probability of receiving the N most probable query suggestions for the search string, wherein N is an integer greater than zero;

comparing the measure of query completeness to a threshold measure of query completeness; and

providing one or more specific query suggestions to the user device, selected from a plurality of specific query suggestions for the search string, when the measure of query completeness exceeds the threshold measure of query completeness;

or

providing one or more general query suggestions to the user device, selected from a plurality of general query suggestions for the search string, when the measure of query completeness does not exceed the threshold measure of query completeness.

2. The method of claim 1, wherein providing the one or more selected specific query suggestions or the one or more selected general query suggestions is performed prior to receiving a command from the user device to perform a search using the search string as a query.

3. The method of claim 1, wherein determining the probability of receiving a first one of the N most probable query suggestion includes:

determining, from the query log, a count of the number of times the plurality of candidate query suggestions were received and a count of the number of times the first one of the N most probable query suggestions was received; and

dividing the count of the number of times the first one of the N most probable query suggestions were received by the count of the number of times the plurality of candidate query suggestions were received.

4. The method of claim 1, wherein comparing the measure of query completeness to the threshold measure of query completeness includes comparing the probability of the user selecting the N most probable query suggestions to a threshold probability.

5. The method of claim 1, wherein determining the measure of query completeness for the search string includes:

determining, for each candidate query suggestion, a product of the probability of the candidate query suggestion multiplied by a logarithm of the probability of the candidate query suggestion; and

summing the determined products of the candidate query suggestions.

6. The method of claim 1, wherein selecting the plurality of candidate query suggestions includes selecting the N most probable query suggestions, wherein N is an integer greater than zero.

7. The method of claim 1, wherein comparing the measure of query completeness to a threshold measure of query completeness comprises comparing an entropy of the probabilities to a threshold sum.

8. The method of claim 1, wherein each specific query suggestion is stored in a query suggestion repository, and wherein the query suggestion repository includes information matching each specific query suggestion to a respective general category, each general category having an associated general query suggestion.

9. The method of claim 8, wherein providing one or more general query suggestions further comprises:

determining one or more specific query suggestions;

determining, from the one or more specific query suggestions, one or more general categories; and

determining, from the one or more general categories, one or more general query suggestions.

10. The method of claim 1, further comprising:

providing instructions to the user device that, when executed by the user device, cause the user device to display a user interface for a mapping application, the user interface including a user interface element for receiving queries from a user and a displayed map;

receiving an indication from the user device that a user has selected a query suggestions; and

providing instructions to the user device to update the displayed map based on the selected query suggestion.

11. The method of claim 10, wherein the general query suggestions are category labels and the specific query suggestions are geographic locations, and wherein the general query suggestions are stored in a query repository including data matching each general query suggestion with one or more specific query suggestions.

12. A system of one or more computers configured to perform operations comprising:

receiving a search string from a user device;

selecting a plurality of candidate query suggestions based on the search string;

determining, for each candidate query suggestion, a probability for the candidate query suggestion based on a count in a query log of the number of times that the plurality of candidate query suggestions were submitted as search queries and a count in the query log of the number of times that the candidate query was submitted as a search query;

determining, by one or more processors, a measure of query completeness for the search string based on an aggregation of the determined probabilities, including determining a probability of receiving the N most probable query suggestions for the search string, wherein N is an integer greater than zero;

comparing the measure of query completeness to a threshold measure of query completeness; and

providing one or more specific query suggestions to the user device, selected from a plurality of specific query suggestions for the search string, when the measure of query completeness exceeds the threshold measure of query completeness;

or

providing one or more general query suggestions to the user device, selected from a plurality of general query suggestions for the search string, when the measure of query completeness does not exceed the threshold measure of query completeness.

13. The system of claim 12, wherein providing the one or more selected specific query suggestions or the one or more selected general query suggestions is performed prior to receiving a command from the user device to perform a search using the search string as a query.

14. The system of claim 12, wherein determining the probability of receiving a first one of the N most probable query suggestion includes:

determining, from the query log, a count of the number of times the plurality of candidate query suggestions were received and a count of the number of times the first one of the N most probable query suggestions was received; and

dividing the count of the number of times the first one of the N most probable query suggestions were received by the count of the number of times the plurality of candidate query suggestions were received.

15. The system of claim 12, wherein comparing the measure of query completeness to the threshold measure of query completeness includes comparing the probability of the user selecting the N most probable query suggestions to a threshold probability.

16. The system of claim 12, wherein determining the measure of query completeness for the search string includes:

determining, for each candidate query suggestion, a product of the probability of the candidate query suggestion multiplied by a logarithm of the probability of the candidate query suggestion; and

summing the determined products of the candidate query suggestions.

17. The system of claim 12, wherein selecting the plurality of candidate query suggestions includes selecting the N most probable query suggestions, wherein N is an integer greater than zero.

18. The system of claim 12, wherein comparing the measure of query completeness to a threshold measure of query completeness comprises comparing an entropy of the probabilities to a threshold sum.

19. The system of claim 12, wherein each specific query suggestion is stored in a query suggestion repository, and wherein the query suggestion repository includes information matching each specific query suggestion to a respective general category, each general category having an associated general query suggestion.

20. The system of claim 19, wherein providing one or more general query suggestions further comprises:

determining one or more specific query suggestions;

determining, from the one or more specific query suggestions, one or more general categories; and

determining, from the one or more general categories, one or more general query suggestions.

21. The system of claim 12, the operations further comprising:

providing instructions to the user device that, when executed by the user device, cause the user device to display a user interface for a mapping application, the user interface including a user interface element for receiving queries from a user and a displayed map;

receiving an indication from the user device that a user has selected a query suggestions; and

providing instructions to the user device to update the displayed map based on the selected query suggestion.

22. The system of claim 21, wherein the general query suggestions are category labels and the specific query suggestions are geographic locations, and wherein the general query suggestions are stored in a query repository including data matching each general query suggestion with one or more specific query suggestions.

23. 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 a search string from a user device;

selecting a plurality of candidate query suggestions based on the search string;

determining, for each candidate query suggestion, a probability for the candidate query suggestion based on a count in a query log of the number of times that the plurality of candidate query suggestions were submitted as search queries and a count in the query log of the number of times that the candidate query was submitted as a search query;

determining a measure of query completeness for the search string based on an aggregation of the determined probabilities, including determining a probability of receiving the N most probable query suggestions for the search string, wherein N is an integer greater than zero;

comparing the measure of query completeness to a threshold measure of query completeness; and

providing one or more specific query suggestions to the user device, selected from a plurality of specific query suggestions for the search string, when the measure of query completeness exceeds the threshold measure of query completeness;

or

providing one or more general query suggestions to the user device, selected from a plurality of general query suggestions for the search string, when the measure of query completeness does not exceed the threshold measure of query completeness.