Systems and methods for generating predicted queries and corresponding search results

• US 9,235,637 B1
• Filed: 02/22/2012
• Issued: 01/12/2016
• Est. Priority Date: 06/22/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kamvar, Sepandar D., Haveliwala, Taher H., Jeh, Glen M.
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Le, Michael
• Application Number:
  US13/402,835
• Time in Patent Office: 1,420 Days
• Field of Search: 707/713, 707/999.003
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query

Abstract

A search system monitors the input of a search query by a user. Before the user finishes entering the search query, the search system identifies and sends a portion of the query as a partial query to the search engine. Based on the partial query, the search engine creates a set of predicted queries. This process may take into account prior queries submitted by a community of users, and may take into account a user profile. The predicted queries are to be sent back to the user for possible selection. The search system may also cache search results corresponding to one or more of the predicted queries in anticipation of the user selecting one of the predicted queries. The search engine may also return at least a portion of the search results corresponding to one or more of the predicted queries.

Claims

1. A computer-implemented method performed at a server system for processing a search query, comprising:

receiving at the server system the search query from a search requestor at a client system that is distinct from the server system; and

at the server system, responding to receiving the search query, including;

determining whether the search query is a partial search query or a final search query;

wherein,

when the search query is deemed to be a partial search query;

(A) predicting a plurality of predicted queries based upon the search query;

(B) selecting one or more predicted queries in the plurality of predicted queries based, at least in part, on how recently each of the predicted queries was previously submitted to the server system;

(C) obtaining search results corresponding to the one or more selected predicted queries, prior to receiving a selection of any predicted query in the plurality of predicted queries from the search requester, and

(D) transmitting (i) the one or more selected predicted queries, and (ii) the search results corresponding to the one or more selected predicted queries to the search requestor at the client system;

when the search query is deemed to be a final search query;

determining whether a server system cache includes search results corresponding to the final search query, wherein

when the server system cache includes search results corresponding to the final search query, transmitting to the search requestor at the client system, from the server system, the search results in the document cache that correspond to the final search query, and

when the server system cache does not include search results corresponding to the final search query;

(i) obtaining search results corresponding to the final search query from an inverse document index, and

(ii) transmitting to the search requestor at the client system, from the server system, the search results corresponding to the final search query from the inverse document index,

wherein at least the predicting (A), selecting (B), and obtaining (C) are executed before obtaining, at the server system, an affirmation, by the search requestor, of a request for executing the search query.

2. The method of claim 1 further comprising:

predicting the plurality of predicted queries from a collection of queries previously received from a community of users.

3. The method of claim 1, wherein the search query is deemed to be a partial search query and includes a complete search term.

4. The method of claim 1, wherein the search query is deemed to be a partial search query, the method further comprising:

comparing one or more characters of the search query to entries in a dictionary; and

creating the plurality of predicted queries from one or more of the entries in the dictionary whose entries include the at least one or more characters.

5. The method of claim 4, wherein the plurality of predicted queries is created from entries in the dictionary whose entries begin with the at least one or more characters.

6. The method of claim 4, further comprising:

selecting the dictionary from a plurality of dictionaries.

7. The method of claim 6, further comprising:

selecting the dictionary based on information obtained from a user profile of the search requestor.

8. The method of claim 1, wherein the selecting (B) includes selecting and ordering the predicted queries based, at least in part, on how recently each of the predicted queries was previously submitted to the server system.

9. The method of claim 1, further comprising obtaining search results corresponding to the search query, wherein the search results corresponding to the one or more predicted search queries are independent from the search results corresponding to the search query.

10. A server system, comprising:

one or more hardware processors;

hardware memory; and

one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for;

receiving at the server system a search query from a search requestor at a client system that is distinct from the server system; and

at the server system, responding to receiving the search query, including;

determining whether the search query is a partial search query or a final search query;

wherein,

when the search query is deemed to be a partial search query;

(A) predicting a plurality of predicted queries based upon the search query;

(B) selecting one or more predicted queries in the plurality of predicted queries based, at least in part, on how recently each of the predicted queries was previously submitted to the server system;

(C) obtaining search results corresponding to the one or more selected predicted queries, prior to receiving a selection of any predicted query in the plurality of predicted queries from the search requester and

(D) transmitting (i) the one or more selected predicted queries, and (ii) the search results corresponding to the one or more selected predicted queries to the search requestor at the client system;

when the search query is deemed to be a final search query;

determining whether a server system cache includes search results corresponding to the final search query, wherein

when the server system cache includes search results corresponding to the final search query, transmitting to the search requestor at the client system, from the server system, the search results in the document cache that correspond to the final search query, and

when the server system cache does not include search results corresponding to the final search query;

(i) obtaining search results corresponding to the final search query from an inverse document index, and

(ii) transmitting to the search requestor at the client system, from the server system, the search results corresponding to the final search query from the inverse document index,

wherein at least the predicting (A), selecting (B), and obtaining (C) are executed before obtaining, at the server system, an affirmation, by the search requestor, of a request for executing the search query.

11. The server system of claim 10, the one or more programs further comprising instructions for:

predicting the plurality of predicted queries from a collection of queries previously received from a community of users.

12. The server system of claim 10, wherein the search query includes a complete search term.

13. The server system of claim 10, wherein the search query is deemed to be a partial search query, the one or more programs further comprising instructions for:

comparing one or more characters of the portion of the search query to entries in a dictionary; and

creating the plurality of predicted queries from one or more of the entries in the dictionary whose entries include the at least one or more characters.

14. The server system of claim 13, wherein the plurality of predicted queries is created from entries in the dictionary whose entries begin with the at least one or more characters.

15. The server system of claim 13, the one or more programs further comprising instructions for:

selecting the dictionary from a plurality of dictionaries.

16. The server system of claim 15, the one or more programs further comprising instructions for:

selecting the dictionary based on information obtained from a user profile of the search requestor.

17. The server system of claim 10, wherein the instructions for selecting (B) include instructions for selecting and ordering the predicted queries based, at least in part, on how recently each of the predicted queries was previously submitted to the server system.

18. The server system of claim 10, the one or more programs further comprising instructions for obtaining search results corresponding to the search query, wherein the search results corresponding to the one or more predicted search queries are independent from the search results corresponding to the search query.

19. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions for:

receiving at a server system a search query from a search requestor at a client system that is distinct from the server system; and

at the server system, responding to receiving the search query, including;

determining whether the search query is a partial search query or a final search query;

wherein,

when the search query is deemed to be a partial search query;

(A) predicting a plurality of predicted queries;

(B) selecting one or more predicted queries in the plurality of predicted queries based, at least in part, on how recently each of the predicted queries was previously submitted to the server system;

(C) obtaining search results corresponding to the one or more selected predicted queries, prior to receiving a selection of any predicted query in the plurality of predicted queries from the search requester and

(D) transmitting (i) the one or more selected predicted queries, and (ii) the search results corresponding to the one or more selected predicted queries to the search requestor at the client system;

when the search query is deemed to be a final search query;

determining whether a server system cache includes search results corresponding to the final search query, wherein

when the server system cache includes search results corresponding to the final search query, transmitting to the search requestor at the client system, from the server system, the search results in the document cache that correspond to the final search query, and

when the server system cache does not include search results corresponding to the final search query;

(i) obtaining search results corresponding to the final search query from an inverse document index, and

(ii) transmitting to the search requestor at the client system, from the server system, the search results corresponding to the final search query from the inverse document index,

wherein at least the predicting (A), selecting (B), and obtaining (C) are executed before obtaining, at the server system, an affirmation, by the search requestor, of a request for executing the search query.

20. The non-transitory computer readable storage medium of claim 19, wherein the one or more programs further comprising instructions for:

predicting the plurality of predicted queries from a collection of queries previously received from a community of users.

21. The non-transitory computer readable storage medium of claim 19, wherein the search query is deemed to be a partial search query and includes a complete search term.

22. The non-transitory computer readable storage medium of claim 19 wherein the search query is deemed to be a partial search query, the one or more programs further comprising instructions for:

comparing one or more characters of the search query to entries in a dictionary; and

creating the plurality of predicted queries from one or more of the entries in the dictionary whose entries include the at least one or more characters.

23. The non-transitory computer readable storage medium of claim 22, wherein the plurality of predicted queries is created from entries in the dictionary whose entries begin with the at least one or more characters.

24. The non-transitory computer readable storage medium of claim 22, wherein the one or more programs further comprise instructions for selecting the dictionary from a plurality of dictionaries.

25. The non-transitory computer readable storage medium of claim 24, the one or more programs further comprising instructions for selecting the dictionary based on information obtained from a user profile of the search requestor.

26. The non-transitory computer readable storage medium of claim 19, wherein the selecting (A) includes ordering the predicted queries based, at least in part, on how recently each of the predicted queries was previously submitted to the server system.

27. The non-transitory computer readable storage medium of claim 19, the one or more programs further comprising instructions for obtaining search results corresponding to the search query, wherein the search results corresponding to the one or more predicted search queries are independent from the search results corresponding to the search query.