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

• US 7,664,735 B2
• Filed: 04/30/2004
• Issued: 02/16/2010
• Est. Priority Date: 04/30/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Chen, Zheng, Zhang, Benyu, Zeng, Hua-Jun
• Primary Examiner(s): Pham; Hung Q
• Application Number:
  US10/837,540
• Publication Number:
  US 20050246328A1
• Time in Patent Office: 2,118 Days
• Field of Search: 707/5, 707/104.1
• 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 computing device for ranking documents of a search result, each document having words, comprising:

a memory having computer-executable instructions and a processor for executing the computer-executable instructions stored in the memory, the executed computer-executable instructions perform steps comprising;

receiving from a user a query;

identifying documents as a search result for the received query;

identifying keywords of the identified documents;

for each pair of identified documents of the search result, calculating an affinity measurement indicating affinity that a document of the pair has to the other document of the pair, wherein affinity measurement is calculated based on the following;

2. The computing device of claim 1 wherein the identifying of the documents including submitting the query to a search engine service and receiving indications of the documents as the search result.

3. The computing device of claim 1 wherein the documents are web pages.

4. A method in a computer system with a processor and a memory for calculating information richness of a document within a collection of documents, the documents in the collection having words, the method comprising:

identifying by the processor an affinity each document in the collection has to another document in the collection, wherein the affinity is identified for each pair of documents with one document of the pair being the document and the other document of the pair being another document in the collection of documents, affinity indicating to what extent the information of one document is subsumed by the information of another document;

determining by the processor information richness for each document in the collection based on an element of a normalized affinity matrix that is derived from an affinity matrix;

storing in the memory indications of the determined information richnesses of the documents in the collection; and

ranking the documents based on the stored indications of information richnesses, wherein the determined information richness for each document is defined as

5. A computing device for calculating information richness of a document within a collection of web pages, the web pages having words, comprising:

a memory having computer-executable instructions and a processor for executing the computer-executable instructions stored in the memory, the executed computer-executable instructions perform steps comprising;

identifying an affinity of each web page in the collection has to the another web page in the collection, wherein the affinity is identified for each pair of web pages with one web page of the pair being the web page and the other web page of the pair being another web page in the collection of web pages, affinity indicating to what extent the information of one web page is subsumed by the information of another web page;

determining information richness for each web page in the collection based on an element of a normalized affinity matrix that is derived from an affinity matrix;

storing in the memory indications of the determined information richnesses of the web pages in the collection; and

ranking the web pages based on the stored indications of information richnesses, wherein the determined information richness for each web page is defined as

6. The computing device of claim 5 wherein the identifying of the affinity of each web page includes generating an affinity graph.

7. The computing device of claim 5 wherein the ranking of web pages includes submitting a query to a search engine service and receiving indications of the web pages as the search result.

8. The computing device of claim 7 wherein the ranking is further based on a search-based relevance.