Suggesting and refining user input based on original user input

• US 9,411,906 B2
• Filed: 04/14/2015
• Issued: 08/09/2016
• Est. Priority Date: 05/04/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Wu, Jun, Lin, Dekang, Qian, Zhe, Zhou, Jie
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US14/686,555
• Publication Number:
  US 20150220547A1
• Time in Patent Office: 483 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/242 Query formulation
• 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/90324 using system suggestions

Abstract

Systems and methods to generate modified/refined user inputs based on the original user input, such as a search query, are disclosed. The method may be implemented for Roman-based and/or non-Roman based language such as Chinese. The method may generally include receiving an original user input and identifying core terms therein, determining potential alternative inputs by replacing core term(s) in the original input with another term according to a similarity matrix and/or substituting a word sequence in the original input with another word sequence according to an expansion/contraction table where one word sequence is a substring of the other, computing likelihood of each potential alternative input, and selecting most likely alternative inputs according to a predetermined criteria, e.g., likelihood of the alternative input being at least that of the original input. A cache containing pre-computed original user inputs and corresponding alternative inputs may be provided.

Claims

1. A computer-implemented method comprising:

receiving a first search query from a user associated with a user device;

obtaining a plurality of queries received from the user in a current query session, the plurality of queries including the first search query and one or more queries received from the user before the first search query;

generating a plurality of query suggestions for the first search query including replacing one or more first terms occurring in the first search query with one or more second terms;

computing a respective relevance score between the plurality of queries received from the user in the current query session and each query suggestion of the plurality of query suggestions;

computing for each of the plurality of query suggestions a respective position of a selected search result that was previously provided in response to receiving the query suggestion as a search query;

computing a respective ranking score for each of the plurality of query suggestions based on the respective relevance score for each of the plurality of query suggestions and the respective position of the selected search result that was previously provided in response to receiving the query suggestion as a search query;

ranking the plurality of query suggestions according to the computed ranking score for each of the plurality of query suggestions; and

providing one or more highest-ranked query suggestions to the user in response to receiving the first search query.

2. The method of claim 1, wherein the plurality of queries received from the user in the current query session are user refinements of an original search query.

3. The method of claim 1, further comprising:

computing for each of the plurality of query suggestions a respective likelihood that the query suggestion will be selected by the user, wherein computing the ranking score for the query suggestion comprises computing the ranking score based on the likelihood that the query suggestion will be selected by the user.

4. The method of claim 1, wherein computing the respective relevance score between the plurality of queries received from the user in the current query session and each query suggestion of the plurality of query suggestions comprises:

computing a correlation score between core terms in the first query and one or more core terms in each of the plurality of queries received from the user in the current query session.

5. The method of claim 4, further comprising determining aligned terms between the core terms in the first query and the one or more core terms in each of the plurality of queries received from the user in the current query session.

6. The method of claim 5, wherein a correlation score between aligned terms is based on a function of a plurality of weights, each weight corresponding to a respective relationship between the aligned terms, wherein the relationships between the aligned terms include one or more of a synonym relationship, an acronym relationship, an antonym relationship, a compound phrase relationship, or a same category relationship.

7. A system comprising:

one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising;

receiving a first search query from a user associated with a user device;

obtaining a plurality of queries received from the user in a current query session, the plurality of queries including the first search query and one or more queries received from the user before the first search query;

generating a plurality of query suggestions for the first search query including replacing one or more first terms occurring in the first search query with one or more second terms;

computing a respective relevance score between the plurality of queries received from the user in the current query session and each query suggestion of the plurality of query suggestions;

computing for each of the plurality of query suggestions a respective position of a selected search result that was previously provided in response to receiving the query suggestion as a search query;

computing a respective ranking score for each of the plurality of query suggestions based on the respective relevance score for each of the plurality of query suggestions and the respective position of the selected search result that was previously provided in response to receiving the query suggestion as a search query;

ranking the plurality of query suggestions according to the computed ranking score for each of the plurality of query suggestions; and

providing one or more highest-ranked query suggestions to the user in response to receiving the first search query.

8. The system of claim 7, wherein the plurality of queries received from the user in the current query session are user refinements of an original search query.

9. The system of claim 7, wherein the operations further comprise:

computing for each of the plurality of query suggestions a respective likelihood that the query suggestion will be selected by the user, wherein computing the ranking score for the query suggestion comprises computing the ranking score based on the likelihood that the query suggestion will be selected by the user.

10. The system of claim 7, wherein the operations further comprise:

computing for each of the plurality of query suggestions a respective position of a selected search result that was previously provided in response to receiving the query suggestion as a search query, wherein computing the ranking score for the query suggestion comprises computing the ranking score based on the position of the selected search result that was previously provided in response to receiving the query suggestion as a search query.

11. The system of claim 7, wherein computing the respective relevance score between the plurality of queries received from the user in the current query session and each query suggestion of the plurality of query suggestions comprises:

computing a correlation score between core terms in the first query and one or more core terms in each of the plurality of queries received from the user in the current query session.

12. The system of claim 11, wherein the operations further comprise determining aligned terms between the core terms in the first query and the one or more core terms in each of the plurality of queries received from the user in the current query session.

13. The system of claim 12, wherein a correlation score between aligned terms is based on a function of a plurality of weights, each weight corresponding to a respective relationship between the aligned terms, wherein the relationships between the aligned terms include one or more of a synonym relationship, an acronym relationship, an antonym relationship, a compound phrase relationship, or a same category relationship.

14. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a first search query from a user associated with a user device;

obtaining a plurality of queries received from the user in a current query session, the plurality of queries including the first search query and one or more queries received from the user before the first search query;

generating a plurality of query suggestions for the first search query including replacing one or more first terms occurring in the first search query with one or more second terms;

computing a respective relevance score between the plurality of queries received from the user in the current query session and each query suggestion of the plurality of query suggestions;

computing for each of the plurality of query suggestions a respective position of a selected search result that was previously provided in response to receiving the query suggestion as a search query;

computing a respective ranking score for each of the plurality of query suggestions based on the respective relevance score for each of the plurality of query suggestions and the respective position of the selected search result that was previously provided in response to receiving the query suggestion as a search query;

ranking the plurality of query suggestions according to the computed ranking score for each of the plurality of query suggestions; and

providing one or more highest-ranked query suggestions to the user in response to receiving the first search query.

15. The computer program product of claim 14, wherein the plurality of queries received from the user in the current query session are user refinements of an original search query.

16. The computer program product of claim 14, wherein the operations further comprise:

computing for each of the plurality of query suggestions a respective likelihood that the query suggestion will be selected by the user, wherein computing the ranking score for the query suggestion comprises computing the ranking score based on the likelihood that the query suggestion will be selected by the user.

17. The computer program product of claim 14, wherein the operations further comprise:

computing for each of the plurality of query suggestions a respective position of a selected search result that was previously provided in response to receiving the query suggestion as a search query, wherein computing the ranking score for the query suggestion comprises computing the ranking score based on the position of the selected search result that was previously provided in response to receiving the query suggestion as a search query.

18. The computer program product of claim 14, wherein computing the respective relevance score between the plurality of queries received from the user in the current query session and each query suggestion of the plurality of query suggestions comprises:

computing a correlation score between core terms in the first query and one or more core terms in each of the plurality of queries received from the user in the current query session.

19. The computer program product of claim 18, wherein the operations further comprise determining aligned terms between the core terms in the first query and the one or more core terms in each of the plurality of queries received from the user in the current query session.

20. The computer program product of claim 19, wherein a correlation score between aligned terms is based on a function of a plurality of weights, each weight corresponding to a respective relationship between the aligned terms, wherein the relationships between the aligned terms include one or more of a synonym relationship, an acronym relationship, an antonym relationship, a compound phrase relationship, or a same category relationship.