Query autocompletions

• US 9,031,970 B1
• Filed: 07/20/2011
• Issued: 05/12/2015
• Est. Priority Date: 01/26/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Effrat, Jonathan J., Wichary, Marcin K., Niechwiej, Bartlomiej
• Primary Examiner(s): Ly, Cheyne D
• Application Number:
  US13/186,930
• Time in Patent Office: 1,392 Days
• Field of Search: 707/706, 707/767, 707/76, 707/856, 715/257, 715/259
• US Class Current: 707/767
• 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

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for obtaining query completions. In one aspect, a method includes receiving a query input in a search engine query input field in a user interface. The method also includes submitting the query input as a first query stem to an autocompletion module. The method also includes receiving a first response from the autocompletion module, the first response providing no first query autocompletions. The method also includes submitting a second query stem to the autocompletion module, the second query stem being the first query stem with a first prefix removed. The method also includes receiving a second response from the autocompletion module including one or more second autocompletions satisfying a second quality test. The method also includes providing second autocompletions for presentation on the user interface.

Claims

1. A computer-implemented method comprising:

receiving a query input in a search engine query input field in a user interface, before receiving an input expressly submitting the query input as a query to a search engine, the query input comprising multiple query terms;

submitting the query input as a first query stem to an autocompletion module to obtain first query autocompletions;

determining that the first query autocompletions do not satisfy a first quality test and, in response, submitting a second query stem to the autocompletion module to obtain second query autocompletions, the second query stem being the first query stem with a prefix removed;

receiving, from the autocompletion module, one or more second query autocompletions satisfying a second quality test, wherein the second quality test includes determining a ratio of a number of times a potential autocompletion occurs in a corpus of user queries to a number of times any query that includes the second query stem occurs in the corpus user queries, and comparing the ratio to a threshold value; and

providing the one or more second query autocompletions for presentation on the user interface.

2. The method of claim 1, wherein the second quality test further comprises applying a smoothing factor to the ratio.

3. The method of claim 1, further comprising:

determining the prefix, wherein determining the prefix comprises;

assigning a query term of the multiple query terms to the prefix;

determining the query term is part of a compound word; and

assigning a second part of the compound word to the prefix.

4. A system, comprising:

one or more computers programmed to perform operations comprising;

receiving a query input in a search engine query input field in a user interface, before receiving an input expressly submitting the query input as a query to a search engine, the query input comprising multiple query terms;

submitting the query input as a first query stem to an autocompletion module to obtain first query autocompletions;

determining that the first query autocompletions do not satisfy a first quality test, and, in response, submitting a second query stem to the autocompletion module to obtain second query autocompletions, the second query stem being the first query stem with a prefix removed;

receiving, from the autocompletion module, one or more second query autocompletions satisfying a second quality test, wherein the second quality test includes determining a ratio of a number of times a potential autocompletion occurs in a corpus of user queries to a number of times any query that includes the second query stem occurs in the corpus user queries, and comparing the ratio to a threshold value; and

providing one or more second query autocompletions for presentation on the user interface.

5. The system of claim 4, wherein the second quality test further comprises applying a smoothing factor to the ratio.

6. The system of claim 4, the operation further comprising:

determining the prefix, wherein determining the prefix comprises;

assigning a query term of the multiple query terms to the prefix;

determining the query term is part of a compound word; and

assigning a second part of the compound word to the prefix.

7. A non-transitory computer storage medium encoded with a computer program, the computer program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving a query input in a search engine query input field in a user interface, before receiving an input expressly submitting the query input as a query to a search engine, the query input comprising multiple query terms;

submitting the query input as a first query stem to an autocompletion module to obtain first query autocompletions;

determining that the first query autocompletions do not satisfy a first quality test, and, in response, submitting a second query stem to the autocompletion module to obtain second query autocompletions, the second query stem being the first query stem with a prefix removed;

receiving, from the autocompletion module, one or more second query autocompletions satisfying a second quality test, wherein the second quality test includes determining a ratio of a number of times a potential autocompletion occurs in a corpus of user queries to a number of times any query that includes the second query stem occurs in the corpus user queries, and comparing the ratio to a threshold value; and

providing the one or more second query autocompletions for presentation on the user interface.

8. The computer storage medium of claim 7, wherein the second quality test further comprises applying a smoothing factor to the ratio.

9. The computer storage medium of claim 7, the operations further comprising:

determining the prefix, wherein determining the prefix comprises;

assigning a query term of the multiple query terms to the prefix;

determining the query term is part of a compound word; and

assigning a second part of the compound word to the prefix.

10. A computer-implemented method comprising:

receiving a query input in a search engine query input field in a user interface, before receiving an input expressly submitting the query input as a query to a search engine, the query input comprising multiple query terms;

submitting the query input as a first query stem to an autocompletion module to obtain first query autocompletions;

determining that the first query autocompletions do not satisfy a first quality test, and, in response, submitting one or more shortened query stems to the autocompletion module to obtain shortened query autocompletions, each shortened query stem being the first query stem with one or more query terms removed;

receiving from the autocompletion module, one or more shortened query autocompletions satisfying a second quality test, wherein the second quality test includes determining a ratio of a number of times a potential autocompletion occurs in a corpus of user queries to a number of times any query that includes the shortened query stem occurs in the corpus user queries, and comparing the ratio to a threshold value;

collecting the shortened query autocompletions; and

providing the shortened query autocompletions for presentation on the user interface.