Query suggestions from documents

• US 9,098,568 B2
• Filed: 08/04/2009
• Issued: 08/04/2015
• Est. Priority Date: 08/04/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Li, Youlin, Hsu, Goang-Tay, Lin, Linda Lin
• Primary Examiner(s): LE, HUNG D
• Application Number:
  US13/388,728
• Publication Number:
  US 20120130978A1
• Time in Patent Office: 2,191 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/248 Presentation of query results
• 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/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Methods, systems, and apparatus, including computer program products, for presenting search query suggestions. In an aspect, query triggers in a resource are identified at a client device. For each query trigger identified in the resource, a rank score for the query trigger based on query trigger attributes is calculated at the client device. The query triggers are ranked at the client device based on the rank scores. Search query suggestions are generated at the client device from the query triggers identified in the resource. The search query suggestions include terms of the query triggers, expansion terms of the query triggers, and search query suggestions generated from templates applied to the terms of the query triggers and expansion terms of the query triggers. The search query suggestions are presented at the client device according to the rank of the corresponding query triggers.

Claims

1. A computer-implemented method, comprising:

receiving at a client device a dictionary defining query triggers, each of the query triggers being one or more terms;

identifying at the client device query triggers in a resource, the resource being a non-query resource;

for each query trigger identified in the resource, calculating at the client device a rank score for the query trigger based on attributes of the query trigger, the attributes including at least one of;

a context of the query trigger defined by a display format of the query trigger in the resource; and

a frequency of occurrence of the query trigger in the resource;

ranking at the client device the query triggers according to the rank scores;

generating at the client device search query suggestions from the query triggers identified in the resource; and

presenting at the client device the search query suggestions according to the ranking of the query triggers.

2. The computer-implemented method of claim 1, wherein:

the query triggers include expansion terms, the expansion terms for each query trigger being terms that are query expansions of the one or more terms of the query trigger;

identifying the query triggers in the resource comprises searching the resource for the query triggers included in the dictionary; and

generating search query suggestions from the query triggers comprises generating for a query trigger identified in the resource a search query that includes an expansion term of the query trigger.

3. The computer-implemented method of claim 2, wherein:

the dictionary of query triggers includes query templates associated with the query triggers, each query template associated with a query trigger and including a variable and string, the variable corresponding to one or more terms of the query trigger and the expansion terms of the query trigger, and the string defining one or more additional terms different from one or more terms of the query trigger and the expansion terms of the query trigger; and

generating search query suggestions from the query triggers comprises;

selecting a query template associated with a query trigger;

using one of the query trigger or expansion terms of the query trigger as an argument for the variable of the selected query template; and

generating the search query suggestion from the argument and the string.

4. The computer-implemented method of claim 2, wherein the one or more terms of the query triggers define entity names, the entity names being names of persons and names of places.

5. The computer-implemented method of claim 1, wherein presenting at the client device the search query suggestions according to the ranking of the query triggers comprises:

sequentially presenting each of search query suggestions for a predefined time period in a toolbar of a web browser displaying the resource.

6. The computer-implemented method of claim 1, wherein:

the attributes of the query trigger further include a popularity score of the query trigger, the popularity score stored in the dictionary and being a measure of a popularity of the query trigger as a query for multiple users of a search engine; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, a length of the query trigger, and the popularity of the query trigger.

7. The computer-implemented method of claim 6, wherein each of the one or more terms of the query triggers are queries received from users of the search system and have a popularity score exceeding a minimum popularity threshold.

8. The computer-implemented method of claim 1, wherein:

the attributes of the query trigger further include a query history score of the query trigger, the query history score stored in the dictionary and being a measure of a selection of a suggested query generated from the query trigger for multiple users of a search engine; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, a length of the query trigger, and the query history score of the query trigger.

9. The computer-implemented method of claim 1, further comprising:

storing client history data at the client device, the client history data storing a search history that includes queries provided to a search engine from the client device;

calculating a client history score for query triggers identified in the resource; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, a length of the query trigger, and the client history score of the query trigger.

10. The computer-implemented method of claim 1, further comprising rendering the resource in a first thread of a browser application at the client device;

and

wherein identifying the query triggers in the resource comprises identifying the query triggers in a second thread of a browser application, the second thread independent of the first thread.

11. The computer-implemented method of claim 1, wherein the attributes include the context of the query trigger and include the frequency of occurrence of the query trigger.

12. A system, comprising:

a data processing apparatus; and

a computer-readable storage medium coupled to the data processing apparatus and storing a dictionary defining query triggers, each of the query triggers being one or more terms;

wherein the computer-readable medium also stores instructions that, when executed by the data processing apparatus, cause the data processing apparatus to perform operations comprising;

identifying query triggers in a resource displayed in a web browser application environment on the data processing apparatus, wherein the resource is a non-query resource;

for each query trigger identified in the resource, calculating a rank score for the query trigger based on attributes of the query trigger, the attributes including at least one of;

a context of the query trigger defined by a display format of the query trigger in the resource; and

a frequency of occurrence of the query trigger in the resource;

ranking the query triggers according to the rank scores;

generating search query suggestions from the query triggers identified in the resource; and

presenting the search query suggestions in the web browser application environment according to the ranking of the query triggers.

13. The system of claim 12, wherein:

the query triggers include expansion terms, the expansion terms for each query trigger being terms that are query expansions of the one or more terms of the query trigger; and

identifying the query triggers in the resource comprises searching the resource for the query triggers included in the dictionary; and

generating search query suggestions from the query triggers comprises generating for a query trigger identified in the resource a search query that includes an expansion term of the query trigger.

14. The system of claim 13, wherein:

the dictionary of query triggers includes query templates associated with the query triggers, each query template associated with a query trigger and including a variable and string, the variable corresponding to one or more terms of the query trigger and the expansion terms of the query trigger, and the string defining one or more additional terms different from one or more terms of the query trigger and the expansion terms of the query trigger; and

generating search query suggestions from the query triggers comprises;

selecting a query template associated with a query trigger;

using one of the query trigger or expansion terms of the query trigger as an argument for the variable of the selected query template; and

generating the search query suggestion from the argument and the string.

15. The system of claim 13, wherein the one or more terms of the query triggers define entity names, the entity names being names of persons and names of places.

16. The system of claim 12, wherein presenting at the client device the search query suggestions according to the ranking of the query triggers comprises:

sequentially presenting each of search query suggestions for a predefined time period in a toolbar of a web browser displaying the resource.

17. The system of claim 12, wherein:

the attributes of the query trigger further include a popularity score of the query trigger, the popularity score stored in the dictionary and being a measure of a popularity of the query trigger as a query for multiple users of a search engine; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, a length of the query trigger, and the popularity of the query trigger;

wherein each of the one or more terms of the query triggers are queries received from users of the search system and have a popularity score exceeding a minimum popularity threshold.

18. The system of claim 12, wherein:

the attributes of the query trigger further include a history score of the query trigger, the history score stored in the dictionary and being a measure of a selection of a suggested query generated from the query trigger for multiple users of a search engine; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, a length of the query trigger, and the history score of the query trigger.

19. The system of claim 12, further comprising rendering the resource in a first thread of a browser application at the client device;

and

wherein identifying the query triggers in the resource comprises identifying the query triggers in a second thread of a browser application, the second thread independent of the first thread.

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

receiving at a client device a dictionary defining query triggers, each of the query triggers being one or more terms and having a popularity score stored in the dictionary, the popularity score being a measure of a popularity of the query trigger as a query for multiple users of a search engine;

rendering a resource in a web browser application on the client device, wherein the resource is a non-query resource;

in response to rendering the resource in the web browser application, identifying at the client device query triggers in the resource;

for each query trigger identified in the resource, calculating at the client device a rank score for the query trigger based on attributes of the query trigger and the popularity score of the query trigger, the attributes including at least one of;

a context of the query trigger defined by a display format of the query trigger in the resource; and

a frequency of occurrence of the query trigger in the resource;

ranking at the client device the query triggers according to the rank scores;

generating at the client device search query suggestions from the query triggers identified in the resource; and

presenting in the web browser application the search query suggestions with the rendered resource and according to the ranking of the query triggers.

21. A system, comprising:

a data processing apparatus; and

a computer-readable storage medium coupled to the data processing apparatus, the computer-readable medium storing instructions that, when executed by the data processing apparatus, cause the data processing apparatus to perform operations comprising;

sending to a client device a dictionary defining query triggers, each of the query triggers being one or more terms;

sending to the client device a module executable by the client device and upon execution causes the client device to perform operations comprising;

identify at the client device query triggers in a resource, the resource being a non-query resource;

for each query trigger identified in the resource, calculating at the client device a rank score for the query trigger based on attributes of the query trigger, the attributes including at least one of;

a context of the query trigger defined by a display format of the query trigger in the resource; and

a frequency of occurrence of the query trigger in the resource;

rank at the client device the query triggers according to the rank scores;

generate at the client device search query suggestions from the query triggers identified in the resource; and

present at the client device the search query suggestions according to the ranking of the query triggers.

22. The system of claim 21, wherein:

the query triggers include expansion terms, the expansion terms for each query trigger being terms that are query expansions of the one or more terms of the query trigger;

identify at the client device the query triggers in the resource comprises search the resource for the query triggers included in the dictionary; and

generate at the client device search query suggestions from the query triggers comprises generate for a query trigger identified in the resource a search query that includes an expansion term of the query trigger.

23. A computer-implemented method, comprising:

receiving at a client device a dictionary defining query triggers, each of the query triggers being one or more terms;

identifying at the client device query triggers in a resource, the resource being a non-query resource, and the identifying including searching the resource for the query triggers in response to the resource being currently or recently accessed at the client device by a user;

for each query trigger identified in the resource, calculating at the client device a rank score for the query trigger based on attributes of the query trigger wherein the attributes of the query trigger include one or more of;

a context of the query trigger defined by a display format of the query trigger in the resource;

a frequency of occurrence of the query trigger in the resource; and

a length in characters of the query trigger; and

wherein calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of one or more of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger;

ranking at the client device the query triggers according to the rank scores;

generating at the client device search query suggestions from the query triggers identified in the resource; and

presenting at the client device the search query suggestions according to the ranking of the query triggers.

24. The computer-implemented method of claim 23, wherein:

the query triggers include expansion terms, the expansion terms for each query trigger being terms that are query expansions of the one or more terms of the query trigger;

identifying the query triggers in the resource comprises searching the resource for the query triggers included in the dictionary; and

generating search query suggestions from the query triggers comprises generating for a query trigger identified in the resource a search query that includes an expansion term of the query trigger.

25. The computer-implemented method of claim 24, wherein:

the dictionary of query triggers includes query templates associated with the query triggers, each query template associated with a query trigger and including a variable and string, the variable corresponding to one or more terms of the query trigger and the expansion terms of the query trigger, and the string defining one or more additional terms different from one or more terms of the query trigger and the expansion terms of the query trigger; and

generating search query suggestions from the query triggers comprises;

selecting a query template associated with a query trigger;

using one of the query trigger or expansion terms of the query trigger as an argument for the variable of the selected query template; and

generating the search query suggestion from the argument and the string.

26. The computer-implemented method of claim 23, wherein:

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger.

27. The computer-implemented method of claim 23, further comprising:

storing client history data at the client device, the client history data storing a search history that includes queries provided to a search engine from the client device;

calculating a client history score for query triggers identified in the resource; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the client history score of the query trigger and one or more of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger.

28. The computer-implemented method of claim 23, wherein the resource is a webpage and the identifying includes searching the webpage for the query triggers in response to the webpage being currently browsed at the client device.

29. The computer-implemented method of claim 23, wherein the attributes include the context of the query trigger, include the frequency of occurrence of the query trigger, and include the length of the query trigger.

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

receiving at a client device a dictionary defining query triggers, each of the query triggers being one or more terms;

in response to rendering a webpage at the client device, searching the webpage for the query triggers;

for each query trigger identified in the webpage, calculating at the client device a rank score for the query trigger based on attributes of the query trigger wherein the attributes of the query trigger include one or more of;

a context of the query trigger defined by a display format of the query trigger in the resource;

a frequency of occurrence of the query trigger in the resource; and

a length in characters of the query trigger; and

wherein calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of one or more of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger;

ranking at the client device the query triggers according to the rank scores;

generating at the client device search query suggestions from the query triggers identified in the resource; and

presenting at the client device the search query suggestions according to the ranking of the query triggers.

31. The computer storage medium of claim 30, wherein:

the query triggers include expansion terms, the expansion terms for each query trigger being terms that are query expansions of the one or more terms of the query trigger; and

identifying the query triggers in the resource comprises searching the resource for the query triggers included in the dictionary; and

generating search query suggestions from the query triggers comprises generating for a query trigger identified in the resource a search query that includes an expansion term of the query trigger.

32. The computer storage medium of claim 31, wherein:

the dictionary of query triggers includes query templates associated with the query triggers, each query template associated with a query trigger and including a variable and string, the variable corresponding to one or more terms of the query trigger and the expansion terms of the query trigger, and the string defining one or more additional terms different from one or more terms of the query trigger and the expansion terms of the query trigger; and

generating search query suggestions from the query triggers comprises;

selecting a query template associated with a query trigger;

using one of the query trigger or expansion terms of the query trigger as an argument for the variable of the selected query template; and

generating the search query suggestion from the argument and the string.

33. The computer storage medium of claim 30, wherein:

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger.

34. The computer storage medium of claim 30, wherein the instructions further comprise instructions that when executed by the data processing apparatus cause the data processing apparatus to perform operations comprising:

storing client history data at the client device, the client history data storing a search history that includes queries provided to a search engine from the client device;

calculating a client history score for query triggers identified in the resource; and

calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of the client history score of the query trigger and one or more of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger.

35. A system, comprising:

a data processing apparatus; and

a computer-readable storage medium coupled to the data processing apparatus, the computer-readable medium storing instructions that, when executed by the data processing apparatus, cause the data processing apparatus to perform operations comprising;

sending to a client device a dictionary defining query triggers, each of the query triggers being one or more terms;

sending to the client device a module executable by the client device and upon execution causes the client device to perform operations comprising;

identifying at the client device query triggers in a resource, the resource being a non-query resource, and the identifying including searching the resource for the query triggers in response to the resource being currently or recently accessed at the client device by a user;

for each query trigger identified in the resource, calculating at the client device a rank score for the query trigger based on attributes of the query trigger wherein the attributes of the query trigger include one or more of;

a context of the query trigger defined by a display format of the query trigger in the resource;

a frequency of occurrence of the query trigger in the resource; and

a length in characters of the query trigger; and

wherein calculating at the client device a rank score for the query trigger based on attributes of the query trigger comprises generating the rank score based on a function of one or more of the context of the query trigger, the frequency of occurrence of the query trigger, and the length of the query trigger;

ranking at the client device the query triggers according to the rank scores;

generating at the client device search query suggestions from the query triggers identified in the resource; and

presenting at the client device the search query suggestions according to the ranking of the query triggers.