Topic distillation via subsite retrieval

• US 20070214116A1
• Filed: 03/13/2006
• Published: 09/13/2007
• 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
• Granted Patent: US 7,580,931 B2
• Time in Patent Office: Days
• 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 for providing a search result for a query, the search result being derived from hierarchically organized documents, comprising:

a search component that identifies documents that are relevant to a query based on a feature of the documents;

a subtree feature calculation component that calculates a subtree feature for an identified document based on a contribution of the feature of the identified document and a contribution of the feature from its descendant documents; and

a relevance component that determines the relevance of the identified documents to the query based on the calculated subtree feature of the identified documents.

2. The system of claim 1 wherein the contribution of a descendant document decreases as an ancestral distance between the document and the identified 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 identified 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 an identified 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 for calculating subtree features for subtrees having root documents, 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.

8. The system of claim 7 wherein the contribution is decreased by a factor represented by the following:

α

(Δ

l)=λ

<sup>Δ

l</sup>

where a represents the decrease, Δ

l represents ancestral distance between the root document and a descendant document, and λ

represents a parameter to control the amount of decrease.

9. The system of claim 7 wherein the contribution is decreased as represented by the following:

$\frac{1}{<br><br>R<br><br>\left(p_s\right)<br><br>}<br><br>\underset{u=1}{\overset{h<br><br>\left(p_s\right)-1}{\sum <br><br>}}<br><br>\left[\underset{p_{i_1}\in <br><br>R<br><br>\left(p_s\right)}{\sum <br><br>}<br><br>\underset{p_{i_2}\in <br><br>R<br><br>\left(p_{i_1}\right)}{\sum <br><br>}<br><br>\mathrm{\cdots <br><br>}<br><br>\underset{p_{i_u}\in <br><br>R<br><br>\left(p_{i_{u-1}}\right)}{\sum <br><br>}<br><br>\frac{f<br><br>\left(p_{i_u}\right)}{\underset{k=1}{\overset{u}{\prod <br><br>}}<br><br><br><br>R<br><br>\left(p_{i_k}\right)<br><br>}\right]$

where h(p_s) represents height of a subtree with the root document of p_s, R(p_s) represents the child documents of p_s, ∥

a∥

represents the number of elements of a, and f(p_iu) represents the feature of document p_iu.

10. The system of claim 7 wherein the contribution is decreased as represented by the following:

$\frac{1}{<br><br>R<br><br>\left(p_s\right)<br><br>}<br><br>\underset{u=1}{\overset{h<br><br>\left(p_s\right)-1}{\sum <br><br>}}<br><br>\left[\mathrm{\alpha <br><br>}<br><br>\left(u\right)<br><br>\underset{p_{i_1}\in <br><br>R<br><br>\left(p_s\right)}{\sum <br><br>}<br><br>\underset{p_{i_2}\in <br><br>R<br><br>\left(p_{i_1}\right)}{\sum <br><br>}<br><br>\mathrm{\cdots <br><br>}<br><br>\underset{p_{i_u}\in <br><br>R<br><br>\left(p_{i_{u-1}}\right)}{\sum <br><br>}<br><br>\frac{f<br><br>\left(p_{i_u}\right)}{\underset{k=1}{\overset{u}{\prod <br><br>}}<br><br><br><br>R<br><br>\left(p_{i_k}\right)<br><br>}\right]$

where h(p_s) represents height of a subtree with the root document of p_s, R(p_s) represents the child documents of p_s, ∥

a∥

represents the number of elements of a, f(p_iu) represents the feature of document p_iu, and where α

is represented as follows;

α

(Δ

l)=λ

<sup>Δ

l</sup>

where Δ

l represents the ancestral distance between the root document and a descendant document and λ

represents a parameter to control the amount of decrease.

11. The system of claim 7 wherein a subtree feature is represented by the following:

$F<br><br>\left[S<br><br>\left(p_s\right)\right]=\mathrm{\alpha <br><br>}<br><br>\left(0\right)<br><br>f<br><br>\left(p_s\right)+\frac{1}{<br><br>R<br><br>\left(p_s\right)<br><br>}<br><br>\underset{u=1}{\overset{h<br><br>\left(p_s\right)-1}{\sum <br><br>}}<br><br>\left[\mathrm{\alpha <br><br>}<br><br>\left(u\right)<br><br>\underset{p_{i_1}\in <br><br>R<br><br>\left(p_s\right)}{\sum <br><br>}<br><br>\underset{p_{i_2}\in <br><br>R<br><br>\left(p_{i_1}\right)}{\sum <br><br>}<br><br>\mathrm{\cdots <br><br>}<br><br>\underset{p_{i_u}\in <br><br>R<br><br>\left(p_{i_{u-1}}\right)}{\sum <br><br>}<br><br>\frac{f<br><br>\left(p_{i_u}\right)}{\underset{k=1}{\overset{u}{\prod <br><br>}}<br><br><br><br>R<br><br>\left(p_{i_k}\right)<br><br>}\right]$

where h(p_s) represents height of a subtree with the root web page of p_s, R(p_s) represents the child documents of p_s, ∥

a∥

represents the number of elements of a, f(p_iu) represents the feature of document p_iu, and where α

is represented as follows;

α

(Δ

l)=λ

<sup>Δ

l</sup>

where Δ

l represents the ancestral distance between the root document and a descendant document and λ

represents a parameter to control the amount of decrease.

12. A computer-readable medium containing instructions for controlling a computer system to identify web pages for a search result for a query, comprising:

calculating a subsite feature for subsites of web pages based on a contribution from a root web page of a subsite and a contribution from descendant web pages of the root web page; and

determining relevance of a subsite to the query based on the calculated subsite feature of the subsite.

13. The computer-readable medium of claim 12 wherein the relevance of a subsite indicates how well the subsite represents a topic distillation for the query.

14. The computer-readable medium of claim 12 wherein the contribution of a descendant web page decreases as an ancestral distance between the root web page and the descendant web page increases.

15. The computer-readable medium of claim 12 wherein the contribution of a descendant web page decreases as a number of sibling web pages to the descendant web page increases.

16. The computer-readable medium of claim 12 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.

17. The computer-readable medium of claim 12 wherein the subsite feature is represented by the following:

$F<br><br>\left[S<br><br>\left(p_s\right)\right]=\mathrm{\alpha <br><br>}<br><br>\left(0\right)<br><br>f<br><br>\left(p_s\right)+\frac{1}{<br><br>R<br><br>\left(p_s\right)<br><br>}<br><br>\underset{u=1}{\overset{h<br><br>\left(p_s\right)-1}{\sum <br><br>}}<br><br>\left[\mathrm{\alpha <br><br>}<br><br>\left(u\right)<br><br>\underset{p_{i_1}\in <br><br>R<br><br>\left(p_s\right)}{\sum <br><br>}<br><br>\underset{p_{i_2}\in <br><br>R<br><br>\left(p_{i_1}\right)}{\sum <br><br>}<br><br>\mathrm{\cdots <br><br>}<br><br>\underset{p_{i_u}\in <br><br>R<br><br>\left(p_{i_{u-1}}\right)}{\sum <br><br>}<br><br>\frac{f<br><br>\left(p_{i_u}\right)}{\underset{k=1}{\overset{u}{\prod <br><br>}}<br><br><br><br>R<br><br>\left(p_{i_k}\right)<br><br>}\right]$

where h(p_s) represents height of the subsite with the root web page of p_s, R(p_s) represents the child web pages of p_s, ∥

a∥

represents the number of elements of a, f(p_iu) represents the feature of web page p_iu, and where α

is represented as follows;

α

(Δ

l)=λ

<sup>Δ

l</sup>

where Δ

l represents the ancestral distance between the root web page and a descendant web page and λ

represents a parameter to control the amount of decrease.

18. The computer-readable medium of claim 12 wherein the subsite features are calculated independently of a query and stored for use when identifying search results of queries.

19. The computer-readable medium of claim 12 wherein the subsite features are calculated based on initial search results of a query.

20. The computer-readable medium of claim 19 wherein the web pages of the search result are root web pages of subsites.