Query completions

1. A computer-implemented method comprising:

receiving, at a first time, a first query submitted by the user;

receiving, at a second time after the first time, a query prefix input by the user but not yet submitted by the user, wherein the query prefix input includes at least a first character; and

in response to receiving the query prefix input:

performing a search of a database of user activity sessions, to determine one or more likely query completions that start with the first character of the query prefix and that co-occur with the previously submitted first query in one or more of the user activity sessions, wherein the previously submitted first query in one or more of the user activity sessions is a query that was most recently submitted by the user;

determining, for each of the one or more likely query completions, a corresponding ranking score based on a corresponding correlation between occurrences of a corresponding one of the one or more likely query completions and the previously submitted first query in the user activity sessions, wherein determining the corresponding ranking scores based on the corresponding correlation between occurrences of the likely query completions and the previously submitted first query is performed based on determining that the previously submitted first query is the query that was most recently submitted by the user; and

causing at least one of the one or more likely query completions to be rendered to the user based on the corresponding ranking scores.

2. The method of claim 1 , wherein the query prefix input further includes a second character in addition to the first character, and wherein causing one or more of the likely query completions to be rendered to the user based on the corresponding ranking scores comprises:

filtering out any of the at least one of the likely query completions having a second character that does not match the second character of the query prefix input, and

causing any filtered out likely query completion to not be rendered to the user.

3. The method of claim 1 , wherein the query prefix input is a one-character query prefix.

4. The method of claim 1 , wherein the database of user activity sessions include user activity sessions describing activities of different users.

5. The method of claim 1 , wherein causing the at least one of the one or more likely query completions to be rendered to the user based on the corresponding ranking scores comprises:

determining a ranking order for the one or more likely query completions based on the corresponding ranking scores; and

providing, based on the ranking order, the at least one of the one or more likely query completions for display.

6. The method of claim 1 , wherein determining the corresponding ranking scores comprises:

obtaining, from a database comprising a baseline collection of query completions, corresponding initial ranking scores for the corresponding likely query completions; and

modifying the corresponding initial ranking scores for the corresponding likely query completions by multiplying the corresponding initial ranking scores by corresponding ranking factors, the corresponding ranking factors comprising a comparison of:

a likelihood of the corresponding likely query completion occurring in a given activity session given that the previously submitted first query also occurred in the given activity session, and

a likelihood of the corresponding likely query completion occurring in any activity session.

7. The method of claim 1 , further comprising:

before performing the search of the database of user activity sessions based on the previously submitted first query:

performing, based on the previously submitted first query, a search of a cache, wherein performing the search of the database of user activity sessions is performed based on no entry of the cache being identified as responsive to the search of the cache.

8. The method of claim 7 , wherein the cache contains a plurality of entries, each entry comprising:

at least one other additional previously submitted query,

a plurality of corresponding previously determined query completions for the at east one corresponding other additional previously submitted query, and

a query prefix corresponding to the corresponding previously determined query completions of the entry.

9. The method of claim 8 , further comprising:

generating, based on a corresponding likely query completion of the likely query completions, an additional cache entry, the additional cache entry comprising:

(i) the previously submitted first query,

(ii) the corresponding likely query completion, and

(iii) at least one beginning character of the query prefix input,

wherein the generating the additional cache entry is performed based on no entry of the cache being identified as responsive to the search of the cache.

10. A system, comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:

receiving, at a first time, a first query submitted by the user;

receiving, at a second time after the first time, a query prefix input by the user but not yet submitted by the user, wherein the query prefix input includes at least a first character; and

in response to receiving the query prefix input:

performing a search of a database of user activity sessions, to determine one or more likely query completions that start with the first character of the query prefix and that co-occur with the previously submitted first query in one or more of the user activity sessions, wherein the previously submitted first query in one or more of the user activity sessions is a query that was most recently submitted by the user;

determining, for each of the one or more likely query completions, a corresponding ranking score based on a corresponding correlation between occurrences of a corresponding one of the one or more likely query completions and the previously submitted first query in the user activity sessions, wherein determining the corresponding ranking scores based on the corresponding correlation between occurrences of the likely query completions and the previously submitted first query is performed based on determining that the previously submitted first query is the query that was most recently submitted by the user; and

causing at least one of the one or more likely query completions to be rendered to the user based on the corresponding ranking scores.

11. The system of claim 10 , wherein the query prefix input further includes a second character in addition to the first character, and wherein the operation of causing one or more of the likely query completions to be rendered to the user based on the corresponding ranking scores comprises:

filtering out any of the at least one of the likely query completions having a second character that does not match the second character of the query prefix input, and

causing any filtered out likely query completion to not be rendered to the user.

12. The system of claim 10 , wherein the query prefix input is a one-character query prefix.

13. The system of claim 10 , wherein the operation of causing the at least one of the one or more likely query completions to be rendered to the user based on the corresponding ranking scores comprises:

determining a ranking order for the one or more likely query completions based on the corresponding ranking scores; and

providing, based on the ranking order, the at least one of the one or more likely query completions for display.

14. The system of claim 10 , wherein the operation of determining the corresponding ranking scores comprises:

obtaining, from a database comprising a baseline collection of query completions, corresponding initial ranking scores for the corresponding likely query completions; and

modifying the corresponding initial ranking scores for the corresponding likely query completions by multiplying the corresponding initial ranking scores by corresponding ranking factors, the corresponding ranking factors comprising a comparison of:

a likelihood of the corresponding likely query completion occurring in a given activity session given that the previously submitted first query also occurred in the given activity session, and

a likelihood of the corresponding likely query completion occurring in any activity session.

15. The system of claim 10 , further comprising:

before performing the search of the database of user activity sessions based on the previously submitted first query:

performing, based on the previously submitted first query, a search of a cache, wherein performing the search of the database of user activity sessions is performed based on no entry of the cache being identified as responsive to the search of the cache.

16. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving, at a first time, a first query submitted by the user;

receiving, at a second time after the first time, a query prefix input by the user but not yet submitted by the user, wherein the query prefix input includes at least a first character; and

in response to receiving the query prefix input:

performing a search of a database of user activity sessions, to determine one or more likely query completions that start with the first character of the query prefix and that co-occur with the previously submitted first query in one or more of the user activity sessions, wherein the previously submitted first query in one or more of the user activity sessions is a query that was most recently submitted by the user;

determining, for each of the one or more likely query completions, a corresponding ranking score based on a corresponding correlation between occurrences of a corresponding one of the one or more likely query completions and the previously submitted first query in the user activity sessions, wherein determining the corresponding ranking scores based on the corresponding correlation between occurrences of the likely query completions and the previously submitted first query is performed based on determining that the previously submitted first query is the query that was most recently submitted by the user; and

causing at least one of the one or more likely query completions to be rendered to the user based on the corresponding ranking scores.

17. The system of claim 16 , wherein the query prefix input further includes a second character in addition to the first character, and wherein the operation of causing one or more of the likely query completions to be rendered to the user based on the corresponding ranking scores comprises:

filtering out any of the at least one of the likely query completions having a second character that does not match the second character of the query prefix input, and

causing any filtered out likely query completion to not be rendered to the user.

18. The system of claim 16 , wherein the query prefix input is a one-character query prefix.

19. The system of claim 16 , wherein the operation of causing the at least one of the one or more likely query completions to be rendered to the user based on the corresponding ranking scores comprises:

determining a ranking order for the one or more likely query completions based on the corresponding ranking scores; and

providing, based on the ranking order, the at least one of the one or more likely query completions for display.

20. The system of claim 16 , wherein the operation of determining the corresponding ranking scores comprises:

obtaining, from a database comprising a baseline collection of query completions, corresponding initial ranking scores for the corresponding likely query completions; and

modifying the corresponding initial ranking scores for the corresponding likely query completions by multiplying the corresponding initial ranking scores by corresponding ranking factors, the corresponding ranking factors comprising a comparison of:

a likelihood of the corresponding likely query completion occurring in a given activity session given that the previously submitted first query also occurred in the given activity session, and

a likelihood of the corresponding likely query completion occurring in any activity session.