Estimating confidence for query revision models

• US 7,617,205 B2
• Filed: 03/30/2005
• Issued: 11/10/2009
• Est. Priority Date: 03/30/2005
• Status: Active Grant

• Current Assignee: Abbott Laboratories Incorporated, Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bailey, David R., Battle, Alexis J., Nayak, P. Pandurang, Gomes, Benedict A.
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): MENG, JAU SHYA
• Application Number:
  US11/096,198
• Publication Number:
  US 20060230035A1
• Time in Patent Office: 1,686 Days
• Field of Search: None
• US Class Current: 1/1
• 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 computer-implemented method comprising:

receiving an original query term from a user;

identifying commonly entered query terms from session data, the session data including a record of each of multiple past sessions of search activity by multiple different other users, each past session including a sequence of queries executed by a respective other user, each commonly entered query term being a query term occurring in a query after the original query term occurs in an earlier query in at least one of the past sessions of the other users;

determining, by one or more processors, a frequency of occurrence of each commonly entered query term in the past sessions as a successor query term to the original query term;

retaining one or more candidate query terms, the candidate query terms being the commonly entered query terms whose frequency of occurrence as the successor query term satisfies a first threshold;

determining a quality score of the original query term and of each of the candidate query terms based on user click data which specifies an extent to which, in the past sessions, the other users interacted with (i) a search result resulting from executing the queries using the original query term and (ii) a search result resulting from executing the queries using the candidate query terms;

retaining one or more improved query terms, each improved query term being the candidate query term having a quality score that exceeds the quality score of the original query term;

determining an expected utility for each improved query term based on multiplying a difference, in the quality score of the improved query terms over the quality score of the original query term, by the frequency of occurrence of the improved query term as the successor query term; and

providing a link to second search results, each of the second search results being associated with one or more of the improved query terms, and each of the second search results being associated with at least a portion of the improved query terms having the expected utility that satisfies a second threshold.

2. The method of claim 1, wherein determining the frequency of occurrence of each commonly entered query term further comprises:

accessing a table which stores pairs of queries which have recurred, in sequence, in excess of a minimum frequency, in the past sessions.

3. The method of claim 1, wherein the first threshold is 1%.

4. The method of claim 1, wherein determining the quality score of each of the candidate query terms further comprises:

assigning a quality score of 0 to a first search result which received no initial click;

applying a duration of an initial click on a second search result to an S-curve; and

assigning a positive quality score to the second search result based on applying the duration to the S-curve.

5. The method of claim 1, wherein:

determining the quality score further comprises determining, from the session data, a duration of each initial click, by the other users in the past sessions, on each search result resulting from executing the queries using the original query term and on each search result resulting from executing the queries using the candidate query terms; and

for the original query term and for each of the candidate query terms, the quality score is based on the respective durations of the initial clicks on the respective search results resulting from executing the respective query terms.

6. The method of claim 5, wherein determining the duration of the subsequent click further comprises identifying as the subsequent click a click that did not select a banner ad.

7. The method of claim 5, further comprising:

storing a time when each initial click occurred and a time when a corresponding subsequent click occurred,

wherein determining the duration of the initial click comprises subtracting the time of occurrence of each initial click from the time of occurrence of the corresponding subsequent click.

8. The method of claim 1, wherein the quality score is expressed as a number between 0 and 1, inclusive.

9. The method of claim 1, wherein the second threshold is 0.02.

10. A system comprising:

one or more computers; and

a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising;

receiving an original query term from a user,

identifying commonly entered query terms from session data, the session data including a record of each of multiple past sessions of search activity by multiple different other users, each past session including a sequence of queries executed by a respective other user, each commonly entered query term being a query term occurring in a query after the original query term occurs in an earlier query in at least one of the past sessions of the other users,

determining a frequency of occurrence of each commonly entered query term in the past sessions as a successor query term to the original query term,

retaining one or more candidate query terms, the candidate query terms being the commonly entered query terms whose frequency of occurrence as the successor term satisfies a first threshold,

determining a quality score of the original query term and of each of the candidate query terms based on user click data which specifies an extent to which, in the past sessions, the other users interacted with (i) a search result resulting from executing the queries using the original query term and (ii) a search result resulting from executing the queries using the candidate query terms,

retaining one or more improved query terms, each improved query term being the candidate query term having a quality score that exceeds the quality score of the original query term,

determining an expected utility for each improved query term based on multiplying a difference, in the quality score of the improved query terms over the quality score of the original query term, by the frequency of occurrence of the improved query term as the successor query term; and

providing a link to second search results, each of the second search results being associated with one or more of the improved query terms, and each of the second search results being associated with at least a portion of the improved query terms having the expected utility that satisfies a second threshold.

11. The system of claim 10, wherein determining the frequency of occurrence of each commonly entered query term further comprises:

accessing a table which stores pairs of queries which have recurred, in sequence, in excess of a minimum frequency, in the past sessions.

12. The system of claim 10, wherein determining the quality score of each of the candidate query terms further comprises:

assigning a quality score of 0 to a first search result which received no initial click;

applying a duration of an initial click on a second search result to an S-curve; and

assigning a positive quality score to the second search result based on applying the duration to the S-curve.

13. The system of claim 10, wherein:

determining the quality score further comprises determining, from the session data, a duration of each initial click, by the other users in the past sessions, on each search result resulting from executing the queries using the original query term and on each search result resulting from executing the queries using the candidate query terms; and

for the original query term and for each of the candidate query terms, the quality score is based on the respective durations of the initial clicks on the respective search results resulting from executing the respective query terms.

14. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving an original query term from a user;

identifying commonly entered query terms from session data, the session data including a record of each of multiple past sessions of search activity by multiple different other users, each past session including a sequence of queries executed by a respective other user, each commonly entered query term being a query term occurring in a query after the original query term occurs in an earlier query in at least one of the past sessions of the other users;

determining a frequency of occurrence of each commonly entered query term in the past sessions as the successor query term to the original query term;

retaining one or more candidate query terms, the candidate query terms being the commonly entered query terms whose frequency of occurrence as the successor query term satisfies a first threshold;

determining a quality score of the original query term and of each of the candidate query terms based on user click data which specifies an extent to which, in the past sessions, the other users interacted with (i) a search result resulting from executing the queries using the original query term and (ii) a search result resulting from executing the queries using the candidate query terms;

retaining one or more improved query terms, each improved query term being the candidate query term having a quality score that exceeds the quality score of the original query term; and

determining an expected utility for each improved query term based on multiplying a difference, in the quality score of the improved query terms over the quality score of the original query term, by the frequency of occurrence of the improved query term as the successor query term; and

providing a link to second search results, each of the second search results being associated with one or more of the improved query terms, and each of the second search results being associated with at least a portion of the improved query terms having the expected utility that satisfies a second threshold.

15. The computer storage medium of claim 14, wherein determining the frequency of occurrence of each commonly entered query term further comprises:

accessing a table which stores pairs of queries which have recurred, in sequence, in excess of a minimum frequency, in the past sessions.

16. The computer storage medium of claim 14, wherein determining the quality score of each of the candidate query terms further comprises:

assigning a quality score of 0 to a first search result which received no initial click;

applying a duration of an initial click on a second search result to an S-curve; and

assigning a positive quality score to the second search result based on applying the duration to the S-curve.

17. The computer storage medium of claim 14, wherein:

determining the quality score further comprises determining, from the session data, a duration of each initial click, by the other users in the past sessions, on each search result resulting from executing the queries using the original query term and on each search result resulting from executing the queries using the candidate query terms; and

for the original query term and for each of the candidate query terms, the quality score is based on the respective durations of the initial clicks on the respective search results resulting from executing the respective query terms.