Query revision using known highly-ranked queries

• US 8,375,049 B2
• Filed: 09/07/2010
• Issued: 02/12/2013
• Est. Priority Date: 03/29/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Bailey, David R., Battle, Alexis J., Cohn, David Ariel, Engelhardt, Barbara, Nayak, P. Pandurang
• Primary Examiner(s): Choi, Yuk Ting
• Application Number:
  US12/876,896
• Publication Number:
  US 20110060736A1
• Time in Patent Office: 889 Days
• Field of Search: None
• US Class Current: 707/767
• 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: G06F 16/9532 Query formulation

Abstract

An information retrieval system includes a query revision architecture providing one or more query revisers, each of which implements a query revision strategy. A query rank reviser suggests known highly-ranked queries as revisions to a first query by initially assigning a rank to all queries, and identifying a set of known highly-ranked queries (KHRQ). Queries with a strong probability of being revised to a KHRQ are identified as nearby queries (NQ). Alternative queries that are KHRQs are provided as candidate revisions for a given query. For alternative queries that are NQs, the corresponding known highly-ranked queries are provided as candidate revisions.

Claims

1. A computer-implemented method comprising:

ranking, using one or more computers, indexed queries based on a respective query rank of each indexed query, the query rank calculated based on a frequency of occurrence of the indexed query and a user satisfaction score of the indexed query, the indexed queries including highly-ranked queries and nearby queries that are queries that have a statistically significant probability of being revised to one of the highly-ranked queries, wherein the user satisfaction score of a particular indexed query is determined from estimates of lengths of clicks on search results, wherein the estimates of the lengths of clicks on search results are based on a duration of time from a selection of a search result for the particular indexed query to a subsequent selection of another search result;

calculating a respective revision score for each indexed query as a function of a revision probability of a first query and the respective query rank for the particular indexed query, the revision probability based on at least one of a semantic similarity or syntactic similarity between the first query and the particular indexed query;

selecting one of the indexed queries as an alternative query to the first query based on the respective revision score of the selected query; and

providing the selected query as a suggested revision for the first query.

2. The method of claim 1 in which the first query is a query revision of an earlier query.

3. The method of claim 1 in which the function is a product of the revision probability for the first query with respect to the particular indexed query and the query rank for the particular indexed query.

4. The method of claim 1 in which the alternative query is a highly-ranked query.

5. The method of claim 4, further comprising:

calculating the frequency of occurrence of the alternative query;

calculating the user satisfaction score for the alternative query; and

computing a rank for the alternative query as a function of the frequency of occurrence and the user satisfaction score,

in which the alternative query is identified as the highly-ranked query based on the rank.

6. The method of claim 5, in which the user satisfaction score is based on an inverse revision frequency.

7. The method of claim 6, in which the inverse revision frequency is the inverse of a number of times the alternative query is revised divided by the query occurrence frequency of the alternative query.

8. The method of claim 1, further comprising:

logging query data generated from user sessions; and

using the query data to generate the indexed queries.

9. The method of claim 1, in which the suggested revision is displayed to a user in a location dependent upon a relative strength of a confidence measure associated with the alternative revision.

10. A non-transitory 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:

ranking indexed queries based on a respective query rank of each indexed query, the query rank calculated based on a frequency of occurrence of the indexed query and a user satisfaction score of the indexed query, the indexed queries including highly-ranked queries and nearby queries that are queries that have a statistically significant probability of being revised to one of the highly-ranked queries, wherein the user satisfaction score of a particular indexed query is determined from estimates of length of click on search result, wherein the estimates of the lengths of clicks on search results are based on a duration of time from a selection of a search result for the particular indexed query to a subsequent selection of another search result;

calculating a respective revision score for each indexed query as a function of a revision probability of a first query and the respective query rank for the particular indexed query, the revision probability based on at least one of a semantic similarity or syntactic similarity between the first query and the particular indexed query;

selecting one of the indexed queries as an alternative query to the first query based on the respective revision score of the selected indexed query; and

providing the selected query as a suggested revision for the first query.

11. The computer storage medium of claim 10 in which the first query is a query revision of an earlier query.

12. The computer storage medium of claim 10 in which the function is a product of the revision probability for the first query with respect to the particular indexed query and the query rank for the particular indexed query.

13. The computer storage medium of claim 10 in which the alternative query is a highly-ranked query.

14. The computer storage medium of claim 13, in which the operations further comprise:

calculating the frequency of occurrence of the alternative query;

calculating the user satisfaction score for the alternative query; and

computing a rank for the alternative query as a function of the frequency of occurrence and the user satisfaction score,

in which the alternative query is identified as the highly-ranked query based on the rank.

15. The computer storage medium of claim 14, in which the user satisfaction score is based on an inverse revision frequency.

16. The computer storage medium of claim 15, in which the inverse revision frequency is the inverse of a number of times the alternative query is revised divided by the query occurrence frequency of the alternative query.

17. The computer storage medium of claim 10, in which the operations further comprise:

logging query data generated from user sessions; and

using the query data to generate the indexed queries.

18. The computer storage medium of claim 10, in which the suggested revision is displayed to a user in a location dependent upon a relative strength of a confidence measure associated with the alternative revision.

19. A system comprising:

memory;

one or more processors coupled to the memory and configured to perform operations comprising;

ranking indexed queries based on a respective query rank of each indexed query, the query rank calculated based on a frequency of occurrence of the indexed query and a user satisfaction score of the indexed query, the indexed queries including highly-ranked queries and nearby queries that are queries that have a statistically significant probability of being revised to one of the highly-ranked queries, wherein the user satisfaction score of a particular indexed query is determined from estimates of lengths of clicks on search results, wherein the estimates of the lengths of clicks on search results are based on a duration of time from a selection of a search result for the particular indexed query to a subsequent selection of another search result;

calculating a respective revision score for each indexed query as a function of a revision probability of a first query and the respective query rank for the particular indexed query, the revision probability based on at least one of a semantic similarity or syntactic similarity between the first query and the particular indexed query;

selecting one of the indexed queries as an alternative query to the first query based on the respective revision score of the selected indexed query; and

providing the selected query as a suggested revision for the first query.

20. The system of claim 19 in which the first query is a query revision of an earlier query.

21. The system of claim 19 in which the function is a product of the revision probability for the first query with respect to the particular indexed query and the query rank for the particular indexed query.

22. The system of claim 19 in which the alternative query is a highly-ranked query.

23. The system of claim 22, in which the operations further comprise:

calculating the frequency of occurrence of the alternative query;

calculating the user satisfaction score for the alternative query; and

computing a rank for the alternative query as a function of the frequency of occurrence and the user satisfaction score,

in which the alternative query is identified as the highly-ranked query based on the rank.

24. The system of claim 23, in which the user satisfaction score is based on an inverse revision frequency.

25. The system of claim 24, in which the inverse revision frequency is the inverse of a number of times the alternative query is revised divided by the query occurrence frequency of the alternative query.

26. The system of claim 19, in which the operations further comprise:

logging query data generated from user sessions; and

using the query data to generate the indexed queries.

27. The system of claim 19, in which the suggested revision is displayed to a user in a location dependent upon a relative strength of a confidence measure associated with the alternative revision.