Search augmentation

• US 8,346,791 B1
• Filed: 03/16/2009
• Issued: 01/01/2013
• Est. Priority Date: 05/16/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Pearson, Mark, Bharat, Krishna, Shukla, Anand, Buettcher, Stefan
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US12/404,447
• Time in Patent Office: 1,387 Days
• Field of Search: None
• US Class Current: 707/759
• CPC Class Codes: G06F 16/144 Query formulation
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/332 Query formulation
• 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/3338 Query expansion
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods, systems, and apparatus, including computer program products, for generating or using augmentation queries. In one aspect, augmentation queries are identified from user interactions or are machine generated. The augmentation queries can be stored in an augmentation query data store. When a user submits a search query to a search engine, the terms of the query, and optionally additional information, such as the geographic location from which the query is received or the language of the query, can be used to identify stored augmentation queries and select one or more similar augmentation queries. The selected augmentation queries, in turn, can be used by the search engine perform an augmented search operation.

Claims

1. A computer-implemented method, comprising:

receiving a query from a user device as input for a search operation that uses the received query to identify search results responsive to the received query;

determining a transformation cost score for each of a plurality of candidate augmentation queries for the received query, the transformation cost score being based on a transformation cost value for each of one or more terms of the received query, the transformation cost value for a term of the received query being proportional to a term weight that measures an importance of the term in the received query;

selecting a candidate augmentation query from among the candidate augmentation queries based on the transformation cost score of the selected candidate augmentation query, the selecting comprising;

comparing each term of the received query to a set of non-transformable terms, each non-transformable term of the set of non-transformable terms being a term for which a matching term in the received query should not be transformed to another term;

identifying a proper subset of candidate augmentation queries from among the candidate augmentation queries, each candidate augmentation query identified for the proper subset being identified in response to a determination that the candidate augmentation query includes each term of the received query that matches a non-transformable term;

ranking the proper subset of candidate augmentation queries according to the transformation cost score of each candidate augmentation query of the proper subset; and

selecting the candidate augmentation query from among the proper subset of candidate augmentation queries based on the ranking of the proper subset;

identifying search results responsive to the selected candidate augmentation query;

augmenting the search results responsive to the received query with the search results responsive to the selected candidate augmentation query to form an augmented set of search results; and

providing the augmented set of search results to the user device as a set of search results responsive to the received query.

2. The method of claim 1, wherein selecting the candidate augmentation query from among the candidate augmentation queries based on the transformation cost score of the selected candidate augmentation query comprises:

ranking the candidate augmentation queries according to the transformation cost score of each candidate augmentation query; and

selecting the candidate augmentation query from among the candidate augmentation queries based on the ranking of the candidate augmentation queries.

3. The method of claim 1, wherein the transformation cost score of each candidate augmentation query is further based on a synonym score for each term of the candidate augmentation query, the synonym score being a measure of similarity of meanings of a term of the received query to a term of the candidate augmentation query.

4. The method of claim 1, wherein the transformation cost score for each candidate augmentation query is further based on an edit distance score for each term of the candidate augmentation query, the edit distance score being a measure of edit distance of a term of the received query to a term of the candidate augmentation query.

5. The method of claim 1, wherein the transformation cost score is proportional to the transformation of location information between the received query and the candidate query.

6. The method of claim 1, wherein the transformation cost score is proportional to a term frequency of a term in the received query, the term frequency being a measure of appearance of the term in other queries.

7. The method of claim 1, further comprising selecting candidate augmentation queries from queries stored in the augmentation query store.

8. The method of claim 1, further comprising providing visual indicator data to the user device that causes the user device to display visual indicators that differentiate the search results that are responsive to the selected candidate query from the search results that are responsive to the received query.

9. The method of claim 1, further comprising selecting candidate augmentation queries from queries stored in an augmentation query store, the selecting comprising:

generating term transformations of terms included in the received query; and

identifying queries in the augmentation query that include the term transformations of terms included in the received query.

10. The method of claim 9, wherein the query store includes a performance score for each query, the performance scores being indicative of query performance derived from user interactions for search results for each query.

11. The method of claim 10, wherein the performance scores are based on long click data indicating long clicks resulting from each query stored in the augmentation query store.

12. The method of claim 10, wherein the transformation cost score for each candidate augmentation query is proportional to the performance score for the candidate augmentation query.

13. The method of claim 1, wherein augmenting the search results responsive to the received query comprises:

identifying a search result that is included in both the search results responsive to the received query and the search results responsive to the selected candidate augmentation query; and

promoting the identified search result in the augmented set of search results.

14. The method of claim 1, wherein the transformation cost score for one of the candidate augmentation queries is based further on a similarity between the search results responsive to the received query and the search results responsive to the one candidate augmentation query.

15. The method of claim 1, wherein the transformation cost value for each of the one or more terms of the received query is a measure of term transformation of the term of the received query to a corresponding term of the candidate augmentation query.

16. A system, comprising:

one or more computers;

an augmentation query store storing augmentation queries; and

software stored in a computer readable medium and comprising instructions executable by the one or more computers to cause the one or more computers to perform operations comprising;

receiving a query from a user device as input for a search operation that uses the received query to identify search results responsive to the received query;

determining a transformation cost score for each of a plurality of candidate augmentation queries for the received query, the transformation cost score being based on a transformation cost value for each of one or more terms of the received query, the transformation cost value for a term of the received query being proportional to a term weight that measures an importance of the term in the received query;

selecting a candidate augmentation query from among the candidate augmentation queries based on the transformation cost score of the selected candidate augmentation query, the selecting comprising;

comparing each term of the received query to a set of non-transformable terms, each non-transformable term of the set of non-transformable terms being a term for which a matching term in the received query should not be transformed to another term;

identifying a proper subset of candidate augmentation queries from among the candidate augmentation queries, each candidate augmentation query identified for the proper subset being identified in response to a determination that the candidate augmentation query includes each term of the received query that matches a non-transformable term;

ranking the proper subset of candidate augmentation queries according to the transformation cost score of each candidate augmentation query of the proper subset; and

selecting the candidate augmentation query from among the proper subset of candidate augmentation queries based on the ranking of the proper subset;

identifying search results responsive to the selected candidate augmentation query;

augmenting the search results responsive to the received query with the search results responsive to the selected candidate augmentation query to form an augmented set of search results; and

providing the augmented set of search results to the user device as a set of search results responsive to the received query.

17. The system of claim 16, wherein the operation of selecting a candidate augmentation query from among the candidate augmentation queries comprises the operations of:

ranking the candidate augmentation queries according to the transformation cost score of each candidate augmentation query; and

selecting a candidate augmentation query based on the ranking of the candidate augmentation queries.

18. The system of claim 16, wherein the software stored in a computer readable medium causes the one or more computers to perform further operations comprising selecting candidate augmentation queries from queries stored in an augmentation query store by identifying queries in the augmentation query store that include at least a subset of search terms that are in the received query.

19. The system of claim 16, wherein the operation of providing the augmented set of search results to the user device as a set of search results responsive to the received query comprises the operation of providing visual indicator data to the user device that causes the user device to display visual indicators that differentiate the search results that are responsive to the selected candidate augmentation query from the search results that are responsive to the received query.

20. The system of claim 16, further comprising a user device that receives the augmented set of search results and displays the augmented set of search results to a user.

21. The system of claim 16, wherein the candidate augmentation queries include user-generated queries whose performance related to search results have been determined to exceed a performance threshold.

22. The system of claim 16, wherein the candidate augmentation queries include synthetic queries that are generated from structured document data.

23. The system of claim 22, further comprising a search results data store storing search results associated with the synthetic queries, and wherein the software stored in a computer readable medium causes the one or more computers to perform further operations comprising:

identifying documents related to a synthetic query independent of a performance of the synthetic query in a search engine; and

associating the identified documents with the synthetic query;

wherein identifying search results responsive to the selected candidate augmentation query comprises identifying the documents associated with the synthetic query as the search results responsive to the synthetic query.

24. The system of claim 16, wherein the transformation cost value for each of the one or more terms of the received query is a measure of term transformation of the term of the received query to a corresponding term of the candidate augmentation query.

25. A computer-implemented method, comprising:

receiving a query from a user device as input for a search operation that uses the received query to identify search results responsive to the received query;

determining a transformation cost score for each of a plurality of candidate augmentation queries for the received query, the transformation cost score being based on a transformation cost value for each of one or more terms of the received query, the transformation cost value for a term of the received query being proportional to a term weight that measures an importance of the term in the received query;

comparing each term of the received query to a set of non-transformable terms, each non-transformable term of the set of non-transformable terms being a term for which a matching term in the received query should not be transformed to another term;

identifying a proper subset of candidate augmentation queries from among the candidate augmentation queries, each candidate augmentation query identified for the proper subset being identified in response to a determination that the candidate augmentation query includes each term of the received query that matches a non-transformable term;

ranking the proper subset of candidate augmentation queries according to the transformation cost score of each candidate augmentation query of the proper subset;

selecting one or more candidate augmentation queries from among the proper subset of candidate augmentation queries based on the ranking of the proper subset of the candidate augmentation queries; and

performing an augmented search operation that uses the one or more candidate augmentation queries as input and that augments the search operation.

26. The method of claim 25, wherein performing an augmented search operation comprises:

identifying search results responsive to the selected one or more candidate augmentation queries;

augmenting the search results responsive to the received query with the search results responsive to the selected one or more candidate augmentation queries to form an augmented set of search results; and

providing the augmented set of search results to the user device as a set of search results responsive to the received query.

27. The method of claim 25, wherein performing an augmented search operation comprises providing to the user device the one or more candidate augmentation queries as suggested queries in response to the received query.

28. The method of claim 25, wherein the transformation cost value for each of the one or more terms of the received query is a measure of term transformation of the term of the received query to a corresponding term of the candidate augmentation query.

29. A computer-implemented method, comprising:

receiving a query from a user device as input for a search operation that uses the received query to identify search results responsive to the received query;

determining a transformation cost score for each of a plurality of candidate augmentation queries for the received query, the transformation cost score being based on a transformation cost value for each of one or more terms of the received query, the transformation cost value for a term of the received query being proportional to a term weight that measures an importance of the term in the received query, wherein determining the transformation cost score for one of the candidate augmentation queries comprises;

determining an edit distance score for the one candidate augmentation query, the edit distance score being a measure of edit distance between each of the one or more terms of the received query and a corresponding one of the one or more terms of the one candidate augmentation query;

determining a synonym score for the one candidate augmentation query, the synonym score being a measure of similarity of meanings of the each of the one or more terms of the received query and a corresponding one of the one or more terms of the one candidate augmentation query; and

determining whether the synonym score exceeds a synonym score threshold,

wherein the transformation cost score of the one candidate augmentation query is further based on the synonym score irrespective of the edit distance score if the synonym score exceeds the synonym score threshold, and

wherein the transformation cost score of the one candidate augmentation query is further based on the synonym score and the edit distance score if the synonym score does not exceed the synonym score threshold;

selecting a candidate augmentation query from among the candidate augmentation queries based on the transformation cost score of the selected candidate augmentation query;

identifying search results responsive to the selected candidate augmentation query;

augmenting the search results responsive to the received query with the search results responsive to the selected candidate augmentation query to form an augmented set of search results; and

providing the augmented set of search results to the user device as a set of search results responsive to the received query.