Generating query refinements from user preference data

• US 9,378,247 B1
• Filed: 12/17/2014
• Issued: 06/28/2016
• 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
• Application Number:
  US14/574,081
• Time in Patent Office: 559 Days
• Field of Search: 707/723, 707/765, 707/767
• US Class Current: 1/1
• 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 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 from user preference data for documents responsive to both the first and the second query;

determining a diversity score for each query pair in the group of query pairs 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; 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, wherein the associating 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.

2. The method of claim 1, wherein the user preference data for documents responsive to both the first and the second query is obtained from user preference data generated based on actions of a group of users, the actions including submitted queries and results responsive to the queries that are selected by respective users.

3. The method of claim 1, further comprising:

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.

4. The method of claim 3, 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.

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

6. The method of claim 3, 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.

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

8. 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.

9. 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.

10. A system 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;

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 from user preference data for documents responsive to both the first and the second query;

determining a diversity score for each query pair in the group of query pairs 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; 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, wherein the associating 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.

11. The system of claim 10, wherein the user preference data for documents responsive to both the first and the second query is obtained from user preference data generated based on actions of a group of users, the actions including submitted queries and results responsive to the queries that are selected by respective users.

12. The system of claim 10, further operable to perform operations comprising:

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.

13. The system of claim 12, 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.

14. The system of claim 13, further operable to perform operations comprising associating the highly ranked candidate refinement with the candidate query as a confirmed refinement for the candidate query.

15. The system of claim 12, 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.

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

17. 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.

18. 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.

19. One or more computer-readable storage media encoded with instructions that, when executed by one or more computers, cause the one or more computers 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 from user preference data for documents responsive to both the first and the second query;

determining a diversity score for each query pair in the group of query pairs 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; 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, wherein the associating 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.