Estimating confidence for query revision models

• US 8,140,524 B1
• Filed: 08/19/2008
• Issued: 03/20/2012
• Est. Priority Date: 03/30/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bailey, David R., Battle, Alexis J., Gomes, Benedict A., Nayak, P. Pandurang
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US12/194,431
• Time in Patent Office: 1,309 Days
• Field of Search: 707/694, 707/713, 707/721, 707/759, 707/768, 707/793, 707/802
• US Class Current: 707/721
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• 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

An information retrieval system includes a query revision architecture that integrates multiple different query revisers, each implementing one or more query revision strategies. A revision server receives a user'"'"'s query, and interfaces with the various query revisers, each of which generates one or more potential revised queries. The revision server evaluates the potential revised queries, and selects one or more of them to provide to the user. A session-based reviser suggests one or more revised queries, given a first query, by calculating an expected utility for the revised query. The expected utility is calculated as the product of a frequency of occurrence of the query pair and an increase in quality of the revised query over the first query.

Claims

1. A method for scoring likelihood of success of revised queries suggested for an original query, the method comprising:

maintaining log files of user clicks on results provided in response to the revised queries suggested for the original query, the log files including data representing features associated with the original query and the revised queries, and a respective feature value for each feature;

selecting a condition, wherein the condition specifies one or more feature values for a corresponding one or more features;

selecting the revised queries that, for a particular feature, are associated with a feature value that matches one or more of the feature values specified by the condition for the particular feature;

collecting click data for the selected revised queries from the log files, the click data including click length data, wherein a long click on a result for a particular revised query in the log files is taken as indicating a success of the particular revised query;

analyzing the click data for the selected revised queries to determine a weight for the condition;

formulating a rule by one or more computers, wherein the rule includes the condition and the weight; and

adding the rule to a predictive model, wherein the model includes a set of rules that contribute to a prediction of a respective likelihood of success for the revised queries.

2. The method of claim 1, further comprising:

applying the original query and the revised queries to the predictive model to obtain confidence measures for the revised queries based on the respective likelihood of success.

3. The method of claim 2, wherein the features include at least one from the group consisting of the original query, each word in original query, length of original query, a topic cluster of the original query, an information retrieval score for the original query, and the number of results for the original query.

4. The method of claim 2, wherein the features include at least one from the group consisting of one of the revised queries, each word in the one of the revised queries, an identification of the revision technique that generated the one of the revised queries, length of the one of the revised queries, a topic cluster associated with the one of the revised queries, an information retrieval score for a top search result for the one of the revised queries, number of results found for the one of the revised queries, length of a click on a link for the one of the revised queries, and length of a click on results for the one of the revised queries.

5. The method of claim 2, further comprising ranking the revised queries according to the confidence measures.

6. The method of claim 2, further comprising:

sorting the revised queries by the confidence measures.

7. The method of claim 2, wherein the revised queries are generated from the original query using one or more revision strategies.

8. The method of claim 1, wherein the click length data is associated with the revised queries or corresponding search results.

9. A system for scoring likelihood of success of revised queries suggested for an original query, 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;

maintaining log files of user clicks on results provided in response to the revised queries suggested for the original query, the log files including data representing features associated with the original query and the revised queries, and a respective feature value for each feature;

selecting a condition, wherein the condition specifies one or more feature values for a corresponding one or more features;

selecting the revised queries that, for a particular feature, are associated with a feature value that matches one or more of the feature values specified by the condition for the particular feature;

collecting click data for the selected revised queries from the log files, the click data including click length data, wherein a long click on a result for a particular revised query in the log files is taken as indicating a success of the particular revised query;

analyzing the click data for the selected revised queries to determine a weight for the condition;

formulating a rule, wherein the rule includes the condition and the weight; and

adding the rule to a predictive model, wherein the model includes a set of rules that contribute to a prediction of a respective likelihood of success for the revised queries.

10. The system of claim 9, wherein the operations further comprise:

applying the original query and the revised queries to the predictive model to obtain confidence measures for the revised queries based on the respective likelihood of success.

11. The system of claim 10, wherein the features include at least one from the group consisting of the original query, each word in original query, length of original query, a topic cluster of the original query, an information retrieval score for the original query, and the number of results for the original query.

12. The system of claim 10, wherein the features include at least one from the group consisting of one of the revised queries, each word in the one of the revised queries, an identification of the revision technique that generated the one of the revised queries, length of the one of the revised queries, a topic cluster associated with the one of the revised queries, an information retrieval score for a top search result for the one of the revised queries, number of results found for the one of the revised queries, length of a click on a link for the one of the revised queries, and length of a click on results for the one of the revised queries.

13. The system of claim 10, wherein the operations further comprise ranking the revised queries according to the confidence measures.

14. The system of claim 10, wherein the operations further comprise:

sorting the revised queries by the confidence measures.

15. The system of claim 10, wherein the revised queries are generated from the original query using one or more revision strategies.

16. The system of claim 9, wherein the click length data is associated with the revised queries or corresponding search results.

17. A non-transitory computer-readable medium storing software for scoring likelihood of success of revised queries suggested for an original query, the software comprising instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

maintaining log files of user clicks on results provided in response to the revised queries suggested for the original query, the log files including data representing features associated with the original query and the revised queries, and a respective feature value for each feature;

selecting a condition, wherein the condition specifies one or more feature values for a corresponding one or more features;

selecting the revised queries that, for a particular feature, are associated with a feature value that matches one or more of the feature values specified by the condition for the particular feature;

collecting click data for the selected revised queries from the log files, the click data including click length data, wherein a long click on a result for a particular revised query in the log files is taken as indicating a success of the particular revised query;

analyzing the click data for the selected revised queries to determine a weight for the condition;

formulating a rule, wherein the rule includes the condition and the weight; and

adding the rule to a predictive model, wherein the model includes a set of rules that contribute to a prediction of a respective likelihood of success for the revised queries.

18. The medium of claim 17, wherein the operations further comprise:

applying the original query and the revised queries to the predictive model to obtain confidence measures for the revised queries based on the respective likelihood of success.

19. The medium of claim 18, wherein the features include at least one from the group consisting of the original query, each word in original query, length of original query, a topic cluster of the original query, an information retrieval score for the original query, and the number of results for the original query.

20. The medium of claim 18, wherein the features include at least one from the group consisting of one of the revised queries, each word in the one of the revised queries, an identification of the revision technique that generated the one of the revised queries, length of the one of the revised queries, a topic cluster associated with the one of the revised queries, an information retrieval score for a top search result for the one of the revised queries, number of results found for the one of the revised queries, length of a click on a link for the one of the revised queries, and length of a click on results for the one of the revised queries.

21. The medium of claim 18, wherein the operations further comprise ranking the revised queries according to the confidence measures.

22. The medium of claim 18, wherein the operations further comprise:

sorting the revised queries by the confidence measures.

23. The medium of claim 18, wherein the revised queries are generated from the original query using one or more revision strategies.

24. The medium of claim 17, wherein the click length data is associated with the revised queries or corresponding search results.