Method and system for autocompletion for languages having ideographs and phonetic characters

• US 20060106769A1
• Filed: 11/12/2004
• Published: 05/18/2006
• Est. Priority Date: 11/12/2004
• Status: Abandoned Application

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Gibbs, Kevin A.
• Application Number:
  US10/987,769
• Publication Number:
  US 20060106769A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

A set of ordered predicted completion strings including strings of ideographs are presented to a user as the user enters text in a text entry box (e.g., a browser or a toolbar). The user entered text may include zero or more ideographs followed by one or more phonetic characters, or the entered text may be one or more. 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. The sets of ordered predicted completion strings are 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. The generation of the ordered prediction strings takes into account multiple phonetic representations of certain strings of ideographs.

Claims

1. A method for suggesting query completions for a language having ideographs and phonetic characters, comprising:

receiving a partial query from a search requester, the partial query comprising zero or more ideographs followed by at least one phonetic character;

predicting from the partial query one of a set of predicted queries ordered in accordance with a ranking criteria, the set containing ideographs; and

conveying the set of ordered predicted queries to the search requestor.

2. A method for suggesting query completions for a language having ideographs and phonetic characters, comprising:

receiving a partial query from a search requester, the partial query comprising a portion of a complete query;

predicting from the partial query a set of predicted queries ordered in accordance with a ranking criteria, the set containing at least one string having one or more ideographs; and

conveying the set of ordered predicted queries to the search requestor.

3. The method of claim 2, wherein the partial query includes at least one phonetic character.

4. The method of claim 2, wherein the partial query comprises both ideographs and phonetic characters.

6. The method of claim 2, further comprising:

including queries submitted by a community of users in the set of predicted queries.

7. The method of claim 2, further including creating the set of predicted queries from queries submitted by a community of users.

8. The method of claim 2, wherein the set of predicted queries includes at least one query not previously submitted by the search requestor.

9. The method of claim 2, wherein the set includes both search queries and at least one URL.

10. The method of claim 2, wherein the predicting includes identifying two or more sets corresponding to the partial query and merging the sets.

11. The method of claim 10, further including merging the sets in an interleaved fashion.

12. The method of claim 10, wherein at least a first one of the sets is generated on a client and a second one of the sets is generated on a server.

13. The method of claim 2, including:

receiving input identifying a selected query from among the set of ordered predicted queries; and

generating search results relevant to the received query.

14. The method of claim 2, including generating search results relevant to at least one of the predicted queries, and

conveying the search results to the requestor.

15. The method of claim 2, further including:

determining related query information from the received query information;

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

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

16. The method of claim 2, wherein the predicting includes ordering the predicted queries in accordance with a time/date value of the predicted query.

17. The method of claim 2, further including modifying the set based on characteristics associated with a user.

18. The method of claim 2, further including:

conveying the set to the search requestor;

determining that no selection corresponding to a transmitted query in the set is received from the search requestor within a predetermined time period; and

transmitting to the search requestor a subsequent set of predicted queries ordered in accordance with the ranking criteria.

19. The method of claim 2, further including:

conveying the set to the search requestor;

receiving a request from the search requestor for a subsequent set of predicted queries;

identifying a subsequent set of predicted queries; and

transmitting to the search requestor the subsequent set of predicted queries ordered in accordance with the ranking criteria.

20. The method of claim 2, including:

prior to receiving the partial query;

identifying a set of historical queries previously submitted by a community of users, each of the queries in the set of historical queries having a frequency of submission and including at least one ideograph; and

generating a plurality of ordered subsets from the identified set of historical queries, each ordered subset including one or more historical queries from the identified set of historical queries ordered in accordance with a respective frequency of submission.

21. The method of claim 20, wherein the generating includes:

mapping strings of one or more ideographs from a plurality of historical queries into one or more representations that include a string of one or more phonetic characters.

22. The method of claim 20, wherein the generating includes mapping a string of one or more ideographs from a plurality historical queries into one or more representations, wherein a least one mapping includes at least one ideograph and a string of one or more phonetic characters.

23. The method of claim 2, including:

identifying a set of historical queries previously submitted by a community of users, each of the queries in the set of historical queries having a frequency of submission and including at least one ideograph; and

generating a plurality of ordered subsets from the identified set of historical queries, each ordered subset including one or more historical queries from the identified set of historical queries ordered in accordance with a respective frequency of submission.

24. The method of claim 23, wherein the generating includes:

mapping strings of one or more ideographs from a plurality of historical queries into one or more representations that include a string of one or more phonetic characters.

25. The method of claim 2, including:

prior to receiving the partial query;

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

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

wherein the predicting includes identifying a first set, from among the plurality of sets, wherein the selected set corresponds to the partial query.

26. The method of claim 25, wherein the predicting includes identifying a second set and merging the first set and the second set.

27. The method of claim 26, wherein the predicting further includes:

identifying the first set from a first memory; and

identifying the second set from a second memory.

5. The method of clam 2, wherein the partial query includes at least one incomplete phonetic sequence representing at least one ideograph;

and

the predicting includes predicting at least one or more ideographs consistent with the incomplete phonetic sequence.

28. A system for suggesting query completions for a language having ideographs and phonetic characters, comprising:

a query processing module for receiving a partial query from a search requester, the partial query comprising a portion of a complete query;

at least one set of predicted queries ordered in accordance with a ranking criteria, the set containing at least query having a string of one or more ideographs;

a predicting module for predicting from the partial query the set of predicted queries ordered in accordance with the ranking criteria; and

a communication module for conveying the set of ordered predicted queries to the search requester.

29. The system of claim 28, wherein the partial query includes at least one phonetic character.

30. The system of claim 28, wherein the partial query comprises both ideographs and phonetic characters.

32. The system of claim 28, wherein the set of predicted queries includes queries submitted by a community of users.

33. The system of claim 28, wherein the set of predicted queries includes at least one query not previously submitted by the search requester.

34. The system of claim 28, wherein the set of predicted queries includes both search queries and at least one URL.

35. The system of claim 28, further including at least a second set of predicted queries ordered in accordance with a ranking criteria, the second set containing at least one query having a string of one or more ideographs, and

the predicting module is further configured to identify at least the first set and the second set of predicted queries and to merge the two sets.

36. The system of claim 35, wherein the predicting module is further configured to merge the first set and the second set in an interleaved fashion.

37. The system of claim 35, wherein the first set is located remotely from the second set.

38. The system of claim 28, further comprising:

a receiving module for receiving input identifying a selected query from among the set of ordered predicted queries; and

a query server for generating search results relevant to the received query.

39. The system of claim 28, wherein the query server is further configured to generate search results relevant to at least one of the predicted queries and convey the search results to the requester.

40. The system of claim 28, further including:

a concept module for determining related query information from the received query information; and

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

41. The system of claim 28, wherein the predicting modules is further configured to order the predicted queries in accordance with a time/date value of the predicted query.

42. The system of claim 28, further including modifying the set based on characteristics associated with a user.

43. The system of claim 28, wherein the prediction module is further configured to:

convey the set to the search requester;

receive a request from the search requestor for a subsequent set of predicted queries;

identify a subsequent set of predicted queries; and

transmit to the search requestor the subsequent set of predicted queries ordered in accordance with the ranking criteria.

44. The system of claim 28, wherein the prediction module is further configured to:

prior to receiving the partial query;

identify a set of historical queries previously submitted by a community of users, each of the queries in the set of historical queries having a frequency of submission and including at least one ideograph; and

generate a plurality of ordered subsets from the identified set of historical queries, each ordered subset including one or more historical queries from the identified set of historical queries ordered in accordance with a respective frequency of submission.

45. The system of claim 44, wherein the prediction module is further configured to:

map strings of one or more ideographs from a plurality of historical queries into one or more representations that include a string of one or more phonetic characters.

46. The system of claim 44, wherein the prediction module is further configured to map a string of one or more ideographs from a plurality historical of queries into one or more representations, wherein at least one mapping includes at least one ideograph and a string of one or more phonetic characters.

47. The system of claim 28, wherein the prediction module is further configured to:

identify a set of historical queries previously submitted by a community of users, each of the queries in the set of historical queries having a frequency of submission and including at least one ideograph; and

generate a plurality of ordered subsets from the identified set of historical queries, each ordered subset including one or more historical queries from the identified set of historical queries ordered in accordance with a respective frequency of submission.

48. The system of claim 47, wherein the prediction module is further configured to map strings of one or more ideographs from a plurality of historical queries into one or more representations that include a string of one or more phonetic characters.

49. The system of claim 28, wherein the prediction module is further configured to:

prior to receiving the partial query;

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

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

to predict a first set, from among the plurality of sets, wherein the selected set corresponds to the partial query.

50. The system of claim 49, wherein the prediction module is further configured to predict a second set and merge the first set and the second set.

51. The system of claim 50, wherein the prediction module is further configured to:

identify the first set from a first memory; and

identify the second set from a second memory.

31. The system of clam 28, wherein the partial query includes at least one incomplete phonetic sequence representing at least one ideograph;

and

wherein at least one predicted query in the set of predicted queries includes at least one or more ideographs consistent with the incomplete phonetic sequence.

52. A computer program product, for use with a computer system, the computer program product comprising:

instructions for receiving a partial query from a search requester, the partial query comprising a portion of a complete query;

instructions for predicting from the partial query a set of predicted queries ordered in accordance with a ranking criteria, the set containing at least one string having one or more ideographs; and

instructions for conveying the set of ordered predicted queries to the search requestor.

53. The computer program product of claim 52, wherein the partial query includes at least one phonetic character.

54. The computer program product of claim 52, wherein the partial query comprises both ideographs and phonetic characters.

56. The computer program product of claim 52, further comprising:

instructions for including queries submitted by a community of users in the set of predicted queries.

57. The computer program product of claim 52, further including instructions for creating the set of predicted queries from queries submitted by a community of users.

58. The computer program product of claim 52, wherein the set of predicted queries includes at least one query not previously submitted by the requester.

59. The computer program product of claim 52, wherein the set includes both search queries and at least one URL.

60. The computer program product of claim 52, wherein the instructions for predicting further include instructions for identifying two or more sets corresponding to the partial query and for merging the sets.

61. The computer program product of claim 60, further including instructions for merging the sets in an interleaved fashion.

62. The computer program product of claim 60, wherein at least a first one of the sets is generated on a client and a second one of the sets is generated on a server.

63. The computer program of claim 52, including:

instructions for receiving input identifying a selected query from among the set of ordered predicted queries; and

instructions for generating search results relevant to the received query.

64. The computer program product of claim 52, including instructions for generating search results relevant to at least one of the predicted queries, and

instructions for conveying the search results to the requester.

65. The computer program product of claim 52, further including:

instructions for determining related query information from the received query information;

instructions for identifying at least one predicted query relevant to the related query information; and

instructions for including the at least one predicted query relevant to the related query information in the subset.

66. The computer program product of claim 52, wherein the instructions for predicting further include ordering the predicted queries in accordance with a time/date value of the predicted query.

67. The computer program product of claim 52, further including instructions for modifying the set based on characteristics associated with a user.

68. The computer program product of claim 52, further including:

instructions for conveying the set to the search requester;

instructions for determining that no selection corresponding to a transmitted query in the set is received from the search requestor within a predetermined time period; and

instructions for transmitting to the search requestor a subsequent set of predicted queries ordered in accordance with the ranking criteria.

69. The computer program product of claim 52, further including:

instructions for conveying the set to the search requester;

instructions for receiving a request from the search requestor for a subsequent set of predicted queries;

instructions for identifying a subsequent set of predicted queries; and

instructions for transmitting to the search requestor the subsequent set of predicted queries ordered in accordance with the ranking criteria.

70. The computer program product of claim 52, including:

instructions for, prior to receiving the partial query;

identifying a set of historical queries previously submitted by a community of users, each of the queries in the set of historical queries having a frequency of submission and including at least one ideograph; and

generating a plurality of ordered subsets from the identified set of historical queries, each ordered subset including one or more historical queries from the identified set of historical queries ordered in accordance with a respective frequency of submission.

71. The computer program product of claim 70, wherein the instructions for generating further include instructions for mapping strings of one or more ideographs from a plurality of historical queries into one or more representations that include a string of one or more phonetic characters.

72. The computer program product of claim 70, wherein the instructions for generating further include instructions for mapping a string of one or more ideographs from a plurality of historical queries into one or more representations, wherein at least one mapping includes at least one ideograph and a string of one or more phonetic characters.

73. The computer program product of claim 52, including:

instructions for identifying a set of historical queries previously submitted by a community of users, each of the queries in the set of historical queries having a frequency of submission and including at least one ideograph; and

instructions for generating a plurality of ordered subsets from the identified set of historical queries, each ordered subset including one or more historical queries from the identified set of historical queries ordered in accordance with a respective frequency of submission.

75. The computer program product of claim 52, including:

instructions for, prior to receiving the partial query;

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

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

wherein the instructions for predicting further include identifying a first set, from among the plurality of sets, wherein the selected set corresponds to the partial query.

76. The computer program product of claim 75, wherein the instructions for predicting further include instructions for identifying a second set and merging the first set and the second set.

77. The computer program product of claim 76, wherein the instructions for predicting further include:

instructions for identifying the first set on a client; and

instructions for identifying the second set on a server.

55. The computer program product of clam 52, wherein the partial query includes at least one incomplete phonetic sequence representing at least one ideograph;

and

the instructions for the predicting further include instructions for predicting at least one or more ideographs consistent with the incomplete phonetic sequence.

74. The computer program product of claim 74, wherein the instructions for generating further include instructions for mapping strings of one or more ideographs from a plurality of historical queries into one or more representations that include a string of one or more phonetic characters.

78. A system for suggesting query completions for a language having ideographs and phonetic characters, comprising:

means for receiving a partial query from a search requestor, the partial query comprising a portion of a complete query;

means for predicting from the partial query a set of predicted queries ordered in accordance with a ranking criteria, the set containing at least one string having one or more ideographs; and

means for conveying the set of ordered predicted queries to the search requestor.