Interactive search querying

• US 8,204,897 B1
• Filed: 09/09/2009
• Issued: 06/19/2012
• Est. Priority Date: 09/09/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Djabarov, Gueorgui N., Harper, Alex B., Jitkoff, John Nicholas, Tabone, Ryan C., Morgan, Stuart B., MacLachlan, David I., Pinkerton, Michael D.
• Primary Examiner(s): Le, Thu-Nguyet
• Application Number:
  US12/556,457
• Time in Patent Office: 1,014 Days
• Field of Search: 707756-768
• US Class Current: 707/767
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results

Abstract

The subject matter of this specification can be implemented in, among other things, a computer-implemented method including receiving from a user a portion of a query. The method further includes providing the portion of the query to multiple data provider modules nearly simultaneously. The method further includes receiving, from ones of the data provider modules, a set of search suggestion items resulting from searching the data sources, each of the search suggestion items including a rank and a relevance value. The method further includes determining a score for each of the search suggestion items by combining the rank and the relevance value for each of the search suggestion items. The method further includes sorting the search suggestion items using the scores. The method further includes presenting the sorted search suggestion items to the user.

Claims

1. A computer-implemented method, comprising:

receiving from a user, through a user interface of a search application at a computing device, a portion of a query that is less than a complete query;

providing the portion of the query to multiple data provider modules nearly simultaneously, each of the data provider modules able to search at least one data source using the portion of the query;

receiving, from ones of the data provider modules, a set of search suggestion items resulting from searching the data sources, each of the search suggestion items including a rank value and a relevance value, each of the rank values indicating a frequency for which the corresponding search suggestion item has been previously accessed, and each of the relevance values indicating a level of match between the portion of the query and the corresponding search suggestion item;

determining a score for each of the search suggestion items by multiplying the rank value and the relevance value for each of the search suggestion items;

sorting the search suggestion items using the scores; and

sending the sorted search suggestion items for presentation to the user.

2. The method of claim 1, wherein the frequency for which the corresponding search suggestion item has been previously accessed is determined over a prior predetermined time interval.

3. The method of claim 1, wherein the relevance values are numbers in a range from zero to one, and wherein a relevance value of zero indicates no match and a relevance value of one indicates a complete match.

4. The method of claim 1, wherein the search suggestion items received from the data provider modules each further comprise an identifier selected from the group consisting of a web page address, a file path, and a contact name.

5. The method of claim 4, further comprising comparing the identifiers of the search suggestion items and removing from the sorted search suggestion items one or more of the search suggestion items having duplicate identifiers.

6. The method of claim 5, wherein removing the one or more search suggestion items having the duplicate identifiers includes removing the one or more search suggestion items having lowest scores and having the duplicate identifiers.

7. The method of claim 1, further comprising storing, for each of the search suggestion items, an indication of a frequency with which the user selects the search suggestion items and combining the indication with the rank value for each of the search suggestion items before multiplying the rank values and the relevance values.

8. The method of claim 7, further comprising resetting the frequency, for each of the search suggestion items, at a reset time interval.

9. The method of claim 1, wherein providing the portion of the query to the data provider modules includes providing the portion of the query to a menu data provider module that searches a data source that includes menu items from one or more applications at the computing device that are external to the search application.

10. The method of claim 9, wherein receiving, from ones of the data provider modules, the sets of search suggestion items resulting from searching the data sources includes receiving from the menu data provider a set of search suggestion items that include one or more of the menu items of the applications that are external to the search application.

11. The method of claim 10, wherein the one or more applications that are external to the search application include a foreground application.

12. The method of claim 10, wherein the one or more applications that are external to the search application include open applications.

13. The method of claim 10, wherein the one or more applications that are external to the search application include an operating system.

14. The method of claim 1, wherein providing the portion of the query to the data provider modules includes providing the portion of the query to a web browser data provider module that searches a data source that includes queries performed in one or more web browser applications that are external to the search application.

15. The method of claim 14, wherein receiving, from ones of the data provider modules, the sets of search suggestion items resulting from searching the data sources includes receiving from the web browser data provider a set of search suggestion items that include one or more of the queries performed in the web browser applications that are external to the search application.

16. The method of claim 1, wherein providing the portion of the query to the data provider modules includes providing the portion of the query to a file data provider module that searches a data source that includes one or more files currently open in an application that is external to the search application.

17. The method of claim 16, wherein receiving, from ones of the data provider modules, the sets of search suggestion items resulting from searching the data sources includes receiving from the file data provider a set of search suggestion items that include contents from the one or more files currently open in the application that is external to the search application.

18. The method of claim 1, wherein sending the sorted search suggestion items for presentation to the user includes presenting a predetermined number of the search suggestion items having the highest scores.

19. The method of claim 1, further comprising grouping the search suggestion items into categories and wherein sending the sorted search suggestion items for presentation to the user includes presenting the groups of sorted search suggestion items to the user.

20. The method of claim 1, further comprising receiving from the user, through the computing device, an input including a restriction condition for the search suggestion items and restricting the search suggestion items to one or more of the search suggestion items that have a relationship with the restriction condition.

21. A non-transitory computer-readable medium storing software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

receiving from a user, through a user interface of a search application at a computing device, a portion of a query that is less than a complete query;

providing the portion of the query to multiple data provider modules nearly simultaneously, each of the data provider modules able to search at least one data source using the portion of the query;

receiving, from ones of the data provider modules, a set of search suggestion items resulting from searching the data sources, each of the search suggestion items including a rank value and a relevance value, each of the rank values indicating a frequency for which the corresponding search suggestion item has been previously accessed, and each of the relevance values indicating a level of match between the portion of the query and the corresponding search suggestion item;

determining a score for each of the search suggestion items by multiplying the rank value and the relevance value for each of the search suggestion items;

sorting the search suggestion items using the scores; and

sending the sorted search suggestion items for presentation to the user.

22. The medium of claim 21, wherein the frequency for accessing the corresponding search suggestion item is determined over a prior predetermined time interval.

23. The medium of claim 21, wherein the frequency for which the corresponding search suggestion item has been previously accessed is computed as a function that weights accesses lower the farther in the past they occurred.

24. The medium of claim 21, wherein the actions further comprise comparing the identifiers of the search suggestion items and removing from the sorted search suggestion items one or more of the search suggestion items having duplicate identifiers.

25. A computer-implemented 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 from a user, through a user interface of a search application at a computing device, a portion of a query that is less than a complete query;

providing the portion of the query to multiple data provider modules nearly simultaneously, each of the data provider modules able to search at least one data source using the portion of the query;

receiving, from ones of the data provider modules, a set of search suggestion items resulting from searching the data sources, each of the search suggestion items including a rank value and a relevance value, each of the rank values indicating a frequency for which the corresponding search suggestion item has been previously accessed, and each of the relevance values indicating a level of match between the portion of the query and the corresponding search suggestion item;

determining a score for each of the search suggestion items by multiplying the rank value and the relevance value for each of the search suggestion items;

sorting the search suggestion items using the scores; and

sending the sorted search suggestion items for presentation to the user.

26. The system of claim 25, wherein the user interface or the data provider module is programmed to convert the portion of the query into a revised form before providing the portion of the query to the data provider modules.