Method and system for ranking documents of a search result to improve diversity and information richness

• US 20050246328A1
• Filed: 04/30/2004
• Published: 11/03/2005
• Est. Priority Date: 04/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zhang, Benyu, Zeng, Hua-Jun
• Granted Patent: US 7,664,735 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9536 Search customisation based on social or collaborative filtering
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and system for ranking documents of search results based on information richness and diversity of topics. A ranking system determines the information richness of each document within a search result. The ranking system groups documents of a search result based on their relatedness, meaning that they are directed to similar topics. The ranking system ranks the documents to ensure that the highest ranking documents may include at least one document covering each topic, that is, one document from each of the groups. The ranking system selects the document from each group that has the highest information richness of the documents within the group. When the documents are presented to a user in rank order, the user will likely find on the first page of the search result documents that cover a variety of topics, rather than just a single popular topic.

Claims

1. A method in a computer system for ranking documents of a search result, the method comprising:

for each document of the search result, initializing an affinity rank based on information richness for the document; and

for each group of documents that are similar, adjusting the affinity rank for documents in the group so that the affinity ranks except for the highest affinity rank are lower relative to the highest affinity rank of a document in the group.

2. The method of claim 1 wherein the adjusting of the affinity rank for documents in the group includes reducing the affinity rank of each document in the group except for the affinity rank of the document in the group with the highest affinity rank.

3. The method of claim 2 wherein a document that is more similar to the document with the highest affinity rank has its affinity rank reduced by more than a document that is less similar to the document with the highest affinity rank.

4. The method of claim 1 wherein the adjusting of the affinity rank for documents in the group includes removing the document with the highest affinity ranks from the group and reducing the affinity rank of remaining documents of the group wherein the order of removal of the documents represents the ranking of the documents of the search result.

5. The method of claim 1 including for each document, calculating a relevance for that document based on the adjusted affinity ranks and a search-based relevance.

6. A method in a computer system for ordering documents of a search result to increase diversity of topics in highly ordered documents, the method comprising:

identifying groups of similar documents of the search result;

selecting one document from each of the identified groups; and

ranking the selected documents above other documents of the search result.

7. The method of claim 6 wherein each document has an initial ranking and the ranking includes ranking a selected document higher than another document that has a higher initial ranking.

8. The method of claim 6 wherein each document has an initial ranking and the selected document from each of the identified groups is the document with the highest initial ranking.

9. The method of claim 6 including re-ranking non-selected documents of a group based on their similarity to the selected document of the group.

10. The method of claim 9 wherein the re-ranking gives the non-selected document of a group that is most similar to the selected document of the group the highest reduction in rank of the documents of the group.

11. The method of claim 10 wherein the non-selected documents of the group are ranked according to their re-ranking.

12. The method of claim 10 including selecting one document from each of the identified groups after re-ranking and ranking those documents above the other documents that have not yet been selected.

13. The method of claim 9 wherein the re-ranking applies a similarity penalty.

14. The method of claim 6 wherein the selected document from each of the groups has the highest information richness of the documents within the group.

15. The method of claim 6 wherein the groups are identified using an affinity graph.

16. A method in a computer system for calculating information richness of a document within a collection of documents, the method comprising:

identifying an affinity each document in the collection has to the document; and

determining information richness for the document based on the affinity that the other documents in the collection have to the document.

17. The method of claim 16 wherein the identifying of the affinity of each document includes generating an affinity graph.

18. The method of claim 16 wherein affinity is a measure of the extent to which information content of one document is subsumed by another document.

19. The method of claim 16 wherein affinity is defined as

$\mathrm{aff}$

( d i , d j ) = d ->

i ·

d ->

j 

d ->

i 

.

20. The method of claim 16 wherein information richness measures the extent to which information content of one document subsumes the information content of other documents.

21. The method of claim 16 wherein information richness is defined as

$\mathrm{InfoRich}$

( d i ) = ∑

all ⁢

 

⁢

j ≠

i ⁢

InfoRich ⁡

( d j ) ·

M ~ ji .

22. A computer-readable medium containing instructions for causing a computer system to rank documents by a method comprising:

for each document, initializing an affinity rank based on information richness of the document; and

when a document has a high affinity rank, reducing the affinity rank for related documents

wherein the affinity rank represents the ranking of the documents.

23. The computer-readable medium of claim 22 wherein the information richness of a document is calculated based on affinities of pairs of documents.

24. The computer-readable medium of claim 23 wherein the information richness is defined as

$\mathrm{InfoRich}$

( d i ) = ∑

all ⁢

 

⁢

j ≠

i ⁢

InfoRich ⁡

( d j ) ·

M ~ ji .

25. The computer-readable medium of claim 23 wherein the affinity is defined as

$\mathrm{aff}$

( d i , d j ) = d →

i ·

d →

j 

d →

i 

.

26. The computer-readable medium of claim 22 wherein a related document that is more similar to the document with the high affinity rank has its affinity rank reduced by more than a document that is less similar to the document with the high affinity rank.

27. The computer-readable medium of claim 22 including for each document, calculating a relevance for that document based on the affinity rank of the document and a search-based relevance for that document.

28. A computer system for calculating information richness of a document within a collection of documents, comprising:

a component that identifies an affinity each document in the collection has to the document; and

a component that determines information richness for the document based on the affinity that the other documents in the collection have to the document.

29. The computer system of claim 28 wherein the component for identifying generates an affinity graph.

30. The computer system of claim 28 wherein affinity is a measure of the extent to which information content of one document is subsumed by another document.

31. The computer system of claim 28 wherein information richness measures the extent to which information content of one document subsumes the information content of other documents.