Method and system for autocompletion using ranked results

• US 9,081,851 B2
• Filed: 12/29/2008
• Issued: 07/14/2015
• Est. Priority Date: 06/22/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gibbs, Kevin A., Kamvar, Sepandar D., Haveliwala, Taher H., Jeh, Glen M.
• Primary Examiner(s): Pulliam, Christyann
• Assistant Examiner(s): ADAMS, CHARLES D
• Application Number:
  US12/345,564
• Publication Number:
  US 20090119289A1
• Time in Patent Office: 2,388 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A set of ordered predicted completion strings are presented to a user as the user enters text in a text entry box (e.g., a browser or a toolbar). The predicted completion strings can be in the form of URLs or query strings. The ordering may be based on any number of factors (e.g., a query'"'"'s frequency of submission from a community of users). URLs can be ranked based on an importance value of the URL. Privacy is taken into account in a number of ways, such as using a previously submitted query only when more than a certain number of unique requesters have made the query. The sets of ordered predicted completion strings is obtained by matching a fingerprint value of the user'"'"'s entry string to a fingerprint to table map which contains the set of ordered predicted completion strings.

Claims

1. A computer-implemented method for processing query information, comprising:

at a server system having one or more processors and memory storing one or more programs for execution by the one or more processors;

receiving a partial search query from a search requester at a client system, the receiving including receiving the partial search query from the client system prior to receiving from the client system a search request on a complete search query that includes the partial search query;

obtaining and conveying to the client system a first set of historical complete search queries previously submitted by a community of users in accordance with a first set of criteria, the first set of historical complete search queries corresponding to the partial search query and ordered in accordance with a ranking criteria; and

obtaining and conveying to the client system a second set of historical complete search queries in accordance with a second set of criteria distinct from the first set of criteria, the second set of criteria including information associated with the search requester, the second set of historical complete search queries corresponding to the partial search query.

2. The method of claim 1, wherein obtaining the first set of historical complete search queries includes ordering the first set of historical complete search queries in accordance with time/date values of the complete search queries.

3. The method of claim 1, wherein obtaining the first set of historical complete search queries includes ordering in accordance with frequency of submission values associated with the first set of historical complete search queries, each of the frequency of submission values corresponding to frequency of submission of a respective complete search query by the community of users.

4. The method of claim 1, further comprising:

at the server system;

determining that no selection corresponding to a search query in the first set of historical ordered complete search queries has been received from the client system within a predetermined time period; and

in response to the determining, conveying to the client system the second set of historical complete search queries.

5. The method of claim 1, wherein obtaining the second set of historical complete search queries includes excluding from the second set of historical complete search queries any queries from the first set of historical complete search queries.

6. The method of claim 1, further comprising:

receiving a search requester initiated trigger indicating a request for a subsequent set of historical complete search queries; and

in response to the trigger, conveying to the client system the second set of historical complete search queries.

7. The method of claim 1, wherein obtaining the second set of historical complete search queries includes reordering the second set of historical complete search queries based on characteristics associated with the search requestor.

8. The method of claim 1, further including,

at the server system:

receiving from the client system a selection of a search query from a respective set of complete search queries comprising at least one of the first and second sets of historical complete search queries conveyed to the client system; and

responding to receiving the selection, by sending the client system a list of search results that satisfy the selected search query.

9. The method of claim 1, further including,

at the server system:

identifying two or more sets of historical complete search queries corresponding to the partial search query; and

merging the sets of historical complete search queries in an interleaved fashion.

10. A non-transitory computer readable storage medium storing one or more programs for execution by one or more processors in a server system, the one or more programs including instructions that, when executed, cause the server system:

to receive a partial search query from a search requester at a client system, wherein the partial search query is received prior to receiving from the client system a search request on a complete search query that includes the partial search query;

to obtain and convey to the client system a first set of historical complete search queries previously submitted by a community of users in accordance with a first set of criteria, the first set of historical complete search queries corresponding to the partial search query and ordered in accordance with a ranking criteria; and

to obtain and convey to the client system a second set of historical complete search queries in accordance with a second set of criteria distinct from the first set of criteria, the second set of criteria including information associated with the search requester, the second set of historical complete search queries corresponding to the partial search query.

11. The computer readable storage medium of claim 10, wherein the instructions to obtain the first set of historical complete search queries include instructions, which when executed, cause the server system to order the first set of historical complete search queries in accordance with time/date values of the complete search queries.

12. The computer readable storage medium of claim 10, wherein the instructions to obtain the first set of historical complete search queries include instructions, which when executed, cause the server system to obtain the first set of historical complete search queries ordered in accordance with frequency of submission values associated with the first set of historical complete search queries, each of the frequency of submission values corresponding to frequency of submission of a respective complete search query by the community of users.

13. The computer readable storage medium of claim 10, the one or more programs further comprising instructions, which when executed, cause the server system:

to determine that no selection corresponding to a search query in the first set of historical ordered complete search queries has been received from the client system within a predetermined time period; and

in response to the determination, to convey to the client system the second set of historical complete search queries.

14. The computer readable storage medium of claim 10, wherein the instructions to obtain the second set of historical complete search queries include instructions, which when executed, cause the server system to exclude from the second set of historical complete search queries any queries from the first set of historical complete search queries.

15. The computer readable storage medium of claim 10, the one or more programs further comprising instructions, which when executed, cause the server system to convey to the client system the second set of historical complete search queries in response a search requester initiated trigger indicating a request for a subsequent set of historical complete search queries.

16. The computer readable storage medium of claim 10, wherein the instructions to obtain the second set of historical complete search queries include instructions, which when executed, cause the server system to reorder the second set of historical complete search queries based on characteristics associated with the search requestor.

17. The computer readable storage medium of claim 10, wherein the one or more programs include instructions, which when executed, cause the server system:

to receive from the client system a selection of a search query from a respective set of complete search queries comprising at least one of the first and second sets of historical complete search queries conveyed to the client system; and

to respond to receiving the selection, by sending to the client system a list of search results that satisfy the selected search query.

18. The computer readable storage medium of claim 10, further comprising instructions, which when executed, cause the server system:

to identify two or more sets of historical complete search queries corresponding to the partial search query; and

to merge the sets of historical complete search queries in an interleaved fashion.

19. A server system for processing query information, comprising:

one or more processors for executing programs; and

memory to store data and to store programs to be executed by the one or more processors, the memory storing;

a plurality of historical complete queries previously submitted by a community of users;

instructions to receive, during operation of the server system, a partial search query from a search requester at a client system prior to receiving from the client system a search request on a complete search query that includes the partial search query;

instructions to obtain and convey to the client system a first set of historical complete search queries previously submitted by a community of users from the plurality of historical complete queries, the first set of historical complete search queries corresponding to the partial search query obtained in accordance with a first set of criteria and ordered in accordance with a ranking criteria; and

instructions to obtain and convey to the client system a second set of historical complete search queries in accordance with a second set of criteria distinct from the first set of criteria, the second set of criteria including information associated with the search requester, the second set of historical complete search queries corresponding to the partial search query.

20. The server system of claim 19, wherein the instructions to obtain the first set of historical complete search queries include instructions, which when executed, cause the server system to order the first set of historical complete search queries in accordance with time/date values of the complete search queries.

21. The server system of claim 19, wherein the instructions to obtain the first set of historical complete search queries include instructions, which when executed, cause the server system to obtain the first set of historical complete search queries ordered in accordance with frequency of submission values associated with the first set of historical complete search queries, each of the frequency of submission values corresponding to frequency of submission of a respective complete search query by the community of users.

22. The server system of claim 19, further comprising instructions, which when executed, cause the server system:

to determine that no selection corresponding to a search query in the first set of historical ordered complete search queries has been received from the client system within a predetermined time period; and

in response to the determination, to convey to the client system the second set of historical complete search queries.

23. The server system of claim 19, wherein the instructions to obtain the second set of historical complete search queries include instructions, which when executed, cause the server system to exclude from the second set of historical complete search queries any queries from the first set of historical complete search queries.

24. The server system of claim 19, further comprising instructions, which when executed, cause the server system to convey to the client system the second set of historical complete search queries in response a search requester initiated trigger indicating a request for a subsequent set of historical complete search queries.

25. The server system of claim 19, wherein the instructions to obtain the second set of historical complete search queries include instructions, which when executed, cause the server system to reorder the second set of historical complete search queries based on characteristics associated with the search requestor.

26. The server system of claim 19, wherein the programs include instructions, which when executed, cause the server system:

to receive from the client system a selection of a search query from a respective set of complete search queries comprising at least one of the first and second sets of historical complete search queries conveyed to the client system; and

to respond to receiving the selection, by sending to the client system a list of search results that satisfy the selected search query.

27. The server system of claim 19, the programs further comprising instructions, which when executed, cause the server system:

to identify two or more sets of historical complete search queries corresponding to the partial search query; and

to merge the sets of historical complete search queries in an interleaved fashion.