Predictive query suggestion caching

• US 8,560,562 B2
• Filed: 07/22/2010
• Issued: 10/15/2013
• Est. Priority Date: 07/22/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kanefsky, Steven T.
• Primary Examiner(s): TIMBLIN, ROBERT M
• Application Number:
  US12/841,571
• Publication Number:
  US 20120023120A1
• Time in Patent Office: 1,181 Days
• Field of Search: 707705-707, 707/721, 707/759, 707/765, 707766-769, 707999001-999003
• US Class Current: 707/767
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• 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/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Methods, systems, an apparatus, and computer program products, for pre-caching query suggestions. In one aspect, a method includes receiving from a client device a request for a search resource; providing to the client device in response to the request the search resource, the search resource including: first instructions that cause the client device to generate a search interface that includes a first query input field; initial query suggestions; second instructions that cause the client device to: store the initial query suggestions in a suggestion store on the client device; compare query characters input in the first query input field to the query suggestions stored in the suggestion store; select query suggestions that match the query characters input in the first query input field based on the comparison; and display the selected query suggestions as query suggestions for the query characters input into the first query input field.

Claims

1. A system, comprising:

a data processing apparatus; and

a memory storage apparatus in data communication with the data processing apparatus, the memory storage apparatus storing server instructions that when executed by the data processing apparatus cause the data processing apparatus to perform operations comprising;

receiving from a client device a request for a search resource;

providing to the client device in response to the request the search resource, the search resource including;

first instructions that cause the client device to generate a search interface that includes a first query input field;

initial query suggestions, wherein each initial query suggestion is determined from data separate from content of the search resource and, upon user selection from the search interface, is processed by a search service as a query, and wherein the initial query suggestions are provided to the client device with the search resource without an additional request for the initial query suggestions from the client device separate from the request;

second instructions that cause the client device to;

store the initial query suggestions in a suggestion store on the client device;

compare query characters input in the first query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the first query input field based on the comparison; and

display the selected query suggestions as query suggestions for the query characters input into the first query input field.

2. The system of claim 1, wherein:

the second instructions cause the client device to;

provide the query characters input in the first query input field to the data processing apparatus as a query suggestion request;

receive, in response to the request, additional query suggestions from the data processing apparatus; and

store the additional query suggestions in the suggestion store; and

the server instructions cause the data processing apparatus to provide the additional query suggestions to the client device in response to the query suggestion request.

3. The system of claim 2, wherein the second instructions cause the client device to provide a separate query suggestion request for each entry of a query character into the query input field.

4. The system of claim 1, wherein:

the server instructions further cause the data processing apparatus to provide a search results resource in response to the query received from the client device, the search results resource including;

third instructions that cause the client device to generate a search results page that displays search results referencing resources determined to be responsive to the query;

additional query suggestions; and

fourth instructions that cause the client device to store the additional query suggestions in the suggestion store on the client device.

5. The system of claim 4, wherein:

the search results page includes a second query input field; and

the fourth instructions cause the client device to;

compare query characters input in the second query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the second query input field based on the comparison; and

display the selected query suggestions as query suggestions for the query characters input into the second query input field.

6. The system of claim 1, wherein the server instructions, when executed by the data processing apparatus, further cause the data processing apparatus to perform operations comprising:

accessing query log data that includes queries submitted by users and the frequency with which each query was submitted;

determining most likely sequences of initial query characters from the query log data;

for each most likely sequence, determining most likely queries from the most likely sequence and the query log data, each most likely query having an initial sequence of query characters matching the most likely sequence of initial query characters; and

designating the most likely queries determined for each of the most likely sequences of initial query characters as the initial query suggestions.

7. The system of claim 6, wherein:

the second instructions cause the client device to;

provide the query characters input in the first query input field to the data processing apparatus as a query suggestion request;

receive, in response to the request, additional query suggestions from the data processing apparatus; and

store the additional query suggestions in the suggestion store;

the server instructions cause the data processing apparatus to;

receive the query characters from the client device;

determine most likely sequences of subsequent query characters from the query log data, the subsequent query characters being query characters that are subsequent in sequence to the query characters received from the client device;

for each most likely sequence of subsequent query characters, determining most likely additional queries from the most likely sequence of subsequent query characters and the query log data, each most likely query having an initial sequence of query characters matching the query characters received from the client device and the most likely sequence of subsequent query characters;

designating the most likely additional queries determined for each of the most likely sequences of subsequent query characters as the additional query suggestions; and

providing the additional query suggestions to the client device in response to the query suggestion request.

8. The system of claim 1, wherein:

the request for the search resource includes location data identifying the current location of the client device;

the initial query suggestions include location specific query suggestions that are specific to the current location of the client device; and

selecting query suggestions that match the query characters input in the first query input field based on the comparison further comprises excluding location specific query suggestions that are not specific to the current location of the client device.

9. The system of claim 1, wherein the initial query suggestions are based on previous queries submitted to the search service by one or more users of the search service.

10. A system, comprising:

a data processing apparatus; and

a memory storage apparatus in data communication with the data processing apparatus, the memory storage apparatus storing server instructions that when executed by the data processing apparatus cause the data processing apparatus to perform operations comprising;

accessing query log data that includes queries submitted by users and the frequency with which each query was submitted;

determining most likely sequences of initial query characters from the query log data;

for each most likely sequence, determine most likely queries from the most likely sequence and the query log data, each most likely query having an initial sequence of query characters matching the most likely sequence of initial query characters;

designate the most likely queries determined for each of the most likely sequences of initial query characters as initial query suggestions;

receive from a client device a request for a search resource;

provide to the client device in response to the request the search resource, the search resource including;

first instructions that cause the client device to generate a search interface that includes a first query input field;

the initial query suggestions;

second instructions that cause the client device to;

store the initial query suggestions in a suggestion store on the client device;

compare query characters input in the first query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the first query input field based on the comparison;

display the selected query suggestions as query suggestions for the query characters input into the first query input field;

provide the query characters input in the first query input field to the data processing apparatus as a query suggestion request;

wherein the server instructions further cause the data processing apparatus to;

receive the query characters from the client device;

determining most likely sequences of subsequent query characters from the query log data, the subsequent query characters being query characters that are subsequent in sequence to the query characters received from the client device;

for each most likely sequence of subsequent query characters, determine most likely additional queries from the most likely sequence of subsequent query characters and the query log data, each most likely query having an initial sequence of query characters matching the query characters received from the client device and the most likely sequence of subsequent query characters;

designate the most likely additional queries determined for each of the most likely sequences of subsequent query characters as additional query suggestions; and

provide the additional query suggestions to the client device in response to the query suggestion request;

wherein the second instructions cause the client device to;

receive, in response to the request, the additional query suggestions from the data processing apparatus; and

store the additional query suggestions in the suggestion store; and

wherein;

the server instructions cause the data processing apparatus to;

provide the initial query suggestions and additional query suggestions in the form of key value pairs, the key value pairs being pairs of query input sequences and query suggestions having initial query characters that match the query input sequences; and

the second instructions cause the client device to;

provide the query characters input in the first query input field to the data processing apparatus as a query suggestion request only in response to determining that the query characters input in the first query input field do not match any of the query input sequences of the key value pairs.

11. A client device, comprising:

a processing system;

a memory storage apparatus in data communication with the processing system, the memory storage apparatus storing browser instructions that when executed by the processing system cause the client device to perform operations comprising;

providing a request for a search resource from a search service;

receiving the search resource in response to the request the search resource, the search resource including;

first instructions that cause the client device to generate a search interface that includes a first query input field;

initial query suggestions, wherein each initial query suggestion is determined from data separate from content of the search resource and, upon user selection from the search interface, is processed by the search service as a query, and wherein the initial query suggestions are received with the search resource without an additional request for the initial query suggestions to the search service separate from the request; and

second instructions that cause the client device to;

store the initial query suggestions in a suggestion store on the client device;

compare query characters input in the first query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the first query input field based on the comparison; and

display the selected query suggestions as query suggestions for the query characters input into the first query input field.

12. The client device of claim 11, wherein:

the second instructions cause the client device to;

provide the query characters input in the first query input field to the search service as a query suggestion request;

receive, in response to the request, additional query suggestions from the search service; and

store the additional query suggestions in the suggestion store.

13. The client device of claim 12, wherein the second instructions cause the client device to provide a separate query suggestion request for each entry of a query character into the query input field.

14. The client device of claim 12, wherein:

the client device receives a search results resource in response to a query received from the client device, the search results resource including;

third instructions that cause the client device to generate a search results page that displays search results referencing resources determined to be responsive to the query;

additional query suggestions; and

fourth instructions that cause the client device to store the additional query suggestions in the suggestion store on the client device.

15. The client device of claim 14, wherein:

the search results page includes a second query input field; and

the fourth instructions cause the client device to;

compare query characters input in the second query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the second query input field based on the comparison; and

display the selected query suggestions as query suggestions for the query characters input into the second query input field.

16. The client device of claim 15, wherein:

the initial query suggestions and the additional query suggestions are provided in the form of key value pairs, the key value pairs being pairs of query input sequences and query suggestions having initial query characters that match the query input sequences; and

the second instructions and the fourth instructions cause the client device to provide the query characters input in the first query input field and second query input field, respectively, to search service as a query suggestion request only in response to determining that the query characters input in the first query input field or the second query input field, respectively, do not match any of the query input sequences of the key value pairs.

17. The client device of claim 16, wherein:

the request for the search resource includes location data identifying the current location of the client device;

the initial query suggestions include location specific query suggestions that are specific to the current location of the client device; and

selecting query suggestions that match the query characters input in the first query input field based on the comparison further comprises excluding location specific query suggestions that are not specific to the current location of the client device.

18. A computer-implemented method performed by a data processing apparatus, comprising:

receiving from a client device a request for a search resource; and

providing to the client device in response to the request for the search resource, the search resource including;

first instructions that cause the client device to generate a search interface that includes a first query input field;

initial query suggestions, wherein each initial query suggestion is determined from data separate from content of the search resource and, upon user selection from the search interface, is processed by a search service as a query, and wherein the initial query suggestions are provided to the client device with the search resource without an additional request for the initial query suggestions from the client device separate from the request; and

second instructions that cause the client device to;

store the initial query suggestions in a suggestion store on the client device;

compare query characters input in the first query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the first query input field based on the comparison; and

display the selected query suggestions as query suggestions for the query characters input into the first query input field.

19. The method of claim 18, further comprising:

accessing query log data that includes queries submitted by users and the frequency with which each query was submitted;

determining most likely sequences of initial query characters from the query log data;

for each most likely sequence, determining most likely queries from the most likely sequence and the query log data, each most likely query having an initial sequence of query characters matching the most likely sequence of initial query characters; and

designating the most likely queries determined for each of the most likely sequences of initial query characters as the initial query characters.

20. The method of claim 19, further comprising:

receiving query characters input into the first query input field from the client device;

determining most likely sequences of subsequent query characters from the query log data, the subsequent query characters being query characters that are subsequent in sequence to the query characters received from the client device;

for each most likely sequence of subsequent query characters, determining most likely additional queries from the most likely sequence of subsequent query characters and the query log data, each most likely query having an initial sequence of query characters matching the query characters received from the client device and the most likely sequence of subsequent query characters; and

designating the most likely additional queries determined for each of the most likely sequences of subsequent query characters as additional query suggestions; and

providing the additional query suggestions to the client device.

21. The method of claim 20, wherein:

the initial query suggestions and additional query suggestions are in the form of key value pairs, the key value pairs being pairs of query input sequences and query suggestions having initial query characters that match the query input sequences; and

the query characters input in the first query input field or second input field are provided as a query suggestion request only in response to determining that the query characters input in the first query input field or the second input field do not match any of the query input sequences of the key value pairs.

22. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving from a client device a request for a search resource; and

providing to the client device in response to the request the search resource, the search resource including;

first instructions that cause the client device to generate a search interface that includes a first query input field;

initial query suggestions, wherein each initial query suggestion is determined from data separate from content of the search resource and, upon user selection from the search interface, is processed by a search service as a query, and wherein the initial query suggestions are provided to the client device with the search resource without an additional request for the initial query suggestions from the client device separate from the request; and

second instructions that cause the client device to;

store the initial query suggestions in a suggestion store on the client device;

compare query characters input in the first query input field to the query suggestions stored in the suggestion store;

select query suggestions that match the query characters input in the first query input field based on the comparison; and

display the selected query suggestions as query suggestions for the query characters input into the first query input field.