Method and system for autocompletion using ranked results

• US 7,487,145 B1
• Filed: 11/11/2004
• Issued: 02/03/2009
• 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., Jeh, Glen M., Gibbs, Kevin A., Haveliwala, Taher H.
• Primary Examiner(s): Mizrahi; Diane
• Application Number:
  US10/987,295
• Time in Patent Office: 1,545 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/7, 707/100, 707/101, 707/103, 707/102, 705/26, 709/206
• 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 requestors 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 method for processing query information, comprising:

receiving from a search requestor a partial search query;

the receiving including receiving the partial search query from the search requester prior to the search requester requesting a search on a complete search query that includes the partial search query;

obtaining a set of complete queries previously submitted by a community of users corresponding to the partial query, ordered in accordance with a ranking criteria;

sending the set of ordered complete queries to the search requester; and

prior to receiving the partial search query;

identifying a set of historical complete queries previously submitted by the community of users, each of the complete queries in the set of historical complete queries having frequency of submission information associated with the complete query; and

generating a plurality of ordered subsets of the identified set of historical complete queries, each ordered subset of historical complete queries including a subset of the identified set of historical complete queries ordered in accordance with the frequency of submission information associated with the historical complete queries in the subset;

wherein the obtaining includes accessing one of the ordered subsets of historical complete queries, selected in accordance with the received partial search query.

2. A method for processing query information, comprising:

receiving from a search requester a partial search query;

the receiving including receiving the partial search query from the search requester prior to the search requester requesting a search on a complete search query that includes the partial search query;

obtaining a set of complete queries previously submitted by a community of users corresponding to the partial query, ordered in accordance with a ranking criteria;

sending the set of ordered complete queries to the search requester;

identifying a set of historical complete queries previously submitted by the community of users, each of the complete queries in the set of historical complete queries having frequency of submission information associated with the complete query; and

generating a plurality of ordered subsets of the identified set of historical complete queries, each ordered subset of historical complete queries including a subset of the identified set of historical complete queries ordered in accordance with the frequency of submission information associated with the historical complete queries in the subset;

wherein the obtaining includes accessing one of the ordered subsets of historical complete queries, selected in accordance with the received partial search query.

3. A method for processing query information, comprising:

receiving from a search requestor a partial search query;

the receiving including receiving the partial search query from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

obtaining a set of complete queries previously submitted by a community of users corresponding to the partial query, ordered in accordance with a ranking criteria;

sending the set of ordered complete queries to the search requestor; and

prior to receiving the partial search query;

identifying a plurality of sets, each of the plurality of sets associated with a query unit and comprising a plurality of historical complete queries previously submitted by the community of users, each complete query having a respective ranking value; and

for at least a portion of the plurality of sets, ordering the queries in the set in accordance with the respective ranking value;

wherein the obtaining includes identifying the set of complete queries, from among the plurality of sets, wherein the identified set corresponds to the received partial search query.

4. A method for processing query information, comprising:

receiving from a search requestor a partial search query;

the receiving including receiving the partial search query from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

obtaining a set of complete queries previously submitted by a community of users corresponding to the partial query, ordered in accordance with a ranking criteria;

sending the set of ordered complete queries to the search requestor; and

prior to receiving the partial search query;

identifying a plurality of sets, each of the plurality of sets associated with a query unit and comprising a plurality of historical complete queries previously submitted by the community of users, each complete query having a respective ranking value; and

for at least a portion of the plurality of sets, ordering the complete queries in the plurality of sets in accordance with the respective ranking value;

wherein the obtaining includes;

identifying two or more sets, from among the portion, wherein the identified sets correspond to the received partial search query, and

merging the identified sets in an interleaved fashion.

5. A method for processing query information, comprising:

receiving from a search requester a partial search query;

the receiving including receiving the partial search query from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

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

sending the set of ordered complete queries to the search requestor;

wherein the obtaining includes;

identifying a plurality of previously submitted historical complete queries relevant to the partial search query;

ordering at least a subset of the plurality in accordance with the ranking criteria; and

identifying the set from the subset as ordered.

6. The method of claim 5, wherein:

the identifying includes identifying the plurality from historical complete queries previously submitted by the community of users; and

ordering includes ordering the subset in accordance with a frequency of submission of each complete query in the subset.

7. The method of claim 5, further including generating, prior to receiving the partial search query, data representing the plurality of previously submitted complete queries from complete queries previously submitted by the community of users.

8. The method of claim 5, further including:

determining related query information from the received partial search query;

identifying at least one obtained complete query relevant to the related query information; and

including the at least one obtained complete query relevant to the related query information in the subset.

9. The method of claim 5, wherein the obtaining further includes identifying at least one complete query in accordance with a modified spelling of the partial search query.

10. A computer-implemented program product, for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored in memory, which when executed cause the computer system;

to receive a partial search query from a search requestor;

wherein the partial search query is received from the search requester prior to the search requester requesting a search on a complete search query that includes the partial search query;

to obtain a set of complete queries previously submitted by a community of users corresponding to the partial query, ordered in accordance with a ranking criteria;

to send the set of ordered complete queries to the search requester; and

prior to receiving the partial search query;

to identify a set of historical complete queries previously submitted by the community of users, each of the complete queries in the set of historical complete queries having frequency of submission information associated with the complete query; and

to generate a plurality of ordered subsets of the identified set of historical complete queries, each ordered subset of historical complete queries including a subset of the identified set of historical complete queries ordered in accordance with the frequency of submission information associated with the historical complete queries in the subset;

wherein the one or more computer programs include instructions stored in the memory, which when executed cause the computer system to access one of the ordered subsets of historical complete queries, selected in accordance with the received partial search query.

11. A computer-implemented program product, for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored in memory, which when executed cause the computer system;

to receive a partial search query from a search requester;

wherein the partial search query is received from the search requester prior to the search requester requesting a search on a complete search query that includes the partial search query;

to identify a set of historical complete queries previously submitted by the community of users, each of the complete queries in the set of historical complete queries having frequency of submission information associated with the complete query;

to generate a plurality of ordered subsets of the identified set of historical complete queries, each ordered subset of historical complete queries including a subset of the identified set of historical complete queries ordered in accordance with the frequency of submission information associated with the historical complete queries in the subset;

to access one of the ordered subsets of historical complete queries, selected in accordance with the received partial search query;

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

to send the set of ordered complete queries to the search requestor.

12. A computer-implemented program product, for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored in memory, which when executed cause the computer system;

to receive a partial search query from a search requestor;

wherein the partial search query is received from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

to obtain a set of complete queries previously submitted by a community of users corresponding to the partial query, ordered in accordance with a ranking criteria;

to send the set of ordered complete queries to the search requestor; and

prior to receiving the partial search query;

to identify a plurality of sets, each of the plurality of sets associated with a query unit and comprising a plurality of historical complete queries previously submitted by the community of users, each complete query having a respective ranking value; and

for at least a portion of the plurality of sets, to order the complete queries in the plurality of sets in accordance with the respective ranking value;

wherein the one or more programs include instructions, which when executed cause the computer system to identify the set of complete queries, from among the plurality of sets, wherein the selected set corresponds to the received partial search query.

13. A computer-implemented program product for use with a computer system, the computer-implemented program product comprising:

one or more computer programs stored in memory, which when executed cause the computer system;

to receive a partial search query from a search requestor;

wherein the partial search query is received from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

to identify a plurality of historical complete queries previously submitted by a community of users relevant to the partial search query;

to order at least a subset of the plurality in accordance with a ranking criteria;

to obtain from a subset as ordered the set of complete queries previously submitted by the community of users corresponding to the partial query, ordered in accordance with the ranking criteria;

to send the set of complete queries previously submitted by the community of users to the search requester; and

to generate, prior to receiving the partial search query, data representing the plurality of historical complete queries previously submitted by the community of users.

14. The computer-implemented program product of claim 13, wherein the one or more programs include instructions stored in the memory, which when executed cause the computer system:

to order the subset in accordance with a historical frequency of submission of each complete query in the subset.

15. The computer-implemented program product of claim 13, further comprising instructions stored in the memory, which when executed cause the computer system:

to determine related query information from the partial search query;

to identify at least one obtained complete query relevant to the related query information; and

to include the at least one obtained complete query relevant to the related query information in the subset.

16. The computer-implemented program product of claim 13, wherein the one or more computer programs include instructions stored in memory, which when executed cause the computer system to identify at least one complete query in accordance with a modified spelling of the partial search query.

17. A 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 complete queries previously submitted by a community of users, ordered in accordance with a ranking function, the set relevant to a partial search query;

a receiving module that during operation of the system receives the partial search query from a search requestor;

wherein the partial search query is received from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

a prediction module that during operation of the system associates the set of complete queries to the partial search query, wherein the prediction module is further configured so that during operation of the system the prediction module associates one of the ordered subsets with the received partial search query;

a transmission module that during operation of the system sends the set of complete queries to the search requestor;

a set of historical complete queries previously submitted by the community of users, each of the complete queries in the set of historical complete queries having an associated frequency of submission information; and

a plurality of ordered subsets of historical complete queries generated from the set of historical complete queries, each subset ordered in accordance with the associated frequency of submission information.

18. The system of claim 17, wherein the memory further stores:

a plurality of time/date values, each associated with a respective complete query in the set of complete queries; and

an ordering module that during operation of the system orders the set of complete queries in accordance with the time/date values.

19. The system of claim 17, wherein the prediction module is configured so that during operation of the system the prediction module identifies at least one complete query in accordance with a modified spelling of the partial search query.

20. The system of claim 17, wherein the memory further stores a personalization module that during operation of the system modifies the set based on characteristics associated with a user.

21. The system of claim 17, wherein the memory further stores:

a time/response module that during operation of the system determines that no selection corresponding to a sent query is received from the search requester within a predetermined time period; and

a transmission module that during operation of the system sends the set of complete queries to the search requester and, in response to the time/response module, sends a subsequent set of complete queries ordered in accordance with the ranking function.

22. A 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 complete queries previously submitted by a community of users, ordered in accordance with a ranking function, the set relevant to a partial search query;

a receiving module that during operation of the system receives the partial search query from a search requestor;

wherein the partial search query is received from the search requestor prior to the search requestor requesting a search on a complete search query that includes the partial search query;

a prediction module that during operation of the system associates the set of complete queries to the partial search query;

a transmission module that during operation of the system sends the set of complete queries to the search requester;

an identification module that during operation of the system identifies historical complete queries relevant to the partial search query from the set of complete queries previously submitted;

an ordering module that during operation of the system orders at least a subset of the identified complete queries in accordance with the ranking function; and

instructions to generate, prior to receiving the partial search query, data representing the historical complete queries.

23. The system of claim 22, wherein the memory further stores:

a plurality of frequency of submission values, each associated with a respective one of the complete queries previously submitted; and

wherein the ordering module, during operation of the system, orders the subset in accordance with the frequency of submission values.

24. The system of claim 22, wherein the memory further stores:

a concept module that during operation of the system determines related query information from the partial search query; and

the subset includes at least one complete query relevant to the related query information.