Generating suggested search queries

• US 9,098,569 B1
• Filed: 12/10/2010
• Issued: 08/04/2015
• Est. Priority Date: 12/10/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Bhagat, Rahul H.
• Primary Examiner(s): Obisesan, Augustine K
• Application Number:
  US12/965,476
• Time in Patent Office: 1,698 Days
• 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/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• 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
• CPC Class Codes: G06F 16/9558 Details of hyperlinks; Management of linked annotations
• CPC Class Codes: G06Q 30/0256 User search
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A user supplied search query is received. Historical search queries are identified that are relevant and/or similar to the user supplied search query. The identified historical queries are then ranked according to various factors. Suggested search queries that are relevant to the user supplied query are identified.

Claims

1. A non-transitory computer-readable medium embodying a program executable in a computing device, the program comprising:

code that receives a user supplied search query, the user supplied search query comprising a plurality of search terms;

code that removes at least one of the search terms from the user supplied search query to generate a plurality of resultant search queries;

code that determines whether individual ones of the resultant search queries comprise same search terms as a respective historical search query in a data store accessible to the computing device that is associated with at least one search result in the data store;

code that identifies a plurality of search results associated with individual ones of the plurality of resultant search queries;

code that determines whether individual ones of the plurality of search results match the at least one search result in the data store associated with the respective historical search query;

code that identifies the respective historical search query as being relevant to the user supplied search query by executing at least one relevance function and at least one similarity function against an index of the respective historical search queries with the user supplied search query, wherein the at least one relevance function comprises a phrase level edit distance comparison of the user supplied search query to the respective historical search query and the at least one similarity function is a cosine similarity, jaccad similarity, or a dice similarity;

code that generates a ranking of the respective historical search queries according to a number of the at least one search result in the data store associated with the respective historical search query that match individual ones of the plurality of search results, wherein a first respective historical search query associated with a higher number of the at least one search result in the data store associated with the respective historical search query that match individual ones of the plurality of search results is ranked higher than a second respective historical search query associated with a lower number of the at least one search result in the data store associated with the respective historical search query that match individual ones of the plurality of search results; and

code that generates a user interface displaying the respective historical search queries in an order according to the ranking.

2. The non-transitory computer-readable medium of claim 1, wherein the code that generates the user interface displaying the respective historical search queries further comprises code that generates a hyperlink associated with individual ones of the respective historical search queries.

3. A system, comprising:

at least one of one or more computing devices; and

a search application executable via at least one of the one or more computing devices, the search application comprising;

logic that determines whether a search query is associated with at least one product in a product catalog, the search query comprising a plurality of search terms;

logic that removes a search term among the plurality of search terms from the search query to generate a plurality of resultant search queries;

logic that identifies a plurality of search results associated with the plurality of resultant search queries;

logic that determines whether individual ones of the resultant search queries match at least one respective historical search query in a data store that is associated with a plurality of historical search results in the data store;

logic that determines whether individual ones of the plurality of search results match individual ones of the plurality of historical search results;

logic that identifies the at least one respective historical search query that is relevant to the search query by generating a ranking of the at least one historical search query according to a number of individual ones of the plurality of historical search results that match individual ones of the plurality of search results, wherein a first historical search query associated with a higher number of individual ones of the plurality of historical search results that match individual ones of the plurality of search results is ranked higher than a second historical search query associated with a lower number of individual ones of the plurality of historical search results that match individual ones of the plurality of search results, and executing at least one relevance function and at least one similarity function against an index of the at least one historical search query with the search query, wherein the at least one relevance function comprises a phrase level edit distance comparison of the search query and the at least one respective historical search query and the at least one similarity function is a cosine similarity, jaccad similarity, or a dice similarity; and

logic that generates a user interface comprising at least one search result associated with the at least one respective historical search query according to the ranking.

4. The system of claim 3, wherein the logic that identifies the at least one respective historical search query that is relevant to the search query further comprises:

logic that identifies a subset of the historical search queries submitted by users over a predetermined period of time; and

logic that indexes the subset of the historical search queries in the index.

5. The system of claim 3, wherein the logic that identifies the at least one respective historical search query that is relevant to the search query further comprises:

logic that generates the ranking of the at least one respective historical search query according to a number of products with which the at least one respective historical search query is associated.

6. The system of claim 5, wherein the logic that generates the user interface comprising the at least one search result associated with the at least one respective historical search query further comprises logic that encodes for display the at least one respective historical search query in an order according to the ranking.

7. The system of claim 5, wherein the logic that generates the user interface comprising the at least one search result associated with the at least one respective historical search query further comprises:

logic that encodes for display a subset of the at least one search result associated with the at least one respective historical search query in the user interface; and

logic that encodes for display a historical search query hyperlink, the historical search query hyperlink linking to a search result user interface displaying the at least one search result associated with the at least one hyperlink.

8. The system of claim 3, wherein the logic that identifies the at least one respective historical search query that is relevant to the search query further comprises:

logic that generates the ranking of the at least one respective historical search query according to a conversion rate of the at least one respective historical search query, the conversion rate being a rate at which the at least one product associated with the at least one respective historical search query is purchased.

9. The system of claim 3, wherein the logic that identifies the at least one respective historical search query that is relevant to the search query further comprises:

logic that generates the ranking of the at least one respective historical search query according to a popularity of the at least one respective historical search query.

10. The system of claim 9, wherein the search application further comprises logic that increases a popularity metric associated with the popularity of the at least one respective historical search query when a user selects a hyperlink associated with the at least one respective historical search query and a search result associated with the at least one respective historical search query.

11. The system of claim 3, wherein the logic that identifies the at least one respective historical search query that is relevant to the search query further comprises:

logic that associates at least one of a marketplace and a product category with the at least one respective historical search query; and

logic that designates the at least one respective historical search query as relevant to the search query when the search query is performed in at least one of the marketplace and the product category.

12. The system of claim 3, wherein the search application further comprises logic that assigns a weight to the at least one search term;

and the logic that identifies the at least one respective historical search query that is relevant to the search query further comprises logic that generates the ranking of the at least one respective historical search query according to a number of highest weighted at least one search term that is in the at least one respective historical search query.

13. The system of claim 12, wherein the logic that assigns a weight to the at least one search term further comprises logic that assigns a higher weight to a first search term in the search query when the first search term is associated with a fewer number of products in the product catalog relative to a second search term in the search query, wherein the fewer number of products is at least one.

14. The system of claim 12, wherein the logic that assigns a weight to the at least one search term further comprises logic that assigns a higher weight to a first search term in the search query when the first search term is associated with a fewer number of historical search queries relative to a second search term in the search query.

15. A method, comprising:

receiving, via at least one of one or more computing devices, a user supplied search query, the user supplied search query comprising a plurality of search terms;

removing, via at least one of the one or more computing devices, at least one of the search terms from the user supplied search query to generate a plurality of resultant search queries;

determining, via at least one of the one or more computing devices, whether individual ones of the resultant search queries one of a plurality of respective historical search queries in a data store accessible to the computing device that is associated with at least one search result in the data store;

identifying, via at least one of the one or more computing devices, a plurality of search results associated with the plurality of resultant search queries;

determining, via at least one of the one or more computing devices, whether the at least one search result is the same as individual ones of the plurality of search results;

identifying, via at least one of the one or more computing devices, the plurality of respective historical search queries as being relevant to the user supplied search query by executing at least one relevance function and at least one similarity function against an index of the plurality of respective historical search queries with the user supplied search query, wherein the at least one relevance function comprises a phrase level edit distance comparison of the user supplied search query and at least one of the plurality of respective historical search queries and the at least one similarity function is a cosine similarity, jaccad similarity, or a dice similarity; and

generating, via at least one of the one or more computing devices, a ranking of the respective historical search queries according to a number of the at least one search results that match individual ones of the plurality of search results, wherein a first historical search query associated with a higher number of the at least one search results that are the same as individual ones of the plurality of search results is ranked higher than a second historical search query associated with a lower number of that least one search results that match individual ones of the plurality of search results.

16. The method of claim 15, further comprising generating, via the at least one of the one or more computing devices, a user interface comprising at least one of the plurality of respective historical search queries.

17. The method of claim 16, wherein generating the user interface comprising at least one of the plurality of respective historical search queries further comprises generating a hyperlink associated with individual ones of the at least one of the plurality of respective historical search queries.

18. The method of claim 17, further comprising generating a query association when a user follows a hyperlink associated with a historical search query, the query association designating that the historical search query is relevant to the search query.

19. The method of claim 15, further comprising assigning, via the at least one of the one or more computing devices, a weight to individual ones of the plurality of search terms by:

determining, via the at least one of the one or more computing devices, whether a respective one of the plurality of search terms are associated with the at least one of the respective historical search queries;

identifying, via the at least one of the one or more computing devices, a number of search results associated with individual ones of the at least one of the respective historical search queries; and

weighting the respective one of the plurality of search terms according to a number of search results associated with the at least one of the respective historical search queries associated with the respective one of the plurality of search terms.

20. The method of claim 19, wherein weighting the respective one of the plurality of search terms according to the number of search results associated with the at least one of the respective historical search queries associated with the respective one of the plurality of search terms further comprises assigning, via the at least one of the one or more computing devices, a higher weight to the respective one of the plurality of search terms that is associated with a respective historical search query that is associated with a fewest number of search results greater than zero.

21. The method of claim 19, wherein generating the ranking of the respective historical search queries further comprises assigning, via the at least one of the one or more computing devices, a higher rank to a first historical search query comprising higher weighted search terms than a second historical search query.

22. The method of claim 15, further comprising assigning, via the at least one of the one or more computing devices, a weight to individual ones of the plurality of search terms by:

identifying, via the at least one of the one or more computing devices, a number of historical search queries associated with a respective one of the plurality of search terms; and

weighting the respective one of the plurality of search terms according to a number of historical search queries associated with the respective one of the plurality of search terms, wherein a higher weight is assigned to a search term that is associated with a fewest number of historical search queries.