Generating query refinements from user preference data

• US 8,918,417 B1
• Filed: 03/26/2013
• Issued: 12/23/2014
• Est. Priority Date: 06/05/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Das, Anwis
• Primary Examiner(s): NGUYEN, CAM LINH T
• Application Number:
  US13/851,034
• Time in Patent Office: 637 Days
• Field of Search: 707/765, 707/767
• US Class Current: 707/765
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/447 Temporal browsing, e.g. timeline
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods, systems, and apparatus, including computer program products, for generating query refinements from user preference data. A group of query pairs are obtained. Each query pair includes a first query and a second query. A quality score is determined for each query pair from user preference data for documents responsive to both the first and the second query. A diversity score is determined for each query pair having a quality score satisfying a quality threshold, the diversity score determined from user preference data for documents responsive to the second, but not the first, query. For each query pair having a quality score satisfying the quality threshold and a diversity score satisfying a diversity threshold, the second query of the query pair is associated with the first query of the query pair as a candidate refinement for the first query.

Claims

1. A computer-implemented method, comprising:

obtaining a group of query pairs, each query pair including a first query and a second query;

determining, using one or more computers, a quality score for each query pair in the group of query pairs;

determining a diversity score for each query pair in the group of query pairs having a quality score satisfying a quality threshold; and

associating, for each query pair having a quality score satisfying the quality threshold and a diversity score satisfying a diversity threshold, the second query of the query pair with the first query of the query pair as a candidate refinement for the first query;

selecting a group of candidate refinements associated with a candidate query, the group of candidate refinements ordered according to an order;

processing one or more of the candidate refinements according to the order and determining, for at least one additional candidate refinement in the one or more processed candidate refinements, that the additional candidate refinement has an intra-suggestion diversity score satisfying an intra-suggestion diversity threshold, the intra-suggestion diversity score estimating diversity between a first group of top documents responsive to the additional candidate refinement and a group of seen documents;

associating the additional candidate refinement with the candidate query as a confirmed refinement; and

adding the first group of top documents to the group of seen documents.

2. The method of claim 1, wherein the group of seen documents comprises one or more top documents responsive to a highly ranked candidate refinement in the group of candidate refinements.

3. The method of claim 1, further comprising associating the highly ranked candidate refinement with the candidate query as a confirmed refinement for the candidate query.

4. The method of claim 1, wherein the intra-suggestion diversity score is determined from quality of result statistics for a first plurality of documents as search results for the additional candidate refinement, wherein the first plurality of documents are not in the group of seen documents.

5. The method of claim 1, wherein the group of candidate refinements are ordered based on quality scores for query pairs corresponding to the candidate query and the candidate refinements.

6. The method of claim 1, wherein the quality score for each query pair is determined from second quality of result statistics for a second plurality of documents as search results for the second query in the query pair, the second plurality of documents being responsive to the first query in the query pair and the second query in the query pair.

7. The method of claim 1, wherein the diversity score for each query pair is determined from third quality of result statistics for a third plurality of documents as search results for the second query in the query pair, wherein the third plurality of documents are responsive to the second query in the query pair, but are not included in a top number of search results responsive to the first query in the query pair.

8. The method of claim 1, wherein the quality threshold has a first value when the second query in a query pair is a query superstring of a first query in the query pair and a different second value when the second query is not a super string of the first query.

9. The method of claim 1, wherein associating the second query of a query pair with the first query of the query pair as a candidate refinement for the first query further comprises:

determining that the second query of the query pair contains a reference to a first geographic location;

determining whether the first query contains a reference to a second geographic location; and

associating the second query with the first query only if the first query contains a reference to the second geographic location.

10. A system comprising one or more computers programmed to perform operations comprising:

obtaining a group of query pairs, each query pair including a first query and a second query;

determining, using one or more computers, a quality score for each query pair in the group of query pairs;

determining a diversity score for each query pair in the group of query pairs having a quality score satisfying a quality threshold; and

associating, for each query pair having a quality score satisfying the quality threshold and a diversity score satisfying a diversity threshold, the second query of the query pair with the first query of the query pair as a candidate refinement for the first query;

selecting a group of candidate refinements associated with a candidate query, the group of candidate refinements ordered according to an order;

processing one or more of the candidate refinements according to the order and determining, for at least one additional candidate refinement in the one or more processed candidate refinements, that the additional candidate refinement has an intra-suggestion diversity score satisfying an intra-suggestion diversity threshold, the intra-suggestion diversity score estimating diversity between a first group of top documents responsive to the additional candidate refinement and a group of seen documents;

associating the additional candidate refinement with the candidate query as a confirmed refinement; and

adding the first group of top documents to the group of seen documents.

11. The system of claim 10, wherein the group of seen documents comprises one or more top documents responsive to a highly ranked candidate refinement in the group of candidate refinements.

12. The system of claim 11, further programmed to perform operations comprising associating the highly ranked candidate refinement with the candidate query as a confirmed refinement for the candidate query.

13. The system of claim 10, wherein the intra-suggestion diversity score is determined from quality of result statistics for a first plurality of documents as search results for the additional candidate refinement, wherein the first plurality of documents are not in the group of seen documents.

14. The system of claim 10, wherein the group of candidate refinements are ordered based on quality scores for query pairs corresponding to the candidate query and the candidate refinements.

15. The system of claim 10, wherein the quality score for each query pair is determined from second quality of result statistics for a second plurality of documents as search results for the second query in the query pair, the second plurality of documents being responsive to the first query in the query pair and the second query in the query pair.

16. The system of claim 10, wherein the diversity score for each query pair is determined from third quality of result statistics for a third plurality of documents as search results for the second query in the query pair, wherein the third plurality of documents are responsive to the second query in the query pair, but are not included in a top number of search results responsive to the first query in the query pair.

17. The system of claim 10, wherein the quality threshold has a first value when the second query in a query pair is a query superstring of a first query in the query pair and a different second value when the second query is not a super string of the first query.

18. The system of claim 10, wherein associating the second query of a query pair with the first query of the query pair as a candidate refinement for the first query further comprises:

determining that the second query of the query pair contains a reference to a first geographic location;

determining whether the first query contains a reference to a second geographic location; and

associating the second query with the first query only if the first query contains a reference to the second geographic location.

19. A computer program product encoded on a computer storage medium, operable to cause data processing apparatus to perform operations comprising:

obtaining a group of query pairs, each query pair including a first query and a second query;

determining, using one or more computers, a quality score for each query pair in the group of query pairs;

determining a diversity score for each query pair in the group of query pairs having a quality score satisfying a quality threshold; and

associating, for each query pair having a quality score satisfying the quality threshold and a diversity score satisfying a diversity threshold, the second query of the query pair with the first query of the query pair as a candidate refinement for the first query;

selecting a group of candidate refinements associated with a candidate query, the group of candidate refinements ordered according to an order;

processing one or more of the candidate refinements according to the order and determining, for at least one additional candidate refinement in the one or more processed candidate refinements, that the additional candidate refinement has an intra-suggestion diversity score satisfying an intra-suggestion diversity threshold, the intra-suggestion diversity score estimating diversity between a first group of top documents responsive to the additional candidate refinement and a group of seen documents;

associating the additional candidate refinement with the candidate query as a confirmed refinement; and

adding the first group of top documents to the group of seen documents.