Disambiguation of search phrases using interpretation clusters

• US 7,225,184 B2
• Filed: 07/18/2003
• Issued: 05/29/2007
• Est. Priority Date: 07/18/2003
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Fain, Daniel C., Flake, Gary William, Carrasco, John Joseph M.
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US10/623,115
• Publication Number:
  US 20050015366A1
• Time in Patent Office: 1,411 Days
• Field of Search: 707/1, 707/2, 707/3, 707/10, 707/200, 709/224
• US Class Current: 1/1
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

In one implementation a method for disambiguation of search phrases is provided, which may include identifying interpretation clusters using bidded search terms of content providers and influencing a position of a search result in a search results list based on the interpretation clusters. In one implementation a method is provided for interpretation clustering, which may include identifying terms and associated content providers and calculating a matrix from the identified terms and associated content providers. Similarity scores between content providers based on the matrix are calculated and interpretation clusters are assigned using the similarity scores. Bidded search terms and/or searcher clickthrough terms may be used. In one implementation, a method is provided for increasing the relevance of search results, which may include receiving a search query and identifying the search query as ambiguous.

Claims

1. A computer implemented method for increasing relevance of search results, the method comprising:

receiving a search query;

identifying the search query as ambiguous;

clustering a plurality of search results for the search query into interpretation clusters;

generating a search results list based on the interpretation clusters;

wherein clustering comprises;

identifying content providers corresponding to the plurality of search results;

retrieving bidded search terms associated with each identified content provider;

determining correlations between the identified content providers based on the retrieved bidded search terms;

clustering positively correlating content providers based on the correlations;

wherein clustering positively correlating content providers comprises;

evaluating pairs of content providers having positive correlation score in descending order of correlation score;

assigning content providers to clusters after each evaluation of a pair content providers, wherein assigning comprises;

creating a new cluster comprising each content provider of a pair of content providers if neither content provider is assigned to a cluster and assigning each content provider of a pair of content providers to the new cluster; and

assigning an unassigned content provider of a partially assigned pair of content providers to a cluster comprising a previously assigned content provider of the partially assigned pair of content providers if only one of the content providers of a pair of content providers was previously assigned to a cluster.

2. The method of claim 1 wherein generating the search results list further comprises ordering search results based on the interpretation clusters.

3. The method of claim 2 wherein identifying the search query as ambiguous comprises identifying at least one of:

(a) an inherent ambiguity in the search query;

(b) an under specified search query;

or (c) a sub-phrase match for the search query.

4. The method of claim 3 wherein identifying the search query as ambiguous comprises identifying an absence of an exact match search result with the search query.

5. The method of claim 4 wherein clustering the plurality of search results associated with the search query comprises using at least one of:

(a) bidded phrases, or (b) clickthrough data.

6. The method of claim 1 wherein identifying the search query as ambiguous comprises identifying absence of an exact match search result with the search query.

7. The method of claim 1 wherein clustering the plurality of search results associated with the search query comprises using at least one of:

(a) bidded phrases, or (b) clickthrough data.

8. The method of claim 7 wherein clustering the plurality of search results associated with the search query comprises using bidded phrases.

9. The method of claim 1 wherein generating the search results list comprises interleaving search results from different interpretation clusters.

10. The method of claim 1 comprising identifying a plurality of search results as potential matches for the search query.

11. The method of claim 10 wherein clustering comprises using at least one of:

(a) bidded search terms, or (b) searcher clickthrough terms.

12. The method of claim 11 wherein clustering comprises calculating Pearson'"'"'s correlation coefficients.

13. The method of claim 12 wherein clustering comprises calculating an occurrence matrix.

14. The method of claim 13 wherein identifying a plurality of search results comprises identifying bidded search terms.

15. The method of claim 12 wherein clustering comprises calculating a co-occurrence matrix.

16. The method of claim 15 wherein identifying a plurality of search results comprises identifying bidded search terms.

17. The method of claim 1, wherein clustering positively correlating content providers comprises:

summing correlation scores of positively correlating content providers for each content provider;

selecting a highest scored content provider;

forming a cluster including content providers having

positive correlation with the highest scored content provider; and

repeating summing, selecting, and forming after removing previously clustered content providers.

18. The method of claim 17 wherein clustering comprises using correlations of occurrence values.

19. The method of claim 18 wherein clustering comprises calculating Pearson'"'"'s correlation coefficients.

20. The method of claim 17 wherein clustering comprises using correlations of co-occurrence values.

21. The method of claim 20 wherein clustering comprises calculating Pearson'"'"'s correlation coefficients.

22. The method of claim 1, wherein assigning content providers to clusters after each evaluation of a pair content providers comprises leaving content providers as previously assigned if both content providers of a pair are already assigned.

23. The method of claim 1, further comprising clustering clusters so as to further define a hierarchical structure between the content providers.

24. The method of claim 23 further comprising storing relationship information corresponding to the hierarchical structure of clustered clusters.

25. The method of claim 1, wherein assigning content providers to clusters after each evaluation of a pair content providers further comprises:

clustering clusters if both content providers of a pair are already assigned to clusters comprising;

defining an inter-cluster score between the clusters of previously assigned content providers of a pair of content providers; and

incrementing an inter-cluster edge score by the correlation score associated with the pair of content providers.

26. The method of claim 25 further comprising normalizing the incremented inter-cluster score.

27. The method of claim 26 wherein normalizing comprises dividing the incremented inter-cluster score by a product of a number of objects in each of the clusters of previously assigned content providers.

28. The method of claim 1, further comprising sorting from maximum to minimum pairs of content providers having positive correlation score prior to evaluating.

29. A computer implemented method for disambiguation of search phrases, the method comprising:

identifying interpretation clusters using bidded search terms of content providers;

influencing a position of a search result in a search results list based on the interpretation clusters;

providing the search results list in response to a search query received by a searcher for review by the searcher;

wherein identifying interpretation clusters comprises;

evaluating pairs of content providers having positive correlation coefficients in descending order; and

assigning content providers to clusters after each evaluation of a pair content providers, wherein assigning comprises;

creating a new cluster comprising each content provider of a pair of content providers if neither content provider is assigned to a cluster and assigning each content provider of a pair of content providers to the new cluster; and

assigning an unassigned content provider of a partially assigned pair of content providers to a cluster comprising a previously assigned content provider of the partially assigned pair of content providers if only one of the content providers of a pair of content providers was previously assigned to a cluster;

wherein assigning content providers to clusters after each evaluation of a pair content providers comprises;

leaving content providers as previously assigned if both content providers of a pair are already assigned.

30. The method of claim 29 wherein identifying interpretation clusters comprises using correlations of occurrence values.

31. The method of claim 30 wherein identifying interpretation clusters comprises calculating Pearson'"'"'s correlation coefficients and clustering along positive correlations.

32. The method of claim 31 wherein clustering comprises:

identifying content providers corresponding to the plurality of search results;

retrieving bidded search terms associated with each identified content provider;

determining correlations between the identified content providers based on the retrieved bidded search terms; and

clustering positively correlating content providers based on the correlations.

33. The method of claim 32 wherein clustering positively correlating content providers comprises:

summing correlation scores of positively correlating content providers for each content provider;

selecting a highest scored content provider;

forming a cluster including content providers having positive correlation with the highest scored content provider; and

repeating summing, selecting, and forming after removing previously clustered content providers.

34. The method of claim 29 wherein clustering comprises using correlations of co-occurrence values.

35. The method of claim 34 wherein identifying interpretation clusters comprises calculating Pearson'"'"'s correlation coefficients and clustering along positive correlations.

36. The method of claim 34 wherein identifying interpretation clusters comprises:

calculating a matrix of bidded terms in common;

calculating correlation coefficients corresponding to the bidded terms in common; and

assigning interpretation clusters using the correlation coefficients.

37. The method of claim 36 wherein calculating correlation coefficients comprises calculating Pearson'"'"'s correlation coefficients and clustering along positive correlations.

38. The method of claim 37 wherein clustering comprises:

identifying content providers corresponding to the plurality of search results;

retrieving bidded search terms associated with each identified content provider;

determining correlations between the identified content providers based on the retrieved bidded search terms; and

clustering positively correlating content providers based on the correlations.

39. The method of claim 38 wherein clustering positively correlating content providers comprises:

summing correlation scores of positively correlating content providers for each content provider;

selecting a highest scored content provider;

forming a cluster including content providers having positive correlation with the highest scored content provider; and

repeating summing, selecting, and forming after removing previously clustered content providers.

40. The method of claim 29, further comprising clustering clusters so as to further define a hierarchical structure between the content providers.

41. The method of claim 40 further comprising storing relationship information corresponding to the hierarchical structure of clustered clusters.

42. The method of claim 29 wherein assigning content providers to clusters after each evaluation of a pair content providers further comprises:

clustering clusters if both content providers of a pair are already assigned to clusters comprising;

defining an inter-cluster score between the clusters of previously assigned content providers of a pair of content providers; and

incrementing an inter-cluster edge score by the correlation coefficient associated with the pair of content providers.

43. The method of claim 42 further comprising normalizing the incremented inter-cluster score.

44. The method of claim 29, further comprising sorting from maximum to minimum pairs of content providers having positive correlation coefficient prior to evaluating.

45. The method of claim 29 wherein identifying interpretation clusters comprises evaluating redundant term vectors.

46. The method of claim 29 wherein identifying interpretation clusters comprises defining a cluster signature based on an evaluation of probabilities of content providers being members of clusters.

47. The method of claim 29 wherein providing the search results comprises providing search results capable of review by a searcher wherein the searcher is an automated process representing a user'"'"'s interest.

48. A computer implemented method for interpretation clustering, the method comprising:

identifying a plurality of terms and associated content providers;

calculating a matrix from the identified plurality of terms and associated content providers;

calculating similarity scores between content providers based on the matrix; and

assigning interpretation clusters using the similarity scores

wherein assigning intemretation clusters comprises;

evaluating pairs of content providers having correlating similarity scores in descending order of similarity score; and

assigning content providers to clusters after each evaluation of a pair content providers, wherein assigning comprises;

creating a new cluster comprising each content provider of a pair of content providers if neither content provider is assigned to a cluster and assigning each content provider of a pair of content providers to the new cluster; and

assigning an unassigned content provider of a partially assigned pair of content providers to a cluster comprising a previously assigned content provider of the partially assigned pair of content providers if only one of the content providers of a pair of content providers was previously assigned to a cluster;

wherein assigning content providers to clusters after each evaluation of a pair content providers comprises leaving content providers as previously assigned if both content providers of a pair are already assigned.

49. The method of claim 48 wherein calculating similarity scores comprises calculating Pearson'"'"'s correlation coefficients.

50. The method of claim 49 wherein calculating a matrix comprises calculating an occurrence matrix.

51. The method of claim 50 wherein identifying comprises using bidded search terms.

52. The method of claim 50 wherein identifying comprises using searcher clickthrough terms.

53. The method of claim 49 wherein calculating a matrix comprises calculating a co-occurrence matrix.

54. The method of claim 53 wherein identifying comprises using at least one of:

(a) bidded search terms, or (b) searcher clickthrough terms.

55. The method of claim 48 wherein calculating a matrix comprises calculating a co-occurrence matrix.

56. The method of claim 55 wherein identifying comprises using bidded search terms.

57. The method of claim 55 wherein identifying comprises using searcher clickthrough terms.

58. The method of claim 48, further comprising clustering clusters to define a hierarchical structure between the content providers.

59. The method of claim 58 further comprising storing relationship information corresponding to the hierarchical structure of clustered clusters.

60. The method of claim 48, wherein assigning content providers to clusters after each evaluation of a pair content providers further comprises:

clustering the clusters if both content providers of a pair are already assigned comprising;

defining an inter-cluster score between the clusters of previously assigned content providers of a pair of content providers; and

incrementing an inter-cluster edge score by the similarity score associated with the pair of content providers.

61. The method of claim 60 further comprising normalizing the incremented inter-cluster score.

62. The method of claim 61 wherein normalizing comprises dividing the incremented inter-cluster score by a product of a number of objects in each of the clusters of previously assigned content providers.

63. The method of claim 48, further comprising sorting from maximum to minimum pairs of content providers having correlating similarity score prior to evaluating.

64. A method for interpretation clustering, the method comprising:

identifying a plurality of terms and associated content providers;

calculating a co-occurrence matrix of terms in common;

calculating correlation coefficients corresponding to the terms in common; and

assigning interpretation clusters using the correlation coefficients

wherein identifying interpretation clusters comprises;

evaluating pairs of primary entities having positive correlation coefficients in descending order; and

assigning primary entities to clusters after each evaluation of a pair primary entities, wherein assigning comprises;

creating a new cluster comprising each content provider of a pair of primary entities if neither content provider is assigned to a cluster and assigning each content provider of a pair of primary entities to the new cluster; and

assigning an unassigned content provider of a partially assigned pair of primary entities to a cluster comprising a previously assigned content provider of the partially assigned pair of primary entities if only one of the content providers of a pair of content providers was previously assigned to a cluster.

wherein assigning content providers to clusters after each evaluation of a pair content providers comprises leaving content providers as previously assigned if both content providers of a pair are already assigned.

65. The method of claim 64 wherein identifying the plurality of terms comprises identifying one of:

(a) bidded search terms, or (b) click-through terms.

66. The method of claim 65 wherein calculating correlation coefficients comprises calculating normalized correlation coefficients.

67. The method of claim 66 wherein assigning interpretation clusters comprises clustering along positive correlations.

68. The method of claim 67 wherein clustering positively correlating content providers comprises:

summing correlation scores of positively correlating content providers for each content provider;

selecting a highest scored content provider;

forming a cluster including content providers having positive correlation with the highest scored content provider; and

repeating summing, selecting, and forming after removing previously clustered content providers.

69. The method of claim 64, further comprising clustering clusters so as to further define a hierarchical structure between the content providers.

70. The method of claim 69 further comprising storing relationship information corresponding to the hierarchical structure of clustered clusters.

71. The method of claim 64, wherein assigning content providers to clusters after each evaluation of a pair content providers further comprises:

clustering clusters if both content providers of a pair are already assigned to clusters comprising;

defining an inter-cluster score between the clusters of previously assigned content providers of a pair of content providers; and

incrementing an inter-cluster edge score by the correlation coefficient associated with the pair of content providers.

72. The method of claim 71 further comprising normalizing the incremented inter-cluster score.

73. The method of claim 64, further comprising sorting from maximum to minimum pairs of content providers having positive correlation coefficient prior to evaluating.

74. The method of claim 64 wherein identifying the plurality of terms comprises selecting search terms preselected by a content provider.

75. The method of claim 74 wherein identifying the plurality of terms comprises selecting search terms preapproved for relevance with the content provider.

76. The method of claim 74 wherein identifying the plurality of terms comprises selecting bidded search terms.

77. The method of claim 64 wherein identifying the plurality of terms and associated content providers comprises

including search terms of a content provider representative of a directory category.

78. A computer readable medium comprising executable instructions for performing a method for providing search results in response to a search query, the method comprising:

identifying the search query as ambiguous;

clustering a plurality of search results for the search query into interpretation clusters using at least one of (a) bidded phrases, or (b) clickthrough data; and

generating a search results list comprising ordering results based on the interpretation clusters;

wherein clustering positively correlating content providers comprises;

evaluating pairs of content providers having positive correlation score in descending order of correlation score; and

assigning content providers to clusters after each evaluation of a pair content providers, wherein assigning comprises;

creating a new cluster comprising each content provider of a pair of content providers if neither content provider is assigned to a cluster and assigning each content provider of a pair of content providers to the new cluster; and

assigning an unassigned content provider of a partially assigned pair of content providers to a cluster comprising a previously assigned content provider of the partially assigned pair of content providers if only one of the content providers of a pair of content providers was previously assigned to a cluster;

wherein assigning content providers to clusters after each evaluation of a pair content providers comprises leaving content providers as previously assigned if both content providers of a pair are already assigned.

79. The computer readable medium of claim 78 wherein clustering comprises:

identifying content providers corresponding to the plurality of search results;

retrieving bidded search terms associated with each identified content provider;

determining correlations between the identified content providers based on the retrieved bidded search terms; and

clustering positively correlating content providers based on the correlations.

80. The computer readable medium of claim 78, wherein clustering positively correlating content providers comprises:

summing correlation scores of positively correlating content providers for each content provider;

selecting a highest scored content provider;

forming a cluster including content providers having positive correlation with the highest scored content provider; and

repeating summing, selecting, and forming after removing previously clustered content providers.

81. The system of claim 80 wherein clustering positively correlating content providers comprises:

summing correlation scores of positively correlating content providers for each content provider;

selecting a highest scored content provider;

forming a cluster including content providers having positive correlation with the highest scored content provider; and

repeating summing, selecting, and forming after removing previously clustered content providers.

82. The system of claim 81 further comprising normalizing the incremented inter-cluster score.

83. The computer readable medium of claim 78, wherein clustering comprises using correlations of occurrence values.

84. The computer readable medium of claim 83 wherein clustering comprises using correlations of co-occurrence values.

85. The system of claim 83 wherein clustering comprises using correlations of occurrence values.

86. The system of claim 83 wherein clustering comprises using correlations of co-occurrence values.

87. The computer readable medium of claim 78, further comprising clustering clusters so as to further define a hierarchical structure between the content providers.

88. The computer readable medium of claim 78, wherein assigning content providers to clusters after each evaluation of a pair content providers further comprises:

clustering clusters if both content providers of a pair are already assigned to clusters comprising;

defining an inter-cluster score between the clusters of previously assigned content providers of a pair of content providers; and

incrementing an inter-cluster edge score by the correlation score associated with the pair of content providers.

89. The computer readable medium of claim 78, further comprising normalizing the incremented inter-cluster score.

90. The system of claim 78 wherein clustering comprises:

identifying content providers corresponding to the plurality of search results;

retrieving bidded search terms associated with each identified content provider;

determining correlations between the identified content providers based on the retrieved bidded search terms; and

clustering positively correlating content providers based on the correlations.