Topic distillation via subsite retrieval

• US 7,580,931 B2
• Filed: 03/13/2006
• Issued: 08/25/2009
• Est. Priority Date: 03/13/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Liu, Tie-Yan, Qin, Tao
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Hu; Jensen
• Application Number:
  US11/375,612
• Publication Number:
  US 20070214116A1
• Time in Patent Office: 1,261 Days
• Field of Search: 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and system for generating a search result for a query of hierarchically organized documents based on retrieval of subtrees that are key resources for topic distillation is provided. The retrieval system may identify documents relevant to a query using conventional searching techniques. The retrieval system then calculates a subtree feature for subtrees that have an identified document as their root. After the retrieval system calculates the subtree feature for the subtrees, the retrieval system may generate a subtree relevance score for each subtree based on its subtree feature. The retrieval system may then order the identified documents based on their corresponding subtree relevances.

Claims

1. A system with a central processing unit and a memory for calculating subtree features for subtrees having root documents, a subtree being a hierarchical organization of documents in which documents have ancestor/descendant relationships, comprising:

a calculate feature component that calculates a feature for each document within a subtree; and

a calculate subtree feature component that calculates a subtree feature for the subtree wherein a contribution of a descendant document of the root document decreases as an ancestral distance between the descendant document and the root document increases and as a number of sibling documents of the descendant document increases;

wherein the subtree feature of a subtree represents an aggregate feature for the root document of the subtree,

wherein the contribution is decreased as represented by the following;

2. The system of claim 1 wherein the contribution of a descendant document decreases as an ancestral distance between the document and the descendant document increases.

3. The system of claim 1 wherein the contribution of a descendant document decreases as a number of sibling documents to the descendant document increases.

4. The system of claim 1 wherein the contribution of a descendant document decreases as an ancestral distance between the document and the descendant document increases and as a number of sibling documents to the descendant document increases.

5. The system of claim 1 including an ancestor subtree feature calculation component that calculates a subtree feature representing ancestor documents of a document based on a contribution of the feature from the ancestor document and a contribution of the feature from its descendant documents and wherein the relevance component calculates the relevance of the ancestor documents based on the calculated subtree features of the ancestor documents.

6. The system of claim 1 wherein the documents are web pages and a subtree represents a subsite of web pages.

7. A system with a central processing unit and a memory for calculating subtree features for subtrees having root documents, a subtree being a hierarchical organization of documents in which documents have ancestor/descendant relationships, comprising:

a calculate feature component that calculates a feature for each document within a subtree; and

a calculate subtree feature component that calculates a subtree feature for the subtree wherein a contribution of a descendant document of the root document decreases as an ancestral distance between the descendant document and the root document increases and as a number of sibling documents of the descendant document increases;

wherein the subtree feature of a subtree represents an aggregate feature for the root document of the subtree,

wherein the contribution is decreased as represented by the following;

8. A system with a central processing unit and a memory for calculating subtree features for subtrees having root documents, a subtree being a hierarchical organization of documents in which documents have ancestor/descendant relationships, comprising:

a calculate feature component that calculates a feature for each document within a subtree; and

a calculate subtree feature component that calculates a subtree feature for the subtree wherein a contribution of a descendant document of the root document decreases as an ancestral distance between the descendant document and the root document increases and as a number of sibling documents of the descendant document increases;

wherein the subtree feature of a subtree represents an aggregate feature for the root document of the subtree,

wherein a subtree feature is represented by the following;

9. A computer-readable storage device containing instructions for controlling a computer system to identify web pages for a search result for a query, the web pages being organized into web sites, the web pages of a web site being hierarchically organized wherein the web pages of the web site have ancestor/descendant relationships, each web page of a web site being a root web page of a subsite of the web site, a subsite includes the root web page of the subsite and its descendant web pages, each web page having a feature, comprising:

receiving from a user a query;

identifying web pages that are related to the received query; and

for each identified web page,

calculating a subsite feature for the subsite with the identified web page being the root web page of the subsite based on a contribution from the feature of the identified web page and a contribution from the features of the descendant web pages of the identified web page, such that the contribution of the features of a descendant web page decreases as an ancestral distance between the identified web page and the descendant web page increases; and

determining relevance of the identified web page to the query based on the calculated subsite feature of the subsite; and

presenting to the user an indication of the identified web pages in an order that is based at least in part on the determined relevance of the identified web pages

wherein the subsite feature is represented by the following;

10. The computer-readable storage device of claim 9 wherein the relevance of a subsite indicates how well the subsite represents a topic distillation for the query.

11. The computer-readable storage device of claim 9 wherein the contribution of a descendant web page decreases as a number of sibling web pages to the descendant web page increases.

12. The computer-readable storage device of claim 9 wherein the contribution of a descendant web page decreases as an ancestral distance between the root web page and the descendant web page increases and as a number of sibling web pages to the descendant web page increases.

13. The computer-readable storage device of claim 9 wherein the subsite features are calculated independently of a query and stored for use when identifying search results of queries.

14. The computer-readable storage device of claim 9 wherein the subsite features are calculated based on initial search results of a query.

15. The computer-readable storage device of claim 14 wherein the web pages of the search result are root web pages of subsites.