System and method for providing search query refinements

• US 9,552,388 B2
• Filed: 01/31/2014
• Issued: 01/24/2017
• Est. Priority Date: 09/05/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Haahr, Paul, Baker, Steven D.
• Primary Examiner(s): PYO, MONICA M
• Application Number:
  US14/169,879
• Publication Number:
  US 20140149415A1
• Time in Patent Office: 1,089 Days
• Field of Search: 707/765, 707/766
• US Class Current: 1/1
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3326 using relevance feedback from the user, e.g. relevance feedback on documents, documents sets, document terms or passages
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A system and method for providing search query refinements are presented. A stored query and a stored document are associated as a logical pairing. A weight is assigned to the logical pairing. The search query is issued and a set of search documents is produced. At least one search document is matched to at least one stored document. The stored query and the assigned weight associated with the matching at least one stored document are retrieved. At least one cluster is formed based on the stored query and the assigned weight associated with the matching at least one stored document. The stored query associated with the matching at least one stored document are scored for the at least one cluster relative to at least one other cluster. At least one such scored search query is suggested as a set of query refinements.

Claims

1. A computer-implemented method comprising:

accessing, by one or more computers, search query-resource pairs and a respective weight for each search query-resource pair, wherein, for each search query-resource pair, the search query resource-pair references (i) a single search query that was previously submitted by one or more users, and (ii) a single resource associated with one or more prior search results that were each selected by at least one of the one or more users in response to submitting the single search query;

receiving a particular search query;

obtaining one or more particular search results in response to receiving the particular search query, wherein each particular search result references (i) a respective resource, and (ii) a respective relevance score for the respective resource that indicates a relevance of the respective resource to the particular search query;

selecting one or more particular resources that each match one or more resources that are referenced by one or more of the search query-resource pairs and that are each referenced by one of the particular search results;

selecting, by one of the computers, a subset of the search queries that are referenced by the search query-resource pairs that each reference one of the particular resources, based at least on (i) the relevance score of the respective particular resource, and (ii) the weight for each respective search query-resource pair; and

providing, by one of the computers for output, one or more of the search queries of the subset of the search queries.

2. The method of claim 1, comprising:

obtaining, for each of the particular resources, a term vector that represents terms from search queries identified by search query-resource pairs that correspond to the respective particular resource;

obtaining one or more clusters of resources based on the term vectors; and

for at least one cluster, selecting, as a representative search query for the cluster, a search query identified by search query-resource pairs that correspond to the resources of the cluster based on the term vectors for each resource included in the cluster.

3. The method of claim 2, wherein selecting a subset of the search queries that are referenced by the search query-resource pairs comprises selecting a set of search queries from the representative search queries.

4. The method of claim 2, wherein, for each of the one or more term vectors, each dimension of the term vector corresponds to a distinct term of the search queries identified by the search query-resource pairs that correspond to the particular resource, and each dimension of the term vector has a value that is based on the respective weights of each search query-resource pair that identifies (i) the particular resource and (ii) a search query that includes the distinct term that corresponds to the dimension.

5. The method of claim 2, comprising:

obtaining, for each cluster, a rank score based on (i) the relevance scores of the search results that reference resources that match the resources of the cluster, and (ii) a quantity of the resources of the cluster; and

selecting, as refinement clusters, a top n clusters with the highest rank score, wherein n is a positive integer,

wherein each representative search query is selected from one of the refinement clusters, and

wherein selecting a subset of the search queries further comprises selecting one or more search queries from the representative search queries of the m clusters with the highest rank score, wherein m is a positive integer.

6. The method of claim 2, comprising:

obtaining a respective centroid for each cluster, each centroid representing a weighted center of a term vector that corresponds to the cluster; and

obtaining, for each cluster, a cluster score for each unique search query identified by search query-resource pairs that correspond to the resources of the cluster based upon (i) a quantity of the search query-resource pairings that identify the unique search query, and (ii) a distance from the unique search query to the centroid of the respective cluster,

wherein selecting a representative search query for a cluster comprises selecting, as a representative search query for the cluster, a unique search query that has a highest cluster score of the cluster scores for the unique search queries identified by search query-resource pairs that correspond to the resources of the cluster.

7. The method of claim 6, comprising:

for each resource in the subset;

multiplying, by a constant factor, a value of each dimension of the term vector that corresponds to a distinct term that matches a term included in the received search query; and

normalizing the term vector.

8. A non-transitory computer-readable medium storing software having stored thereon instructions, which, when executed by one or more computers, cause the one or more computers to perform operations of:

accessing search query-resource pairs and a respective weight for each search query-resource pair, wherein, for each search query-resource pair, the search query resource-pair references (i) a single search query that was previously submitted by one or more users, and (ii) a single resource associated with one or more prior search results that were each selected by at least one of the one or more users in response to submitting the single search query;

receiving a particular search query;

obtaining one or more particular search results in response to receiving the particular search query, wherein each particular search result references (i) a respective resource, and (ii) a respective relevance score for the respective resource that indicates a relevance of the respective resource to the particular search query;

selecting one or more particular resources that each match one or more resources that are referenced by one or more of the search query-resource pairs and that are each referenced by one of the particular search results;

selecting, by one of the computers, a subset of the search queries that are referenced by the search query-resource pairs that each reference one of the particular resources, based at least on (i) the relevance score of the respective particular resource, and (i) the weight for each respective search query-resource pair; and

providing, for output, one or more of the search queries of the subset of the search queries.

9. The computer-readable medium of claim 8, wherein the operations comprise:

obtaining, for each of the particular resources, a term vector that represents terms from search queries identified by search query-resource pairs that correspond to the respective particular resource;

obtaining one or more clusters of resources based on the term vectors; and

for at least one cluster, selecting, as a representative search query for the cluster, a search query identified by search query-resource pairs that correspond to the resources of the cluster based on the term vectors for each resource included in the cluster.

10. The computer-readable medium of claim 9, wherein selecting a subset of the search queries that are referenced by the search query-resource pairs comprises selecting a set of search queries from the representative search queries.

11. The computer-readable medium of claim 9, wherein, for each of the one or more term vectors, each dimension of the term vector corresponds to a distinct term of the search queries identified by the search query-resource pairs that correspond to the particular resource, and each dimension of the term vector has a value that is based on the respective weights of each search query-resource pair that identifies (i) the particular resource and (ii) a search query that includes the distinct term that corresponds to the dimension.

12. The computer-readable medium of claim 9, wherein the operations comprise:

obtaining, for each cluster, a rank score based on (i) the relevance scores of the search results that reference resources that match the resources of the cluster, and (ii) a quantity of the resources of the cluster; and

selecting, as refinement clusters, a top n clusters with the highest rank score, wherein n is a positive integer,

wherein each representative search query is selected from one of the refinement clusters, and

wherein selecting a subset of the search queries further comprises selecting one or more queries from the representative search queries of the m clusters with the highest rank score, wherein m is a positive integer.

13. The computer-readable medium of claim 9, wherein the operations comprise:

obtaining a respective centroid for each cluster, each centroid representing a weighted center of a term vector that corresponds to the cluster; and

obtaining, for each cluster, a cluster score for each unique search query identified by search query-resource pairs that correspond to the resources of the cluster based upon (i) a quantity of the search query-resource pairings that identify the unique search query, and (ii) a distance from the unique search query to the centroid of the respective cluster,

wherein selecting a representative search query for a cluster comprises selecting, as a representative search query for the cluster, a unique search query that has a highest cluster score of the cluster scores for the unique search queries identified by search query-resource pairs that correspond to the resources of the cluster.

14. The computer-readable medium of claim 13, wherein the operations comprise:

for each resource in the subset;

multiplying, by a constant factor, a value of each dimension of the term vector that corresponds to a distinct term that matches a term included in the received search query; and

normalizing the term vector.

15. A system comprising:

one or more processors and one or more non-transitory computer storage media storing instructions that are operable, when executed by the one or more processors, to cause the one or more processors to perform operations comprising;

accessing search query-resource pairs and a respective weight for each search query-resource pair, wherein, for each search query-resource pair, the search query resource-pair references (i) a single search query that was previously submitted by one or more users, and (ii) a single resource associated with one or more prior search results that were each selected by at least one of the one or more users in response to submitting the single search query;

receiving a particular search query;

obtaining one or more particular search results in response to receiving the particular search query, wherein each particular search result references (i) a respective resource, and (ii) a respective relevance score for the respective resource that indicates a relevance of the respective resource to the particular search query;

selecting one or more particular resources that each match one or more resources that are referenced by one or more of the search query-resource pairs and that are each referenced by one of the particular search results;

selecting a subset of the search queries that are referenced by the search query-resource pairs that each reference one of the particular resources, based at least on (i) the relevance score of the respective particular resource, and (i) the weight for each respective search query-resource pair; and

providing, for output, one or more of the search queries of the subset of the search queries.

16. The system of claim 15, wherein the operations comprise:

obtaining, for of the particular resources, a term vector that represents terms from search queries identified by search query-resource pairs that correspond to the respective particular resource;

obtaining one or more clusters of resources based on the term vectors; and

for at least one cluster, selecting, as a representative search query for the cluster, a search query identified by search query-resource pairs that correspond to the resources of the cluster based on the term vectors for each resource included in the cluster.

17. The system of claim 16, wherein selecting a subset of the search queries that are referenced by the search query-resource pairs comprises selecting a set of search queries from the representative search queries.

18. The system of claim 16, wherein, for each of the one or more term vectors, each dimension of the term vector corresponds to a distinct term of the search queries identified by the search query-resource pairs that correspond to the particular resource, and each dimension of the term vector has a value that is based on the respective weights of each search query-resource pair that identifies (i) the particular resource and (ii) a search query that includes the distinct term that corresponds to the dimension.

19. The system of claim 16, wherein the operations comprise:

obtaining, for each cluster, a rank score based on (i) the relevance scores of the search results that reference resources that match the resources of the cluster, and (ii) a quantity of the resources of the cluster; and

selecting, as refinement clusters, a top n clusters with the highest rank score, wherein n is a positive integer,

wherein each representative search query is selected from one of the refinement clusters, and

wherein selecting a subset of the search queries further comprises selecting one or more search queries from the representative search queries of the m clusters with the highest rank score, wherein m is a positive integer.

20. The system of claim 16, wherein the operations comprise:

obtaining a respective centroid for each cluster, each centroid representing a weighted center of a term vector that corresponds to the cluster; and

obtaining, for each cluster, a cluster score for each unique search query identified by search query-resource pairs that correspond to the resources of the cluster based upon (i) a quantity of the search query-resource pairings that identify the unique search query, and (ii) a distance from the unique search query to the centroid of the respective cluster,

wherein selecting a representative search query for a cluster comprises selecting, as a representative search query for the cluster, a unique search query that has a highest cluster score of the cluster scores for the unique search queries identified by search query-resource pairs that correspond to the resources of the cluster.