Diversifying a set of items

• US 20080154878A1
• Filed: 12/20/2006
• Published: 06/26/2008
• Est. Priority Date: 12/20/2006
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Oath Inc. (Verizon Communications Inc.)
• Inventors: Rose, Daniel E., Raju, Swati
• Application Number:
  US11/643,473
• Publication Number:
  US 20080154878A1
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Techniques are described hereafter for diversifying search results by ranking the search results based, at least in part, on a diversifying factor. In one embodiment, the diversifying factor is used to generate diversity scores for the matching documents. Matching items that are very different from other highly-ranked matching items are assigned high diversity scores, and have their rankings improved based on their diversity scores. Conversely, matching items that are very similar to other highly-ranked matching items are assigned low diversity scores, and have their rankings reduced based on their diversity scores. Techniques are also described for re-ranking search results in response to user input without any additional interaction with the search engine. Techniques are also described for generating tag clouds that indicate the concepts associated with the currently-presented set of search results, where a visual characteristic of the tags reflects how strongly the corresponding concepts reflect the currently-presented set of search results.

Claims

1. A method for ranking items that belong to a set of items, comprising:

generating diversity scores for items that belong to said set of items based on how different the items are to other items that belong to said set of items; and

sending a message that presents said set of items in manner that is based, at least in part, on said diversity scores.

2. The method of claim 1 further comprising:

generating relevance scores for a plurality of items based on how relevant those items are to search terms contained in a search query; and

selecting said set of items from said plurality of items.

3. The method of claim 2 wherein the message is sent as a response to said search query.

4. The method of claim 1 wherein the message presents said set of items in an order that is based, at least in part, on said diversity scores.

5. The method of claim 2 further comprising selecting said set of items from among said plurality of items based, at least in part, on the relevance scores.

6. The method of claim 3 wherein the step of sending a message includes:

generating presentation scores for items in said set of items based, at least in part, on said relevance scores and said diversity scores; and

presenting said items in an order that is based on said presentation scores.

7. The method of claim 6 further comprising:

generating relevance rankings for said items based on the relevance scores; and

generating diversity rankings for said items based on the diversity scores;

wherein the step of generating presentation scores includes generating presentation scores based, at least in part, on the relevance rankings and the diversity rankings.

8. The method of claim 7 wherein the step of generating presentation scores for items in said set of items includes determining relative weights for the relevance rankings and diversity rankings based on a particular degree of diversity.

9. The method of claim 8 further comprising receiving input from a user that specifies said particular degree of diversity.

10. The method of claim 8 wherein:

the step of generating diversity rankings is performed by a search engine; and

the method further comprises receiving, at the search engine, a specified degree of diversity from an external program that is using searching services provided by the search engine.

11. The method of claim 8 further comprising determining said particular degree of diversity based on user-specific information associated with a user that submitted the search query.

12. The method of claim 8 wherein:

the step of generating diversity rankings is performed by a search engine in response to a search query;

the search engine generates the diversity rankings based on a degree of diversity; and

the degree of diversity is based, at least in part, on the type of said query.

13. The method of claim 8 wherein:

the step of generating diversity rankings is performed by a search engine in response to a search query submitted by a user;

the search engine generates the diversity rankings based on a degree of diversity; and

the degree of diversity is based, at least in part, on the user that submitted the query.

14. The method of claim 13 wherein the degree of diversity is based, at least in part, on whether the user that submitted the query frequently clicks-through items with lower presentation rankings.

15. The method of claim 13 wherein the degree of diversity is based, at least in part, on stored preferences of the user that submitted the query.

16. The method of claim 8 wherein:

the step of generating diversity rankings is performed by a search engine in response to a search query;

the search engine generates the diversity rankings based on a degree of diversity; and

the degree of diversity is based, at least in part, on how many results are produced by the query.

56. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 1.

57. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 2.

58. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 3.

59. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 4.

60. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 5.

61. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 6.

62. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 7.

63. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 8.

64. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 9.

65. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 10.

66. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 11.

67. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 12.

68. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 13.

69. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 14.

70. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 15.

71. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 16.

17. A method for ranking search results of a search query, comprising:

storing association information that associates concepts with items in a population;

receiving a search query for items in said population that match specified search criteria;

identifying a plurality of items, from said population, that match said search query;

assigning presentation rankings to each of said plurality of items;

identifying, based on the presentation rankings, a first subset of said items to be listed in a first search results web page;

generating, as the first search results web page, a web page that

(a) identifies items in the first subset of items, and

(b) includes a display of concepts;

wherein the concepts that are included in the display of concepts are selected exclusively based on concepts that said association information associates with the items in the first subset.

18. The method of claim 17 wherein the display of concepts is a tag cloud.

19. The method of claim 18 wherein:

the association information includes concept weight information that indicates the degrees to which items are related to the concepts with which the items are associated; and

at least one visual characteristic of tags in said tag cloud reflects the degrees to which items in the first subset are related to the concepts in the tag cloud.

20. The method of claim 17 wherein storing association information includes storing concept vectors for items in said population.

21. The method of claim 20 wherein the step of assigning presentation rankings includes:

determining diversity rankings based on said concept vectors; and

determining the presentation rankings based, at least in part, on said concept vectors.

72. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 17.

73. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 18.

74. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 19.

75. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 20.

76. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 21.

22. A method for ranking a set of items, comprising:

(a) assigning diversity rankings to one or more items in the set of items;

(b) after step (a), for each item, in said set of items, that has not yet been assigned a diversity ranking, determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking; and

(c) based on the diversity scores determined in step (b), assigning diversity rankings to one or more items, from the set of items, that have not yet been assigned diversity rankings.

23. The method of claim 22 further comprising repeating steps (b) and (c) until all items in the set of items have been assigned diversity rankings.

24. The method of claim 22 wherein the step of determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking includes determining a diversity score that reflects differences in subject matter between the item and all items that have already been assigned a diversity ranking.

25. The method of claim 22 wherein the step of determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking includes determining a diversity score that reflects differences in source between the item and all items that have already been assigned a diversity ranking.

26. The method of claim 22 wherein the step of determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking includes determining a diversity score that reflects differences in geographic locations associated with the item and all items that have already been assigned a diversity ranking.

27. The method of claim 22 wherein the step of determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking includes determining a diversity score that reflects differences in author between the item and all items that have already been assigned a diversity ranking.

28. The method of claim 22 wherein the step of determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking includes determining a diversity score that reflects differences in item type between the item and all items that have already been assigned a diversity ranking.

29. The method of claim 22 wherein the step of determining a diversity score that indicates a degree of difference between (i) the item and (ii) all items, from the set, that have already been assigned a diversity ranking includes determining a diversity score that reflects differences in prices associated with the item and all items that have already been assigned a diversity ranking.

30. The method of claim 22 wherein:

the set of items are items from search results produced in response to a search query; and

the method further includes determining a presentation ranking for the search results based, at least in part, on the diversity rankings.

46. The method of claim 30 further comprising:

generating relevance rankings for said items based on the relevance scores; and

generating diversity rankings for said items based on the diversity scores;

wherein the step of generating presentation scores includes generating presentation scores based, at least in part, on the relevance rankings and the diversity rankings.

47. The method of claim 46 wherein the step of generating presentation scores for items in said set of items includes determining relative weights for the relevance rankings and diversity rankings based on a particular degree of diversity.

48. The method of claim 47 further comprising receiving input from a user that specifies said particular degree of diversity.

49. The method of claim 47 wherein:

the step of generating diversity rankings is performed by a search engine; and

the method further comprises receiving, at the search engine, a specified degree of diversity from an external program that is using searching services provided by the search engine.

50. The method of claim 47 further comprising determining said particular degree of diversity based on user-specific information associated with a user that submitted the search query.

51. The method of claim 47 wherein:

the step of generating diversity rankings is performed by a search engine in response to a search query;

the search engine generates the diversity rankings based on a degree of diversity; and

the degree of diversity is based, at least in part, on the type of said query.

52. The method of claim 47 wherein:

the step of generating diversity rankings is performed by a search engine in response to a search query submitted by a user;

the search engine generates the diversity rankings based on a degree of diversity; and

the degree of diversity is based, at least in part, on the user that submitted the query.

53. The method of claim 52 wherein the degree of diversity is based, at least in part, on whether the user that submitted the query frequently clicks-through items with lower presentation rankings.

54. The method of claim 52 wherein the degree of diversity is based, at least in part, on stored preferences of the user that submitted the query.

55. The method of claim 47 wherein:

the step of generating diversity rankings is performed by a search engine in response to a search query;

the search engine generates the diversity rankings based on a degree of diversity; and

the degree of diversity is based, at least in part, on how many results are produced by the query.

77. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 22.

78. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 23.

79. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 24.

80. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 25.

81. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 26.

82. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 27.

83. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 28.

84. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 29.

85. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 30.

101. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 46.

102. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 47.

103. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 48.

104. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 49.

105. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 50.

106. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 51.

107. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 52.

108. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 53.

109. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 54.

110. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 55.

31. A method of presenting search results, the method comprising:

receiving a search query at a search engine;

in response to the search query, the search engine performing the steps of

generating a plurality of rankings for items in said search results, wherein each ranking of the plurality of rankings ranks said items using a different ranking criteria; and

responding to the search query by sending to a client a response that includes ranking data;

wherein the ranking data is based on said plurality of rankings and allows the client to generate a display in which the items are ranked in a presentation ranking that is based on relative weights assigned to said rankings, and to change the relative weights, and thereby change the presentation ranking, without requiring said dent to interact further with said search engine.

32. The method of claim 31 wherein:

the search engine precomputes a plurality of presentation rankings;

each presentation ranking of the plurality of presentation rankings is based on assigning different relative weights to said plurality of rankings; and

the ranking data indicates said plurality of presentation rankings.

34. The method of claim 31 wherein the step of generating a plurality of rankings includes:

generating a first ranking of said items based on a first degree of diversity;

generating a second ranking of said items based on a second degree of diversity; and

wherein the plurality of rankings include the first ranking and the second ranking.

86. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 31.

87. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 32.

89. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 34.

33. The method of 31 wherein the ranking data indicates said plurality of rankings, thereby allowing the client to compute different presentation rankings by assigning different relative weights to said plurality of rankings.

88. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 33.

35. A method for presenting search results, the method comprising:

receiving from a search engine, at a client, a response to a search query;

wherein the response includes ranking data that is based on a plurality of rankings performed by the search engine,

wherein each of the plurality of rankings rank a plurality of items that match the search query;

at the client, displaying the plurality of items in a first presentation ranking that reflects a first set of relative weights for said plurality of rankings; and

in response to user input at the client, without further interaction with the search engine, redisplaying the plurality of items in a second presentation ranking that reflects a second set of relative weights for said plurality of rankings.

36. The method of claim 35 wherein:

the search engine precomputes a plurality of presentation rankings;

each presentation ranking of the plurality of presentation rankings is based on assigning different relative weights to said plurality of rankings; and

the ranking data indicates said plurality of presentation rankings.

38. The method of claim 35 wherein:

the first presentation ranking is based on a first degree of diversity; and

the second presentation ranking is based on a second degree of diversity.

39. The method of claim 35 wherein the step of displaying a search results listing includes displaying a web page.

40. The method of claim 35 where the user input involves interaction with a control.

41. The method of claim 40 wherein the control is a slider.

90. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 35.

91. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 36.

93. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 38.

94. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 39.

95. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 40.

96. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 41.

37. The method of 35 wherein:

the ranking data indicates said plurality of rankings, and

the client computes at least one of the first presentation ranking and the second presentation ranking based on the ranking data.

92. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 37.

42. A method comprising:

generating diversity scores for a plurality of items based on how different the items are to other items of said plurality of items; and

determining a set of items to list in a response to a search query based, at least in part, on the diversity scores; and

in response to said search query, sending said response that lists said set of items.

43. The method of claim 42 further comprising:

generating relevance scores for said plurality of items based on how relevant those items are to search terms contained in said search query; and

determining said set of items to list based, at least in part, on said relevance scores.

44. The method of claim 42 wherein the response presents said set of items in an order that is based, at least in part, on said diversity scores.

45. The method of claim 44 further comprising:

generating presentation scores for items in said set of items based, at least in part, on said relevance scores and said diversity scores; and

presenting said items in an order that is based on said presentation scores.

97. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 42.

98. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 43.

99. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 44.

100. A computer-readable medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to perform the method recited in claim 45.