Method and System for Autocompletion Using Ranked Results

• US 20090119289A1
• Filed: 12/29/2008
• Published: 05/07/2009
• Est. Priority Date: 06/22/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Glen M. Jeh, Kevin A. Gibbs, Sepandar D. Kamvar, Taher H. Haveliwala
• Inventors: Kamvar, Sepandar D., Jeh, Glen M., Gibbs, Kevin A., Haveliwala, Taher H.
• Granted Patent: US 9,081,851 B2
• Time in Patent Office: 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;

receiving a partial search query from 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 a set of historical complete search queries previously submitted by a community of users, the set of historical complete search queries corresponding to the partial search query and ordered in accordance with a ranking criteria; and

conveying the set of ordered complete search queries to the client system.

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

3. The method of claim 1, wherein the obtaining includes obtaining the set of complete search queries ordered in accordance with frequency of submission values associated with the complete search queries in the set, 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 including,

at the server system:

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

in response to the determining, sending to the client system a subsequent set of complete search queries ordered in accordance with the ranking criteria.

5. The method of claim 1, wherein the obtaining includes extracting the set of historical complete search queries from a database of historical complete search queries that were previously submitted by users in the community of users.

6. The method of claim 5, wherein the database of historical complete search queries includes historical complete search queries ordered in accordance with the ranking criteria.

7. The method of claim 1, wherein the obtaining includes modifying the set of historical complete search queries based on characteristics associated with a search requestor at the client system.

8. The method of claim 1, further including,

at the server system:

receiving from the client system a selection of a search query from the set of 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 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 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 a set of historical complete search queries previously submitted by a community of users, the set of historical complete search queries corresponding to the partial search query and ordered in accordance with a ranking criteria; and

to convey the set of ordered complete search queries to the client system.

11. The computer readable storage medium of claim 10, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system to order the 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 set of historical complete search queries include instructions, which when executed, cause the server system to obtain the set of complete search queries ordered in accordance with frequency of submission values associated with the complete search queries in the set, 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, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system:

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

in response to the determination, to send to the client system a subsequent set of complete search queries ordered in accordance with the ranking criteria.

14. The computer readable storage medium of claim 10, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system extract the set of historical complete search queries from a database of historical complete search queries that were previously submitted by users in the community of users.

15. The computer readable storage medium of claim 14, wherein the database of historical complete search queries includes historical complete search queries ordered in accordance with the ranking criteria.

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

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

to receive from the client system a selection of a search query from the set of 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, wherein the instructions to obtain the set of historical complete search queries include 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 set 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 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 a set of historical complete search queries previously submitted by a community of users, the set of historical complete search queries corresponding to the partial search query and ordered in accordance with a ranking criteria; and

instructions to convey the set of ordered complete search queries to the client system.

20. The server system of claim 19, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system to order the 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 set of historical complete search queries include instructions, which when executed, cause the server system to obtain the set of complete search queries ordered in accordance with frequency of submission values associated with the complete search queries in the set, 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, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system:

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

in response to the determination, to send to the client system a subsequent set of complete search queries ordered in accordance with the ranking criteria.

23. The server system of claim 19, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system extract the set of historical complete search queries from a database of historical complete search queries that were previously submitted by users in the community of users.

24. The server system of claim 23, wherein the database of historical complete search queries includes historical complete search queries ordered in accordance with the ranking criteria.

25. The server system of claim 19, wherein the instructions to obtain the set of historical complete search queries include instructions, which when executed, cause the server system to modify the set of historical complete search queries based on characteristics associated with a search requester at the client system.

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

to receive from the client system a selection of a search query from the set of 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, wherein the instructions to obtain the set of historical complete search queries include 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.