System and method for providing search query refinements

• US 20050055341A1
• Filed: 09/22/2003
• Published: 03/10/2005
• 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
• Granted Patent: US 8,086,619 B2
• Time in Patent Office: Days
• 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 system for creating query refinement suggestions, comprising:

a matcher matching at least one search document retrieved responsive to a query to one or more stored queries; and

a scorer scoring the stored query as a potential query refinement suggestion.

2. A system according to claim 1, further comprising:

a document matcher matching the at least one search document to one or more stored documents associated with the one or more stored queries.

3. A system according to claim 1, further comprising:

a weight associated with at least one such stored query; and

a clusterer forming at least one cluster based on the stored query and weight.

4. A system according to claim 3, further comprising:

a term vector used in cluster formation computed from terms extracted from the stored query and based on the weight for the stored query.

5. A system according to claim 4, further comprising:

a distance for the term vector; and

the cluster forming the at least one cluster relative to the distance.

6. A system according to claim 3, further comprising:

a ranker ranking the at least one cluster relative to the at least one other cluster by evaluating a relevance score associated with each search document corresponding to each matched stored document.

7. A system according to claim 6, further comprising:

a selector selecting at least one ranked cluster as a potential refinement cluster.

8. A system according to claim 3, further comprising:

a centroid computed as a weighted center of the at least one cluster; and

a score computed for each stored query relative to the centroid.

9. A system according to claim 8, further comprising:

a selector naming the at least one cluster for at least one scored stored query.

10. A system according to claim 1, further comprising:

a threshold applied to the stored scored query.

11. A system according to claim 1, further comprising:

a precomputation engine associating one or more stored documents to the stored query based on at least one of a chosen search document, a set of search documents, regenerated previous search documents, and inverted cached document and query pairings.

12. A method for creating query refinement suggestions, comprising:

matching at least one search document retrieved responsive to a query to one or more stored queries; and

scoring the stored query as a potential query refinement suggestion.

13. A method according to claim 12, further comprising:

matching the at least one search document to one or more stored documents associated with the one or more stored queries.

14. A method according to claim 12, further comprising:

associating a weight with at least one such stored query; and

forming at least one cluster based on the stored query and weight.

15. A method according to claim 14, further comprising:

computing a term vector used in cluster formation from terms extracted from the stored query and based on the weight for the stored query.

16. A method according to claim 15, further comprising:

determining a distance for the term vector; and

forming the at least one cluster relative to the distance.

17. A method according to claim 14, further comprising:

ranking the at least one cluster relative to the at least one other cluster by evaluating a relevance score associated with each search document corresponding to each matched stored document.

18. A method according to claim 17, further comprising:

selecting at least one ranked cluster as a potential refinement cluster.

19. A method according to claim 14, further comprising:

computing a centroid as a weighted center of the at least one cluster; and

computing a score for each stored query relative to the centroid.

20. A method according to claim 19, further comprising:

naming the at least one cluster for at least one scored stored query.

21. A method according to claim 12, further comprising:

applying a threshold to the stored scored query.

22. A method according to claim 12, further comprising:

associating one or more stored documents to the stored query based on at least one of a chosen search document, a set of search documents, regenerated previous search documents, and inverted cached document and query pairings.

23. A computer-readable storage medium holding code for performing the method according to claim 12.

24. An apparatus for creating query refinement suggestions, comprising:

means for matching at least one search document retrieved responsive to a query to one or more stored queries; and

means for scoring the stored query as a potential query refinement suggestion.

25. A system for providing search query refinements, comprising:

an associator associating a stored query and a stored document as a logical pairing and assigning a weight to the logical pairing;

a searcher issuing the search query and producing a set of search documents;

a matcher matching at least one search document to at least one stored document and retrieving the stored query and the assigned weight associated with the matching at least one stored document;

a clusterer forming at least one cluster based on the stored query and the assigned weight associated with the matching at least one stored document; and

a scorer scoring the stored query associated with the matching at least one stored document for the at least one cluster relative to at least one other cluster and suggesting at least one such scored search query as a set of query refinements.

26. A system according to claim 25, further comprising:

a selector selecting one such search document chosen from among the set of search documents responsive to the search query issuance as the at least one such search document.

27. A system according to claim 25, further comprising:

a selector selecting the set of search documents as the at least one such search document.

28. A system according to claim 25, further comprising:

a query log tracking previous search queries; and

a regenerator regenerating a set of previous search documents produced by the previous search queries as the at least one such search document.

29. A system according to claim 25, further comprising:

a cache associating at least one cached document and one or more cached queries as a cached pairing; and

an inverter inverting each cached pairing to associate at least one cached query and one or more cached documents as the at least one such search document.

30. A system according to claim 25, wherein relevancy to the stored query is estimated for the stored document as the weight assigned to the pairing.

31. A system according to claim 30, wherein each such assigned weight for a plurality of pairings corresponding to the stored query and the stored document is summed.

32. A system according to claim 25, wherein each stored query comprises one or more terms, further comprising:

a term vector comprising the terms in the stored query associated with the matching at least one stored document;

a distance determined for the term vector; and

the clusterer forming the at least one cluster relative to the distance.

33. A system according to claim 32, further comprising:

a normalizer normalizing the term vector.

34. A system according to claim 32, further comprising:

an evaluator computing a length of the term vector in multi-dimensional space with each dimension equaling a sum of the weights of the term in a set of associated stored queries.

35. A system according to claim 32, further comprising:

a relevance score assigned to the at least one search document; and

a ranker ranking the at least one cluster relative to the at least one other cluster by the relevance score associated with the matching at least one search document and a number of the matching at least one search document.

36. A system according to claim 35, further comprising:

a selector selecting one of more of the ranked at least one cluster as potential refinement clusters based on the rankings.

37. A system according to claim 36, further comprising:

a centroid computed as a weighted center for each such potential refinement cluster; and

the scorer scoring the stored query associated with the matching at least one stored document for the potential refinement cluster relative to the centroid.

38. A system according to claim 37, further comprising:

an evaluator computing the centroid as a normalized sum of a product of the term vector for each stored query and the relevance score associated with the matching at least one search document.

39. A system according to claim 38, further comprising:

a length of a distance vector determined from the term vector and the centroid; and

the scorer computing the score for the scored query as a product of a number of stored documents with which the stored query is associated and the distance vector length.

40. A system according to claim 25, further comprising:

a selector selecting the stored query associated with the matching at least one stored document relative to a threshold.

41. A system according to claim 25, further comprising:

a sorter sorting the set of query refinements.

42. A system according to claim 25, further comprising:

a presenter presenting the set of query refinements.

43. A system according to claim 25, further comprising:

a set of supplemental query refinements negating each term in the set of query refinements not present in the search query and using the negated terms in combination with the search query as at least one supplemental query refinement.

44. A system according to claim 25, further comprising:

an association database maintaining the pairings.

45. A system according to claim 25, wherein at least one of each such stored document and each such search document is specified as at least one of a Uniform Resource Locator (URL), hyperlink, anchor, and document excerpt.

46. A method for providing search query refinements, comprising:

associating a stored query and a stored document as a logical pairing and assigning a weight to the logical pairing;

issuing the search query and producing a set of search documents;

matching at least one search document to at least one stored document and retrieving the stored query and the assigned weight associated with the matching at least one stored document;

forming at least one cluster based on the stored query and the assigned weight associated with the matching at least one stored document; and

scoring the stored query associated with the matching at least one stored document for the at least one cluster relative to at least one other cluster and suggesting at least one such scored search query as a set of query refinements.

47. A method according to claim 46, further comprising:

selecting one such search document chosen from among the set of search documents responsive to the search query issuance as the at least one such search document.

48. A method according to claim 46, further comprising:

selecting the set of search documents as the at least one such search document.

49. A method according to claim 46, further comprising:

tracking previous search queries; and

regenerating a set of previous search documents produced by the previous search queries as the at least one such search document.

50. A method according to claim 46, further comprising:

associating at least one cached document and one or more cached queries as a cached pairing; and

inverting each cached pairing to associate at least one cached query and one or more cached documents as the at least one such search document.

51. A method according to claim 46, further comprising:

for each such pairing, estimating relevancy to the stored query for the stored document as the weight assigned to the pairing.

52. A method according to claim 51, further comprising:

summing each such assigned weight for a plurality of pairings corresponding to the stored query and the stored document.

53. A method according to claim 46, wherein each stored query comprises one or more terms, further comprising:

computing a term vector comprising the terms in the stored query associated with the matching at least one stored document;

determining a distance determined for the term vector; and

forming the at least one cluster relative to the distance.

54. A method according to claim 53, further comprising:

normalizing the term vector.

55. A method according to claim 53, further comprising:

computing a length of the term vector in multi-dimensional space with each dimension equaling a sum of the weights of the term in a set of associated stored queries.

56. A method according to claim 53, further comprising:

assigning a relevance score to the at least one search document; and

ranking the at least one cluster relative to the at least one other cluster by the relevance score associated with the matching at least one search document and a number of the matching at least one search document.

57. A method according to claim 56, further comprising:

selecting one of more of the ranked at least one cluster as potential refinement clusters based on the rankings.

58. A method according to claim 57, further comprising:

computing a centroid as a weighted center for each such potential refinement cluster; and

scoring the stored query associated with the matching at least one stored document for the potential refinement cluster relative to the centroid.

59. A method according to claim 58, further comprising:

computing the centroid as a normalized sum of a product of the term vector for each stored query and the relevance score associated with the matching at least one search document.

60. A method according to claim 59, further comprising:

determining a length of a distance vector from the term vector and the centroid; and

computing the score for the scored query as a product of a number of stored documents with which the stored query is associated and the distance vector length.

61. A method according to claim 46, further comprising:

selecting the stored query associated with the matching at least one stored document relative to a threshold.

62. A method according to claim 46, further comprising:

sorting the set of query refinements.

63. A method according to claim 46, further comprising:

presenting the set of query refinements.

64. A method according to claim 46, further comprising:

negating each term in the set of query refinements not present in the search query and using the negated terms in combination with the search query as at least one supplemental query refinement.

65. A method according to claim 46, further comprising:

maintaining the pairings in a database.

66. A method according to claim 46, further comprising:

specifying at least one of each such stored document and each such search document as at least one of a Uniform Resource Locator (URL), hyperlink, anchor, and document excerpt.

67. A computer-readable storage medium holding code for performing the method according to claim 46.

68. An apparatus for providing search query refinements, comprising:

means for associating a stored query and a stored document as a logical pairing and means for assigning a weight to the logical pairing;

means for issuing the search query and means for producing a set of search documents;

means for matching at least one search document to at least one stored document and means for retrieving the stored query and the assigned weight associated with the matching at least one stored document;

means for forming at least one cluster based on the stored query and the assigned weight associated with the matching at least one stored document; and

means for scoring the stored query associated with the matching at least one stored document for the at least one cluster relative to at least one other cluster and means for suggesting at least one such scored search query as a set of query refinements.

69. A system for integrating query refinement candidates, comprising:

a matcher matching at least one search document retrieved responsive to a query to one or more stored documents associated with a stored query and weight and matching at least one further search document retrieved responsive to a candidate query to the one or more stored documents;

a cluster forming at least one cluster based on the stored query and weight associated with each stored document matched responsive to the query and forming at least one further cluster based on the stored query and weight associated with each stored document matched responsive to the candidate query;

a combiner combining the at least one cluster and the at least one further cluster; and

a scorer scoring the stored query for the combined cluster relative to at least one other cluster as a potential query refinement suggestion.

70. A system according to claim 69, further comprising:

a set of candidate query refinements comprising at least one such candidate query.

71. A system according to claim 70, further comprising:

an evaluator assigning at least one such candidate query to the at least one cluster.

72. A system according to claim 71, further comprising:

a builder creating an orthogonal set of candidate query refinements comprising at least one such unassigned query candidate.

73. A method for integrating query refinement candidates, comprising:

matching at least one search document retrieved responsive to a query to one or more stored documents associated with a stored query and weight;

forming at least one cluster based on the stored query and weight associated with each stored document matched responsive to the query;

matching at least one further search document retrieved responsive to a candidate query to the one or more stored documents;

forming at least one further cluster based on the stored query and weight associated with each stored document matched responsive to the candidate query;

combining the at least one cluster and the at least one further cluster; and

scoring the stored query for the combined cluster relative to at least one other cluster as a potential query refinement suggestion.

74. A method according to claim 73, further comprising:

assembling a set of candidate query refinements comprising at least one such candidate query.

75. A method according to claim 74, further comprising:

assigning at least one such candidate query to the at least one cluster.

76. A method according to claim 75, further comprising:

creating an orthogonal set of candidate query refinements comprising at least one such unassigned query candidate.

77. A computer-readable storage medium holding code for performing the method according to claim 73.

78. An apparatus for integrating query refinement candidates, comprising:

means for matching at least one search document retrieved responsive to a query to one or more stored documents associated with a stored query and weight;

means for forming at least one cluster based on the stored query and weight associated with each stored document matched responsive to the query;

means for matching at least one further search document retrieved responsive to a candidate query to the one or more stored documents;

means for forming at least one further cluster based on the stored query and weight associated with each stored document matched responsive to the candidate query;

means for combining the at least one cluster and the at least one further cluster; and

means for scoring the stored query for the combined cluster relative to at least one other cluster as a potential query refinement suggestion.