Autocompletion for partially entered query

• US 8,996,550 B2
• Filed: 06/03/2010
• Issued: 03/31/2015
• Est. Priority Date: 06/03/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ko, David H., Lee, Kayi, Law, Ching, Tse, Chi Yung
• Primary Examiner(s): ROBERTS, SHAUN A
• Application Number:
  US13/376,364
• Publication Number:
  US 20120166182A1
• Time in Patent Office: 1,762 Days
• Field of Search: 704 8- 9, 707/722, 707/727, 707/758, 715/256, 715/264
• US Class Current: 707/758
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/58 Use of machine translation, e.g. for multi-lingual retrieval, for server-side translation for client devices or for real-time translation

Abstract

A server system receives, respectively, a first character string from a first user and a second character string from a second user. There are one or more differences between the first and second character strings. The server system obtains from a plurality of previously submitted complete queries, respectively, a first set of predicted complete queries corresponding to the first character string and a second set of predicted complete queries corresponding to the second character string. There are one or more identical queries in both the first and second sets. The server system conveys at least a first subset of the first set to the first user and at least a second subset of the second set to the second user. Both the first subset and the second subset include a respective identical query.

Claims

1. A computer-implemented method, comprising:

at a server system,

maintaining a database corresponding to a language specific model that maps non-Latin character strings to one or more corresponding Latin character strings using at least one of user survey data, custom data and third party data, the language specific model based, at least in part, on phonetic representations of respective non-Latin character strings, wherein the model includes, for each of a plurality of respective non-Latin character strings, a plurality of distinct Latin character strings, wherein at least one of the plurality of distinct Latin character strings is based on personal preferences of different users to the phonetic representations of the non-Latin character string;

receiving, respectively, a first string of Latin characters from a first user and a second string of Latin characters from a second user, wherein there are one or more differences between the first and second strings of Latin characters, wherein the one or more differences occurs due to different preferences of the first user and the second user to the phonetic representations of the same non-Latin character string;

obtaining from a plurality of previously submitted complete queries and the language specific model, respectively, a first set of predicted complete queries corresponding to the first string of Latin characters and a second set of predicted complete queries corresponding to the second string of Latin characters, wherein there are one or more identical queries in both the first and second sets, wherein at least one identical query of the one or more identical queries is obtained by respectively mapping the first and second strings of Latin characters having the one or more differences to the same non-Latin character string using the language specific model; and

conveying at least a first subset of the first set to the first user and at least a second subset of the second set to the second user, wherein both the first subset and the second subset include a respective identical predicted complete query, wherein the first subset include a respective identical query.

2. The method of claim 1, wherein the first and second strings of Latin characters correspond to two distinct phonetic representations of the same query in Cantonese.

3. The method of claim 1, wherein the one or more differences include a difference between the respective leading characters of the first and second strings of Latin characters.

4. The method of claim 1, wherein the one or more differences include a difference between the respective ending characters of the first and second strings of Latin characters.

5. The method of claim 1, wherein the first subset of the first set of predicted complete queries includes a plurality of predicted complete queries in the first language and a plurality of predicted complete queries in a second language.

6. The method of claim 5, wherein the plurality of predicted complete queries in the first language are for concurrent display with the plurality of predicted complete queries in the second language.

7. The method of claim 1, wherein each predicted complete query has a popularity score, further comprising:

conveying, respectively, each of the first and second subsets of predicted complete queries in a respective order based on their respective popularity scores within the same subset.

8. The method of claim 7, wherein the respective identical predicted complete query is preceded by a first number of predicted complete queries in the first subset and by a second number of predicted complete queries in the second subset and the first number is different from the second number.

9. The method of claim 1, further comprising:

applying a hash function to each of the first and second strings of Latin characters to produce a respective hash value; and

performing a lookup operation using the respective hash value to obtain the respective set of predicted complete queries.

10. A computer system for processing query information, comprising:

means for maintaining a database corresponding to a language specific model that maps non-Latin character strings to one or more corresponding Latin character strings using at least one of user survey data, custom data and third party data, the language specific model based, at least in part, on phonetic representations of respective non-Latin character strings, wherein the model includes, for each of a plurality of respective non-Latin character strings, a plurality of distinct Latin character strings, wherein at least one of the plurality of distinct Latin character strings is based on personal preferences of different users to the phonetic representations of the non-Latin character string;

means for receiving, respectively, a first string of Latin characters from a first user and a second string of Latin characters from a second user, wherein there are one or more differences between the first and second strings of Latin characters, wherein the one or more differences occurs due to different preferences of the first user and the second user to the phonetic representations of the same non-Latin character string;

means for obtaining from a plurality of previously submitted complete queries and the language specific model, respectively, a first set of predicted complete queries corresponding to the first string of Latin characters and a second set of predicted complete queries corresponding to the second string of Latin characters, wherein there are one or more identical queries in both the first and second sets, wherein at least one identical query of the one or more identical queries is obtained by respectively mapping the first and second strings of Latin characters having the one or more differences to the same non-Latin character string using the language specific model; and

means for conveying at least a first subset of the first set to the first user and at least a second subset of the second set to the second user, wherein both the first subset and the second subset include a respective identical query.

11. The computer system of claim 10, wherein the first and second strings of Latin characters correspond to two phonetic representations of the same query in Cantonese.

12. The computer system of claim 10, wherein the one or more differences include a difference between the respective leading characters of the first and second strings of Latin characters.

13. The computer system of claim 10, wherein the one or more differences include a difference between the respective ending characters of the first and second strings of Latin characters.

14. The computer system of claim 10, wherein the first subset of the first set of predicted complete queries includes a plurality of predicted complete queries in the first language and a plurality of predicted complete queries in a second language.

15. The computer system of claim 14, wherein the plurality of predicted complete queries in the first language are for concurrent display with the plurality of predicted complete queries in the second language.

16. The computer system of claim 10, wherein each predicted complete query has a popularity score, and the system further includes means for conveying, respectively, each of the first and second subsets of predicted complete queries in a respective order based on their respective popularity scores within the same subset.

17. The computer system of claim 16, wherein the respective identical predicted complete query is preceded by a first number of predicted complete queries in the first subset and by a second number of predicted complete queries in the second subset and the first number is different from the second number.

18. The computer system of claim 10, further including:

means for applying a hash function to each of the first and second strings of Latin characters to produce a respective hash value; and

means for performing a lookup operation using the respective hash value to obtain the respective set of predicted complete queries.