Providing query suggestions

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.