Search query autocompletion

• US 6,564,213 B1
• Filed: 04/18/2000
• Issued: 05/13/2003
• Est. Priority Date: 04/18/2000
• Status: Active Grant

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: Amazon.com, Inc.
• Inventors: Frederick, Robert, Avery, John W., Ortega, Ruben E.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/551,787
• Time in Patent Office: 1,120 Days
• Field of Search: 707/1-10, 707/100, 707/102, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A system for facilitating online searches suggests query autocompletion strings (terms and/or phrases) to users during the query entry process, wherein the suggested strings are based on specific attributes of the particular database access system being searched. A string extraction component associated with a database access system, such as a web site of an online merchant, periodically generates a dataset that contains the autocompletion strings for the system. The datasets are preferably biased to favor the database items that are currently the most popular (e.g., best selling or most frequently viewed), and may be customized to particular users or user groups. The datasets are transmitted to users'"'"' computing devices, which may include handheld and other wireless devices that lack a full keyboard. An autocompletion client which runs on the computing devices in association with a browser uses the datasets to suggest the autocompletion strings as users enter queries that are directed to the database access system.

Claims

1. A method of assisting users in generating queries for submission to a query server of a database access system, comprising:

generating a dataset that contains autocompletion strings for the query server, wherein the autocompletion strings are selected based on attributes of the database access system;

transmitting the dataset to a remote computing device of a user of the database access system; and

on the remote computing device, suggesting autocompletion strings to the user from the dataset as the user enters a query for submission to the query server;

wherein the dataset is generated remotely from the remote computing device.

2. The method as in claim 1, wherein the computing device is a wireless device that lacks a full keyboard.

3. The method as in claim 1, wherein the attributes comprise a history of query submissions submitted to the query server by a plurality of users.

4. The method as in claim 3, wherein generating the dataset comprises extracting the autocompletion strings from a query log that reflects query submissions from each of a plurality of user computing devices.

5. The method as in claim 4, wherein extracting the autocompletion strings from the query log comprises selecting search terms and/or search phrases from the query log based at least upon frequency of submission.

6. The method as in claim 4, wherein extracting the autocompletion strings from the query log comprises ignoring query submissions that produced a null query result.

7. The method as in claim 4, wherein extracting the autocompletion strings from the query log comprises extracting the strings from a most recent set of the query log data so that the autocompletion strings reflect current interest of users.

8. The method as in claim 1, wherein the attributes comprise items stored within a database of the database access system.

9. The method as in claim 8, wherein generating the dataset comprises extracting the autocompletion strings from item descriptions within the database.

10. The method as in claim 8, wherein generating the dataset comprises identifying a subset of the items within the database based on selected criteria, and extracting the autocompletion strings from item descriptions of the subset of items.

11. The method as in claim 1, wherein generating a dataset that contains autocompletion strings comprises generating a plurality of datasets, wherein each dataset corresponds to a different group of users, and wherein the method further comprises transmitting the datasets to users based on group memberships.

12. The method as in claim 11, wherein generating the plurality of datasets comprises generating datasets for each of a plurality of geographic regions based at least in part on activities of users within such regions.

13. The method as in claim 1, further comprising customizing the dataset to the user prior to transmission to the computing device.

14. The method as in claim 1, further comprising submitting a suggested autocompletion string to the query server in response to the user performing a single selection action with respect to the string, without requiring the user to perform an additional action.

15. The method as in claim 1, wherein suggesting the autocompletion strings to the user comprises selecting autocompletion strings to display based at least upon a search context specified by the user.

16. The method as in claim 1, wherein transmitting the dataset to a remote computing device comprises transmitting at least a portion of the dataset with a corresponding search page.

17. The method as in claim 1, wherein suggesting autocompletion strings to the user comprises suggesting the autocompletion strings as the user enters a query by voice.

18. The method of claim 1, further comprising transmitting the dataset to each of a plurality of additional remote computing devices, and on each of the additional remote computing devices, suggesting autocompletion strings from the dataset to a user during search query entry.

19. A search engine system that embodies the method of claim 1.

20. A system for assisting users in generating search queries for submission to a query server of a database access system, comprising:

a first component that extracts autocompletion strings from at least one of the following sources (a) a log of queries submitted to the query server by a plurality of users, and (b) descriptions of items stored within a database of the database access system;

a second component that dispatches the autocompletion strings extracted by the first component to computing devices of users of the database access system; and

a third component that runs on the computing devices and suggests the autocompletion strings to users as the users enter search queries for submission to the query server of the database access system.

21. The system as in claim 20, wherein the third component runs on a wireless computing device that lacks a full keyboard.

22. The system as in claim 21, wherein the third component suggests autocompletion strings in response to entry of queries by voice.

23. The system as in claim 20, wherein the first component extracts the autocompletion strings so as to generally favor the most popular items within the database.

24. The system as in claim 20, wherein the first component extracts query strings from the query log based at least upon frequency of string submission.

25. The system as in claim 20, wherein the first component extracts autocompletion strings from descriptions of items within the database based at least upon item popularity data.

26. The system as in claim 20, wherein the first component extracts the autocompletion strings periodically based at least upon a most recent set of user activity data.

27. The system as in claim 20, wherein the first component generates customized datasets of autocompletion strings for each of a plurality of subsets of a population of users.

28. The system as in claim 20, wherein the second component transmits at least some of the extracted autocompletion strings to computing devices with a search page to which the autocompletion strings correspond.

29. The system as in claim 20, wherein the third component automatically submits a suggested autocompletion string to the query server in response to a user performing a single selection action with respect to the string, without requiring the user to perform a further action.

30. A method of assisting a user in generating a query to submit to a query server, comprising, on a computing device:

retrieving a dataset of autocompletion strings from a server, wherein at least a portion of the dataset corresponds to the query server;

storing the dataset in a memory of the computing device; and

in response to entry by a user of a search query for submission to the query server, suggesting autocompletion strings from the dataset to the user.

31. The method as in claim 30, wherein the dataset is retrieved in response to user retrieval of a search page that corresponds to the query server.

32. The method as in claim 30, wherein the computing device is a wireless device that lacks a full keyboard.

33. The method as in claim 30, wherein the autocompletion strings are suggested in response to voice entry by the user of the search query.

34. The method as in claim 30, further comprising transmitting a suggested autocompletion string to the query server in response to the user performing a single selection action with respect to the string, without requiring the user to perform a further action.

35. The method as in claim 34, wherein the single selection action is one of the following:

(a) clicking once on the suggested string, (b) tapping once on the suggested string, (c) clicking twice on the suggested string, or (d) tapping twice on the suggested string.

36. The method as in claim 30, wherein suggesting autocompletion strings comprises selecting strings from the dataset based at least upon a search context specified by the user.

37. An autocompletion client component that embodies the method of claim 30.

38. A search engine system, comprising:

a multi-user query processing system that maintains a log of search queries submitted by users of the query processing system, said search queries including search strings;

a first component that analyses the log to identify search strings that are deemed to be useful as search query autocompletion strings, and which incorporates selected search strings into a dataset of autocompletion strings; and

a second component that monitors entry by a user of a search query, and during said entry, suggests corresponding autocompletion strings to the user from the dataset of autocompletion strings to assist the user in entering the search query.

39. The search engine system as in claim 38, wherein the second component runs on a user computing device, remotely from the first component.

40. The search engine system as in claim 38, wherein the second component is adapted to run on a wireless computing device, and is adapted to received the dataset of autocompletion strings from a server over a wireless link.

41. The search engine system as in claim 38, wherein the first component implements a search string scoring algorithm to assign scores to search strings.

42. The search engine system as in claim 41, wherein the search string scoring algorithm scores a search string based at least in-part upon a frequency with which the search string has been submitted by users over a selected period of time.

43. The search engine system as in claim 41, wherein the search string scoring algorithm scores a search string based at least in-part upon post-query-submission actions performed by users who submitted the search string, said post-query-submission actions comprising user actions performed with respect to search result items.

44. The search engine system as in claim 41, wherein the first component incorporates scores generated by the search string scoring algorithm into the dataset, and second component uses the scores to select autocompletion strings from the dataset to suggest.

45. The search engine system as in claim 38, wherein the first component incorporates search context information into dataset, and the second component uses the search context information to select autocompletion strings that correspond to a search context of the search query.

46. The search engine system as in claim 38, wherein the first component additionally incorporates into the dataset autocompletion strings selected from searchable items.

47. A method of facilitating the formulation of search queries, the method comprising:

maintaining a log of search queries submitted to a multi-user query server by users thereof, said search queries including search strings;

selecting a plurality of the search strings from the log based on search string selection criteria;

incorporating the plurality of search strings into a dataset of autocompletion strings; and

dispatching the dataset of autocompletion strings to each of a plurality of user devices that are adapted to suggest autocompletion strings therefrom to users during entry of search queries.

48. The method claim 47 wherein the plurality of search strings are selected based at least in-part upon relative frequencies of search string submission.

49. The method of claim 47, wherein the plurality of search strings are selected based at least in-part upon numbers of search result items produced by corresponding searches.

50. The method of claim 47, wherein the plurality of search strings are selected based at least in-part upon an analysis of post-query-submission user actions performed with respect to items located by corresponding search queries.

51. The method of claim 47, wherein dispatching the dataset of autocompletion strings to each of a plurality of user devices comprises transmitting the dataset over a wireless link to at least one user device.

52. The method of claim 47, wherein dispatching the dataset of autocompletion strings comprises sending the dataset to a user device with a corresponding search page.

53. The method of claim 47, wherein the log includes queries submissions from each of a plurality of user computing devices.

54. A method of facilitating user searches of a database, comprising:

transmitting a search page from a server to a computing device of a user together with an associated dataset of autocompletion strings, said search page including a field for entering a search query for submission to a query server;

on the computing device, monitoring entry by the user of a search query into the field of the search page; and

during said entry of the search query, suggesting at least one autocompletion string of the dataset to the user to assist the user, in completing the search query.

55. The method of claim 54, further comprising generating the dataset at least in-part by selecting search strings from a record of search queries submitted by users of the query server.

56. The method of claim 54, further comprising, in response to selection by the user of a suggested autocompletion string, submitting the autocompletion string to the query server without requiring further user action, whereby the user can both select an autocompletion string and submit a search query with a single selection action.