Query revision using known highly-ranked queries

• US 20060224554A1
• Filed: 11/22/2005
• Published: 10/05/2006
• Est. Priority Date: 03/29/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cohn, David Ariel, Engelhardt, Barbara, Bailey, David R., Battle, Alexis J., Nayak, P. Pandurang
• Granted Patent: US 7,870,147 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 method for automatically suggesting known highly-ranked queries in response to a first query, comprising:

calculating a revision score for an indexed query as a function of a revision probability for the first query with respect to the indexed query and a query rank for the indexed query;

responsive to the revision score, selectively retrieving the indexed query as an alternative query to the first query; and

responsive to the alternative query being a known highly-ranked query, returning the alternative query as a candidate revision query.

2. The method of claim 1, further comprising:

responsive to the alternative query having a statistically significant probability of revising to a known highly-ranked query, returning the known highly-ranked query as a candidate revision query.

3. The method of claim 1, wherein the first query is a query revision.

4. The method of claim 1, wherein the function is the product of the revision probability for the first query with respect to the indexed query and a query rank for the indexed query.

5. The method of claim 1, further comprising identifying a query as the known highly-ranked query.

6. The method of claim 5, further comprising:

calculating a query occurrence frequency for the query;

calculating a user satisfaction score for the query; and

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

7. The method of claim 6, wherein the user satisfaction score is determined by user click behavior data estimating the length of clicks on search results.

8. The method of claim 6, wherein the user satisfaction score is determined by an inverse revision frequency.

9. The method of claim 8, wherein the inverse revision frequency is the inverse of a number of times the query is revised divided by the query occurrence frequency of the query.

10. The method of claim 1, further comprising creating an index of queries comprising the indexed query.

11. The method of claim 10, wherein the index includes pointers from each of the queries in the index to one or more known highly-ranked queries.

12. The method of claim 1, wherein the revision probability comprises behavioral similarity of the indexed query with respect to the first query.

13. The method of claim 1, wherein the revision probability comprises semantic similarity of the indexed query with respect to the first query.

14. The method of claim 1, wherein the revision probability comprises syntactical similarity of the indexed query with respect to the first query.

15. The method of claim 1, further comprising:

logging query data generated from user sessions; and

using the query data to generate the index of queries.

16. The method of claim 1, further comprising:

ranking the candidate revision query using the revision score for the candidate revision query as a confidence measure.

17. The method of claim 1, further comprising:

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

18. The method of claim 17, wherein the suggested revision is displayed to a user in a location dependent upon a relative strength of the confidence measure.

19. A method for automatically suggesting known highly-ranked queries in response to a first query, comprising:

logging query data generated from user sessions;

creating an index of queries during the user session;

calculating a revision score for an indexed query as a function of a revision probability for the first query with respect to the indexed query and a query rank for the indexed query, wherein the revision probability comprises the similarity of the indexed query with respect to the first query;

responsive to the revision score, selectively retrieving the indexed query as an alternative query to the first query;

responsive to the alternative query being a known highly-ranked query, returning the alternative query as a candidate revision query, wherein identifying the known highly-ranked query comprises;

calculating a query occurrence frequency for a query;

calculating a user satisfaction score for the query, wherein the user satisfaction score is determined by user click behavior data estimating the length of clicks on search results; and

computing a rank for the query as a product of the query occurrence frequency and the user satisfaction score;

responsive to the alternative query having a statistically significant probability of revising to a known highly-ranked query, returning the known highly-ranked query as a candidate revision query;

ranking the candidate revision query using the revision score for the candidate revision query as a confidence measure; and

providing the candidate revision query as a suggested revision for the first query, wherein the suggested revision is displayed to a user in a location dependent upon a relative strength of the confidence measure.

20. A method of identifying a query as a known highly-ranked query, comprising:

calculating a query occurrence frequency for the query;

calculating a user satisfaction score for the query; and

computing a query rank for the query using the query occurrence frequency and the user satisfaction score.

21. The method of claim 20, further comprising:

comparing the query rank of the query to other query ranks associated with the other queries to determine whether the query rank is greater than the other query ranks.

22. The method of claim 20, wherein the query occurrence frequency is calculated as the frequency of the query per unit time.

23. The method of claim 20, wherein the user satisfaction score is based upon an inverse revision frequency.

24. The method of claim 23, wherein the inverse revision frequency is the inverse of a number of times the query is revised divided by the query occurrence frequency of the query.

25. The method of claim 20, wherein the user satisfaction score is a function of a quality score.

26. The method of claim 25, wherein the quality score for the query is estimated from user behavior data estimating the length of clicks on search results.

27. The method of claim 20, wherein the query rank is a function of the query occurrence frequency and the user satisfaction score.

28. The method of claim 20, wherein the known highly-ranked query is returned as a candidate revision query.

29. A computer program product for automatically suggesting known highly-ranked queries in response to a first query, the computer program product comprising:

a computer-readable medium; and

computer program code, coded on the medium, for;

calculating a revision score for an indexed query as a function of a revision probability for the first query with respect to the indexed query and a query rank for the indexed query;

responsive to the revision score, selectively retrieving the indexed query as an alternative query to the first query; and

responsive to the alternative query being a known highly-ranked query, returning the alternative query as a candidate revision query.

30. The computer program product of claim 29, further comprising:

computer program code, coded on the medium, for;

returning the known highly-ranked query as a candidate revision query responsive to the alternative query having a statistically significant probability of revising to a known highly-ranked query.

31. The computer program product of claim 29, further comprising:

computer program code, coded on the medium, for;

ranking the candidate revision query using the revision score for the candidate revision query as a confidence measure.

32. A computer program product for identifying a query as a known highly-ranked query, the computer program product comprising:

a computer-readable medium; and

computer program code, coded on the medium, for;

calculating a query occurrence frequency for the query;

calculating a user satisfaction score for the query; and

computing a query rank using the query occurrence frequency and the user satisfaction score.

33. The computer program product of claim 32, wherein the user satisfaction score is a function of a quality score.

34. The computer program product of claim 32, wherein the quality score for the query is estimated from user behavior data estimating the length of clicks on search results.

35. The computer program product of claim 32, wherein the query rank is a function of the query occurrence frequency and the user satisfaction score.

36. A system for providing revised queries for a query as a known highly-ranked query, the system comprising:

means for calculating a revision score for an indexed query as a function of a revision probability for the first query with respect to the indexed query and a query rank for the indexed query;

means for responsive to the revision score, selectively retrieving the indexed query as an alternative query to the first query; and

means for responsive to the alternative query being a known highly-ranked query, returning the alternative query as a candidate revision query.

37. The system of claim 36, further comprising:

means for returning the known highly-ranked query as a candidate revision query responsive to the alternative query having a statistically significant probability of revising to a known highly-ranked query.

38. The system of claim 36, further comprising:

means for ranking the candidate revision query using the revision score for the candidate revision query as a confidence measure.

39. A system for providing revised queries for identifying a query as a known highly-ranked query, the system comprising:

means for calculating a query occurrence frequency for the query;

calculating a user satisfaction score for the query; and

computing a query rank using the query occurrence frequency and the user satisfaction score.

40. The system of claim 39, wherein the user satisfaction score is a function of a quality score.

41. The system of claim 39, wherein the quality score for the query is estimated from user behavior data estimating the length of clicks on search results.

42. The system of claim 39, wherein the query rank is a function of the query occurrence frequency and the user satisfaction score.