Autocompletion and Automatic Input Method Correction for Partially Entered Search Query

• US 20090043741A1
• Filed: 08/07/2008
• Published: 02/12/2009
• Est. Priority Date: 08/09/2007
• Status: Abandoned Application

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kim, Dohyung
• Application Number:
  US12/188,163
• Publication Number:
  US 20090043741A1
• 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: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A method for processing query information includes receiving a partial search query from a search requestor, and obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users. The set of predicted complete queries include both English language and Korean language complete search queries. The set of predicted complete queries are ordered in accordance with ranking criteria, and at least a subset of the ordered set is sent to the search requestor. The partial search query may be a Romanized representation of a partial Korean language search query.

Claims

1. A method for processing query information, comprising:

at a server,

receiving from a search requester a partial search query, the search requester located remotely from the server;

obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users;

the set of predicted complete queries including both first language and second language complete search queries;

ordering the set of predicted complete queries in accordance with ranking criteria; and

conveying at least a subset of the ordered set to the search requestor.

2. The method of claim 1, wherein the first language is Korean and the second language is English.

3. The method of claim 1, wherein, when the partial search query comprises a partially entered first language search query, the method includes generating a Romanized representation of the partial search query.

4. The method of claim 1, wherein, when the received partial search query includes one or more first language characters, obtaining a set of predicted complete queries includes:

converting the partial search query into a representation of the partial search query in characters of the second language;

applying a hash function to the representation of the partial search query to produce a hash value; and

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

5. The method of claim 1, wherein, when the received partial search query includes one or more complete first language characters and an incomplete first language character, obtaining a set of predicted complete queries includes:

converting the partial search query into a Romanized representation of the partial search query;

applying a hash function to the Romanized representation of the partial search query to produce a hash value; and

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

6. The method of claim 1, wherein the received partial search query includes one or more complete first language characters and an incomplete first language character.

7. The method of claim 1, including, prior to the conveying, filtering the set of predicted complete queries to remove queries, if any, matching one or more terms in one or more predefined sets of terms.

8. A method for processing query information, comprising:

at a client,

receiving from a search requestor a partial search query;

obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users, wherein the set of predicted complete queries includes both first language and second language complete search queries and is ordered in accordance with ranking criteria; and

displaying at least a subset of the ordered set to the search requester.

9. The method of claim 8, wherein the first language is Korean and the second language is English.

10. The method of claim 8, wherein, when the partial search query comprises a partially entered first language search query, the method includes generating a Romanized representation of the partial first language search query.

11. The method of claim 8, wherein the obtaining includes when the received partial search query includes one or more first language characters:

converting the partial search query into a representation of the partial search query in characters of the second language;

applying a hash function to the representation of the partial search query to produce a hash value; and

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

12. The method of claim 8, wherein the obtaining includes

when the received partial search query includes one or more complete first language characters and an incomplete first language character, converting the partial search query into a Romanized representation of the partial search query, applying a hash function to the Romanized representation of the partial search query to produce a hash value, and performing a lookup operation using the hash value to obtain the predicted complete queries.

13. The method of claim 8, wherein the received partial search query includes one or more complete first language characters and an incomplete first language character.

14. A system for processing query information, comprising:

one or more central processing units for executing programs; and

memory to store data and to store one or more programs to be executed by the one or more central processing units, the one or more programs including instructions for;

receiving from a search requestor a partial search query, the search requestor located remotely from the server;

obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users;

the set of predicted complete queries including complete search queries in both a first language and a second language distinct from the first language;

ordering the set of predicted complete queries in accordance with ranking criteria; and

conveying at least a subset of the ordered set to the search requester.

15. The system of claim 14, wherein the one or more programs include instructions for generating a Romanized representation of a respective partial search query that comprises a partially entered first language search query.

16. The system of claim 14, wherein the instructions for obtaining a set of predicted complete queries include instructions for:

converting a respective partial search query that includes one or more first language characters into a representation of the respective partial search query in characters of the second language;

applying a hash function to the representation of the partial search query to produce a hash value; and

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

17. The system of claim 14, wherein the instructions for obtaining a set of predicted complete queries include instructions for:

converting a respective partial search query that includes one or more complete first language characters and an incomplete first language character into a Romanized representation of the respective partial search query;

applying a hash function to the Romanized representation of the respective partial search query to produce a hash value; and

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

18. The system of claim 14, wherein the received partial search query includes one or more complete first language characters and an incomplete first language character.

19. The system of claim 14, wherein the instructions for obtaining a set of predicted complete queries include instructions for filtering the set of predicted complete queries to remove queries, if any, matching one or more terms in one or more predefined sets of terms.

20. The system of claim 14, wherein the instructions for obtaining a set of predicted complete queries include instructions for:

converting a respective partial search query that includes one or more Korean language characters into a Romanized representation of the respective partial search query

applying a hash function to the Romanized representation of the partial search query to produce a hash value; and

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

21. The system of claim 14, wherein the instructions for obtaining a set of predicted complete queries include instructions for:

converting a respective partial search query that includes one or more complete Korean language characters and an incomplete Korean language character into a Romanized representation of the respective partial search query;

applying a hash function to the Romanized representation of the respective partial search query to produce a hash value; and

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

22. The system of claim 14, wherein the received partial search query includes one or more complete Korean language characters and an incomplete Korean language character.

23. A method for building a data structure for processing query information, comprising:

obtaining a set of previously submitted complete first language queries, the complete first language queries previously submitted by a community of users;

obtaining a set of previously submitted complete second language queries, the complete second language queries previously submitted by a community of users;

converting the set of complete first language queries into a set of complete second language queries in Romanized representation; and

storing the sets of complete first language queries and Romanized complete second language queries in one or more query completion data tables;

wherein the one or more query completion data tables form one or more data structures capable of being used to predict both complete first language and second language queries corresponding to either partial first language queries or partial second language queries.

24. The method of claim 23, including filtering the set of previously submitted complete first language queries and the set of previously submitted second language queries to exclude queries matching one or more sets of predefined terms.

25. The method of claim 23, wherein the first language is Korean and the second language is English.

26. A client system, comprising:

one or more central processing units for executing programs; and

memory to store data and to store one or more programs to be executed by the one or more central processing units, the one or more programs including instructions for;

receiving from a search requestor a partial search query;

obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users, wherein the set of predicted complete queries includes both first language and second language complete search queries and is ordered in accordance with ranking criteria; and

displaying at least a subset of the ordered set to the search requester.

27. The client system of claim 26, wherein the first language is Korean and the second language is English.

28. A computer readable-storage medium storing one or more programs for execution by one or more processors of a respective server system, the one or more programs comprising instructions for:

receiving from a search requestor a partial search query, the search requestor located remotely from the server;

obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users;

the set of predicted complete queries including both first language and second language complete search queries;

ordering the set of predicted complete queries in accordance with ranking criteria; and

conveying at least a subset of the ordered set to the search requester.

29. The computer readable-storage medium of claim 28, wherein the first language is Korean and the second language is English.

30. A computer readable-storage medium storing one or more programs for execution by one or more processors of a respective client device or system, the one or more programs comprising instructions for:

receiving from a search requestor a partial search query;

obtaining a set of predicted complete queries corresponding to the partial search query from a plurality of previously submitted complete queries, the previously submitted complete queries submitted by a community of users, wherein the set of predicted complete queries includes both first language and second language complete search queries and is ordered in accordance with ranking criteria; and

displaying at least a subset of the ordered set to the search requester.

31. The computer readable-storage medium of claim 30, wherein the first language is Korean and the second language is English.