System and method for providing search query refinements

• US 8,086,619 B2
• Filed: 09/22/2003
• Issued: 12/27/2011
• 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
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Pyo, Monica M
• Application Number:
  US10/668,721
• Publication Number:
  US 20050055341A1
• Time in Patent Office: 3,018 Days
• Field of Search: 707/3, 707/5, 707/104.1, 707/10, 707/765, 707/766, 707/999.005, 707/999.01, 707/999.104, 707/999.003
• US Class Current: 707/765
• 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 method, performed by one or more server devices, the method comprising:

storing, in a memory of the one or more server devices, search query-search document associations, each search query-search document association representing a one-to-one pairing of an issued search query and a search document retrieved based on the issued search query;

receiving, by one or more processors of the one or more server devices, a search query;

identifying, by one or more processors of the one or more server devices, a set of search result documents using the received search query;

forming, by one or more processors of the one or more server devices, a plurality of clusters of search documents, of the stored search query-search document associations, that match the identified set of search result documents;

selecting, by one or more processors of the one or more server devices, at least one of the plurality of clusters;

computing, by one or more processors of the one or more server devices, a centroid for each of the selected at least one of the plurality of clusters;

computing, by one or more processors of the one or more server devices, a score for each unique issued search query associated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

formulating, by one or more processors of the one or more server devices, a search query refinement suggestion based on the compound scores; and

sorting, by one or more processors of the one or more server devices, the formulated search query refinement suggestion among a group of search query refinement suggestions.

2. The method of claim 1, further comprising:

assigning weights to the search query-search document associations in the database based on relevancies of the search documents to the issued search queries in the search query-search document associations; and

storing the weights.

3. The method of claim 2, where the formulating the search query refinement suggestion further comprises:

computing term vectors using terms in the issued search queries of the search query-search document associations and the assigned weights.

4. The method of claim 3, where the formulating the search query refinement suggestion further comprises:

normalizing the term vectors; and

forming the clusters based on distances of each of the normalized term vectors from a common origin.

5. The method of claim 4, where the formulating the search query refinement suggestion further comprises:

multiplying, by a constant, those of the normalized term vectors that include constituent terms with the received search query to downwardly weight the constituent terms to produce an independence of the clusters from the terms of the received search query.

6. The method of claim 4, further comprising:

assigning a relevance score to the at least one search result document,

where the formulating the search query refinement suggestion further includes;

ranking the clusters based on the relevance score and a number of identified search documents in the clusters.

7. The method of claim 6, where the selecting at least one of the clusters comprises:

selecting at least one of the clusters based on the ranking. search query in the selected at least one of the clusters based on the centroids.

8. The method of claim 1, where the computing the score for each of the unique search queries comprises:

multiplying a frequency of the issued search queries in the search query-search document associations in the selected at least one of the clusters times a length of a distance vector measured from the term vectors of the issued search queries in the search query-search document associations to the centroids of the selected at least one of the clusters.

9. The method of claim 1, where the formulating the search query refinement suggestion further comprises:

designating a name to each of the selected at least one of the clusters based on the computed scores of the unique search queries of the selected at least one of the clusters.

10. The method of claim 9, where the formulating the search query refinement suggestion further comprises:

comparing the computed scores of the unique search queries of the named clusters to a threshold; and

selecting those cluster names with the computed score that exceeds the threshold to obtain the search query refinement suggestions.

11. The method of claim 10, where the sorting the formulated search query refinement suggestion further comprises:

sorting the formulated search query refinement suggestion among the group of search query refinement suggestions based on a relevance score assigned to each of the search result documents coffesponding to the identified search documents associated with the named clusters and a number of the identified search documents in the named clusters to obtain a sorted set of search query refinement suggestions.

12. The method of claim 11, further comprising:

presenting the sorted search query refinement suggestions to a user.

13. The method of claim 11, further comprising:

augmenting the sorted set of search query refinement suggestions with supplemental queries that include one or more of the terms of the search query and negated forms of all terms appearing in the set of search query refinement suggestions, but not appearing in the search query; and

presenting the augmented search query refinement suggestions to a user.

14. A system comprising:

means for storing search query-search document associations in a memory, each search query-search document association representing a one-to-one pairing of a stored search query and a search document retrieved based on the stored search query;

means for receiving a search query;

means for identifying a set of search result documents using the received search query;

means for forming a plurality of clusters of search documents, of the search query-search document associations, that are associated with the identified set of search result documents;

means for selecting at least one of the plurality of clusters;

means for computing a centroid for each of the selected at least one of the plurality of clusters;

means for computing a score for each unique stored search query asociated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

means for formulating a search query refinement suggestion based on the computed scores; and

means for sorting the formulated search query refinement suggestion among a group of search query refinement suggestions.

15. The system of claim 14, where the means for formulating the search query refinement suggestion includes:

means for identifying search documents of the search query-search document association that match the at least one search result document within the database; and

means for using the issued search queries associated with the identified search documents in the formulating.

16. The system of claim 15, further comprising:

means for assigning weights to the search query-search document associations in the database based on relevancies of the search documents to the issued search queries in the search query-search document associations; and

means for storing the weights in the database.

17. A computer-readable memory device to store instructions executable by at least one processor to cause the at least one processor to:

store search query-search document associations, each search query-search document association representing a one-to-one pairing of an issued search query and a search document retrieved based on the issued search query;

receive a search query;

identify a set of search result documents using the received search query;

form a plurality of clusters of search documents, of the stored search query-search document associations, that are associated with the identified set of search result documents;

select at least one of the plurality of clusters;

compute a centroid for each of the selected at least one of the plurality of clusters;

compute a score for each unique issued search query associated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

formulate a search query refinement suggestion based on the computed scores; and

sort the formulated search query refinement suggestion among a group of search query refinement suggestions.

18. The computer-readable memory device of claim 17, further comprising one or more instructions to cause the at least one processor to:

normalize the term vectors; and

form clusters of the identified search documents based on distances of each of the normalized term vectors from a common origin

identify search documents of the search query-search document associations that match the at least one of the search result documents; and

use the issued search queries, associated with the issued search documents, in the formulating.

19. The computer-readable memory device of claim 18, further comprising one or more instructions to cause the at least one processor to:

assign weights to the search query-search document associations in the database based on relevancies of the search documents to the issued search queries in the search query-search document associations; and

store the weights.

20. A method, performed by one or more server devices, the method comprising:

storing, in a memory of the one or more server devices, a plurality of query-document associations, each query-document association including a one-to-one pairing of an issued search query and a stored search document that was retrieved based on the issued search query;

receiving, by one or more processors of the one or more server devices, a search query from a client device;

identifying, by one or more processors of the one or more server devices, a set of search result documents using the received search query;

identifying, by one or more processors of the one or more server devices, search result documents in the identified set of search result documents that match stored search documents;

forming, by one or more processors of the one or more server devices, a plurality of clusters of the search documents, of the stored plurality of query-document associations, that match the search result documents;

selecting, by one or more processors of the one or more server devices, at least one of the plurality of clusters;

computing, by one or more processors of the one or more server devices, a centroid for each of the selected at least one of the plurality of clusters;

computing, by one or more processors of the one or more server devices, a score for each unique issued search query associated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

identifying, by one or more processors of the one or more server devices, for a stored search document of the selected at least one of the plurality of clusters, a query-document association in the plurality of query-document associations based on the computed scores;

formulating, by one or more processors of the one or more server devices, a search query refinement suggestion for the received search query based on an issued search query of the identified query-document association; and

sorting, by one or more processors of the one or more sever devices, the formulated search query refinement suggestion among a group of search query refinement suggestions.

21. The method of claim 20, further comprising:

assigning weights to the stored query-document associations based on relevancies of the search documents to the issued search queries in the query-document associations; and

storing the assigned weights.

22. The method of claim 21, where the formulating the search query refinement suggestion further comprises:

computing term vectors using terms in the issued search queries of the identified query-document associations and the assigned weights.

23. The method of claim 22, where the formulating the search query refinement suggestion further comprises:

normalizing the term vectors; and

forming clusters of the search documents in the identified query-document associations based on distances of each of the normalized term vectors from a common origin.

24. The method of claim 23, where the formulating the search query refinement suggestion further comprises:

multiplying, by a constant, those of the normalized term vectors that include constituent terms with the received search query to downwardly weight the constituent terms to produce an independence of the clusters from the terms of the received search query.

25. The method of claim 23, further comprising:

assigning a relevance score to the search result documents,

where the formulating the search query refinement suggestion further includes;

ranking the clusters based on the relevance score and a number of search documents in the clusters.

26. The method of claim 25, where the formulating the search query refinement suggestion further comprises:

selecting ones of the clusters based on the ranking.

27. The method of claim 20, where the computing the score for each of the unique search queries comprises:

multiplying a frequency of the issued search queries in the identified query-document associations in the selected clusters times a length of a distance vector measured from the term vectors of the issued search queries in the identified query-document associations to the centroids of the selected clusters.

28. The method of claim 20, where the formulating the search query refinement suggestion further comprises:

designating a name to each of the selected clusters based on the computed scores of the unique search queries of the selected clusters.

29. The method of claim 28, where the formulating the search query refinement suggestion further comprises:

comparing the computed scores of the unique search queries of the named clusters to a threshold; and

selecting those cluster names that exceed the threshold to obtain the search query refinement suggestions.

30. The method of claim 29, where the sorting the formulated the search query refinement suggestion further comprises:

sorting the formulated search query refinement suggestions based on a relevance score assigned to each of the search result documents corresponding to the search documents in the query-document associations associated with the named clusters and a number of the search documents in the named clusters.

31. The method of claim 30, further comprising:

presenting the sorted search query refinement suggestions to a user.

32. The method of claim 30, further comprising:

augmenting the sorted search query refinement suggestions with supplemental queries that include one or more of the terms of the search query and negated forms of all terms appearing in the set of search query refinement suggestions, but not appearing in the search query; and

presenting the augmented search query refinement suggestions to a user.

33. A system comprising:

means for storing a plurality of query-document associations, each query-document association including a one-to-one pairing of a search query and a search document retrieved based on the search query;

means for receiving a search query;

means for identifying a set of search result documents using the received search query;

means for identifying search result documents in the identified set of search result documents that match one or more of the stored search documents;

means for forming a plurality of clusters based on the stored search documents that match search result documents in the identified set of search result documents;

means for selecting at least one of the plurality of clusters;

means for computing a centroid for each of the selected at least one of the plurality of clusters;

means for computing a score for each unique stored search query associated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

means for identifying, for a search result document of the selected at least one of the plurality of clusters, a search query of a query-document association of the plurality of query-document associations that corresponds to the identified search result document based on the computed scores;

means for formulating a search query refinement suggestion for the received search query based on the identified search query, and

means for sorting the formulated search query refinement suggestion among a group of search query refinement suggestions.

34. The system of claim 33, further comprising:

means for using the search queries associated with the identified query-document associations in the formulating.

35. The system of claim 34, further comprising:

means for assigning weights to the stored query-document associations based on relevancies of the search documents to the search queries in the query-document associations; and

means for storing the assigned weights.

36. A method, performed by one or more server devices, the method comprising:

creating, by one or more processors of the one or more server devices, a query source reference, including;

identifying, by one or more processors of the one or more server devices, associations between issued search queries and retrieved search documents in a one-to-one relation, and assigning, by one or more processors of the one or more server devices, a weight to each of the associations;

receiving, by one or more processors of the one or more server devices, a search query;

forming, by one or more processors of the one or more server devices, a plurality of clusters based on the query source reference;

selecting, by one or more processors of the one or more server devices, at least one of the plurality of clusters;

computing, by one or more processors of the one or more server devices, a centroid for each of the selected at least one of the plurality of clusters;

computing, by one or more processors of the one or more server devices, a score for each unique issued search query associated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

formulating, by one or more processors of the one or more server devices, a refinement suggestion for the received search query based on the computed scores; and

sorting, by one or more processors of the one or more server devices, the formulated search query refinement suggestion among a group of search query refinement suggestions.

37. The method of claim 36, further comprising:

obtaining at least one search result document using the received search query,

where the formulating the search query refinement suggestion further comprises;

comparing the at least one search result document to the retrieved search documents,

identifying the retrieved search documents that match the at least one search result document, and

using the issued search queries associated with the identified search documents in the formulating.

38. The method of claim 37, where the formulating the search query refinement suggestion further comprises:

computing term vectors using terms in the issued search queries associated with the identified search documents and the assigned weights.

39. The method of claim 38, where the formulating the search query refinement suggestion further comprises:

ranking the search query refinement suggestion based on the computed term vectors,

where the method further comprises;

presenting the ranked search query refinement suggestion to a user.

40. A system comprising:

a memory; and

a processor to;

store, in the memory, search query-search document associations, each search query-search document association representing a one-to-one pairing of an issued search query and a search document retrieved based on the issued search query;

receive a search query;

identify a set of search result documents using the received search query;

form a plurality of clusters of search documents, of the stored search query-search document associations, that match the identified set of search result documents;

select at least one of the plurality of clusters;

compute a centroid for each of the selected at least one of the plurality of clusters;

compute a score for each unique issued search query associated with a document in the selected at least one of a plurality of clusters based on the computed centroid;

formulate a search query refinement suggestion based on the scores; and

sort the formulated search query refinement suggestion among a group of search query refinement suggestions.

41. The system of claim 40, where the processor is further to:

assign weights to the search query-search document associations in the database based on relevancies of the search documents to the issued search queries in the search query-search document associations; and

store the weights.

42. The system of claim 41, where, when formulating the search query refinement suggestion, the processor is further to:

compute term vectors using terms in the issued search queries of the search query-search document associations and the assigned weights.

43. The system of claim 42, where, when formulating the search query refinement suggestion, the processor is further to:

normalize the term vectors; and

form the clusters based on distances of each of the normalized term vectors from a common origin.

44. The system of claim 43, where, when formulating the search query refinement suggestion, the processor is further to:

multiply, by a constant, those of the normalized term vectors that include constituent terms with the received search query to downwardly weight the constituent terms to produce an independence of the clusters from the terms of the received search query.

45. The system of claim 43, where the processor is further to:

assign a relevance score to the at least one search result document, where, when formulating the search query refinement suggestion, the processor is further to;

rank the clusters based on the relevance score and a number of identified search documents in the clusters.

46. The system of claim 45, where, when selecting at least one of the clusters, the processor is further to:

select at least one of the clusters based on the ranking.

47. The system of claim 40, where, when computing the score for each of the unique search queries, the processor is flirther to:

multiply a frequency of the issued search queries in the search query-search document associations in the selected at least one of the clusters times a length of a distance vector measured from the term vectors of the issued search queries in the search query-search document associations to the centroids of the selected at least one of the clusters.

48. The system of claim 40, where, when formulating the search query refinement suggestion, the processor is further to:

designate a name to each of the selected at least one of the clusters based on the computed scores of the unique search queries of the selected at least one of the clusters.

49. The system of claim 48, where, when formulating the search query refinement suggestion, the processor is further to:

compare the computed scores of the unique search queries of the named clusters to a threshold; and

select those cluster names with the computed score that exceeds the threshold to obtain the search query refinement suggestions.

50. The system of claim 49, where, when sorting the formulated search query refinement suggestion, the processor is further to:

sort the formulated search query refinement suggestion among a group of search query refinement suggestions based on a relevance score assigned to each of the search result documents corresponding to the identified search documents associated with the named clusters and a number of the identified search documents in the named clusters to obtain a sorted set of search query refinement suggestions.

51. The system of claim 50, where the processor is further to:

present the sorted search query refinement suggestions to a user.

52. The system of claim 50, where the processor is further to:

augment the sorted set of search query refinement suggestions with supplemental queries that include one or more of the terms of the search query and negated forms of all terms appearing in the set of search query refinement suggestions, but not appearing in the search query; and

present the augmented search query refinement suggestions to a user.