Generating word completions based on shared suffix analysis

• US 8,417,718 B1
• Filed: 09/21/2011
• Issued: 04/09/2013
• Est. Priority Date: 07/11/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Finkelstein, Lev, Kim, Eddo, Shotland, Ari, Mittelman, Alon
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US13/239,251
• Time in Patent Office: 566 Days
• Field of Search: 707/713, 707/759, 707/765, 707/766, 707/767
• US Class Current: 707/767
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions

Abstract

A technology is described herein for identifying suggested query completions for a partial query based upon unique queries which have suffixes similar to the suffix of the partial query, but have prefixes which do not contain the prefix of the partial query. The technology described herein selects suggested query completions for the partial query based on terms occurring at the ends of the unique queries, in a manner which is not limited to past queries that include all of the terms in the partial query. As a result, meaningful suggested query completions that are likely to assist the user in completing a partial query can be provided in instances where terms in the prefix of the partial query are ambiguous or uncommon.

Claims

1. A method of selecting suggested query completions for a partial query, the method including:

determining a prefix and a suffix of a partial query having multiple terms, the prefix including one or more terms occurring at a beginning of the partial query, the suffix including one or more terms occurring at an end of the partial query, wherein a last term in the prefix precedes a first term in the suffix;

calculating suffix similarity scores for unique queries having prefixes which do not include the prefix of the partial query as a substring, the suffix similarity score for a unique query based at least in part on similarity of terms in the suffix of the partial query and terms in a suffix of the unique query;

selecting one or more of the unique queries as candidate queries for completing the partial query based at least in part on the suffix similarity scores for the unique queries;

calculating completion scores for unique suffixes among the suffixes of the candidate queries, the completion scores representing an extent to which the unique suffixes are potential query completions for the partial query; and

using the completion scores to select one or more terms of the unique suffixes as suggested query completions for the partial query;

wherein the method is performed by one or more computer processors.

2. The method of claim 1, wherein the suffix of the partial query ends with an incomplete term.

3. The method of claim 2, wherein the suffix of at least one of the candidate queries includes a term which begins with the incomplete term in the suffix of the partial query.

4. The method of claim 1, wherein the suffix of at least one of the candidate queries includes at least two terms in common with the suffix of the partial query.

5. The method of claim 4, wherein the suffix of at least one of the candidate queries includes at least three terms in common with the suffix of the partial query.

6. The method of claim 1, wherein selecting one more of the unique queries as candidate queries includes:

identifying a first set of candidate queries having suffixes including at least three terms in common with the suffix of the partial query;

identifying a second set of candidate queries having suffixes including at least two terms in common with the suffix of the partial query; and

selecting the first set of candidate queries as the candidate queries for completing the partial query if the first set is not empty, and selecting the second set of candidate queries as the candidate queries for completing the partial query if the second set is empty.

7. The method of claim 1, wherein calculating the completion scores for the unique suffixes includes:

calculating query popularity scores for the candidate queries indicating frequency of the candidate queries in a log of past queries submitted to one or more search engines; and

calculating the completion scores for the unique suffixes using the query popularity scores of the corresponding candidate queries.

8. The method of claim 1, wherein using the completion scores includes:

using the completion scores to create a ranking of the unique suffixes; and

selecting one or more of the unique suffixes as suggested query completions based at least in part on the ranking.

9. The method of claim 8, wherein selecting the one or more unique suffixes includes selecting one or more unique suffixes having completion scores at least a threshold greater than the completion scores of remaining lower ranked unique suffixes.

10. The method of claim 1, wherein the candidate queries have suffixes which include the suffix of the partial query as a substring.

11. The method of claim 1, including:

receiving the partial query; and

sending one or more of the selected terms of the unique suffixes in response to receiving the partial query.

12. A non-transitory computer readable storage medium storing computer instructions executable by a processor to perform a method of selecting suggested query completions for a partial query, the method including:

determining a prefix and a suffix of a partial query having multiple terms, the prefix including one or more terms occurring at a beginning of the partial query, the suffix including one or more terms occurring at an end of the partial query, wherein a last term in the prefix precedes a first term in the suffix;

calculating suffix similarity scores for unique queries having prefixes which do not include the prefix of the partial query as a substring, the suffix similarity score for a unique query based at least in part on similarity of terms in the suffix of the partial query and terms in a suffix of the unique query;

selecting one or more of the unique queries as candidate queries for completing the partial query based at least in part on the suffix similarity scores for the unique queries;

calculating completion scores for unique suffixes among the suffixes of the candidate queries, the completion scores representing an extent to which the unique suffixes are potential query completions for the partial query; and

using the completion scores to select one or more terms of the unique suffixes as suggested query completions for the partial query.

13. The non-transitory computer readable storage medium of claim 12, wherein the suffix of the partial query ends with an incomplete term.

14. The non-transitory computer readable storage medium of claim 13, wherein the suffix of at least one of the candidate queries includes a term which begins with the incomplete term in the suffix of the partial query.

15. The non-transitory computer readable storage medium of claim 12, wherein the suffix of at least one of the candidate queries includes at least two terms in common with the suffix of the partial query.

16. The non-transitory computer readable storage medium of claim 15, wherein the suffix of at least one of the candidate queries includes at least three terms in common with the suffix of the partial query.

17. The non-transitory computer readable storage medium of claim 12, wherein selecting one more of the unique queries as candidate queries includes:

identifying a first set of candidate queries having suffixes including at least three terms in common with the suffix of the partial query;

identifying a second set of candidate queries having suffixes including at least two terms in common with the suffix of the partial query; and

selecting the first set of candidate queries as the candidate queries for completing the partial query if the first set is not empty, and selecting the second set of candidate queries as the candidate queries for completing the partial query if the second set is empty.

18. The non-transitory computer readable storage medium of claim 12, wherein calculating the completion scores for the unique suffixes includes:

calculating query popularity scores for the candidate queries indicating frequency of the candidate queries in a log of past queries submitted to one or more search engines; and

calculating the completion scores for the unique suffixes using the query popularity scores of the corresponding candidate queries.

19. The non-transitory computer readable storage medium of claim 12, wherein using the completion scores includes:

using the completion scores to create a ranking of the unique suffixes; and

selecting one or more of the unique suffixes as suggested query completions based at least in part on the ranking.

20. The non-transitory computer readable storage medium of claim 19, wherein selecting the one or more unique suffixes includes selecting one or more unique suffixes having completion scores at least a threshold greater than the completion scores of remaining lower ranked unique suffixes.

21. The non-transitory computer readable storage medium of claim 12, wherein the candidate queries have suffixes which include the suffix of the partial query as a substring.

22. The non-transitory computer readable storage medium of claim 12, including sending one or more of the selected terms of the unique suffixes in response to receiving the partial query.

23. A system including memory and one or more processors operable to execute instructions, stored in the memory, to select suggested query completions for a partial query, including instructions to:

determine a prefix and a suffix of a partial query having multiple terms, the prefix including one or more terms occurring at a beginning of the partial query, the suffix including one or more terms occurring at an end of the partial query, wherein a last term in the prefix precedes a first term in the suffix;

calculate suffix similarity scores for unique queries having prefixes which do not include the prefix of the partial query as a substring, the suffix similarity score for a unique query based at least in part on similarity of terms in the suffix of the partial query and terms in a suffix of the unique query;

select one or more of the unique queries as candidate queries for completing the partial query based at least in part on the suffix similarity scores for the unique queries;

calculate completion scores for unique suffixes among the suffixes of the candidate queries, the completion scores representing an extent to which the unique suffixes are potential query completions for the partial query; and

use the completion scores to select one or more terms of the unique suffixes as suggested query completions for the partial query.

24. The system of claim 23, wherein the suffix of the partial query ends with an incomplete term.

25. The system of claim 24, wherein the suffix of at least one of the candidate queries includes a term which begins with the incomplete term in the suffix of the partial query.

26. The system of claim 23, wherein the suffix of at least one of the candidate queries includes at least two terms in common with the suffix of the partial query.

27. The system of claim 26, wherein the suffix of at least one of the candidate queries includes at least three terms in common with the suffix of the partial query.

28. The system of claim 23, wherein the instructions to select one more of the unique queries as candidate queries includes instructions to:

identify a first set of candidate queries having suffixes including at least three terms in common with the suffix of the partial query;

identify a second set of candidate queries having suffixes including at least two terms in common with the suffix of the partial query; and

select the first set of candidate queries as the candidate queries for completing the partial query if the first set is not empty, and select the second set of candidate queries as the candidate queries for completing the partial query if the second set is empty.

29. The system of claim 23, wherein the instructions to calculate the completion scores for the unique suffixes includes instructions to:

calculate query popularity scores for the candidate queries indicating frequency of the candidate queries in a log of past queries submitted to one or more search engines; and

calculate the completion scores for the unique suffixes using the query popularity scores of the corresponding candidate queries.

30. The system of claim 23, wherein the instructions to use the completion scores includes instructions to:

use the completion scores to create a ranking of the unique suffixes; and

select one or more of the unique suffixes as suggested query completions based at least in part on the ranking.

31. The system of claim 30, wherein the instructions to select the one or more unique suffixes includes instructions to select one or more unique suffixes having completion scores at least a threshold greater than the completion scores of remaining lower ranked unique suffixes.

32. The system of claim 23, wherein the candidate queries have suffixes which include the suffix of the partial query as a substring.

33. The system of claim 23, including instructions to send one or more of the selected terms of the unique suffixes in response to receiving the partial query.