System and method for characterizing a web page using multiple anchor sets of web pages

• US 20080082481A1
• Filed: 10/03/2006
• Published: 04/03/2008
• Est. Priority Date: 10/03/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Reed, Benjamin Clay, Ravikumar, Shanmugasundaram, Tomkins, Andrew, Joshi, Amruta Sadanand
• Granted Patent: US 7,912,831 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/95 Retrieval from the web

Abstract

An improved system and method is provided for characterizing a web page using multiple anchor sets of web pages. To do so, web pages in a collection of unknown web pages may be characterized using known anchor sets of web pages with different characterizations that may be linked to the collection of unknown web pages. A direction and method may be selected for propagating a probability distribution between vertices of a graph representing the collection of web pages and vertices of the anchor sets representing the anchor sets of web pages. Methods for propagating the probability distribution in a forward, backward or bidirectional direction are provided. Various quality measures of the characterization of the vertices are provided using the propagated probability distribution. These various quality measures may be paired and combined in different ways to provide a characterization of the vertices representing the unknown web pages.

Claims

1. A computer system for characterizing a web page, comprising:

a characterization engine for characterizing a web page;

a probability distribution engine operably coupled to the characterization engine for generating a probability distribution over the vertices of a graph representing a collection of web pages; and

a characterization measure analyzer operably coupled to the characterization engine for determining a quality measure for the web page using the probability distribution.

2. The system of claim 1 further comprising a forward probability distribution engine operably coupled to the probability distribution engine for generating the probability distribution in a forward direction over the vertices of the graph representing the collection of web pages.

3. The system of claim 1 further comprising a backward probability distribution engine operably coupled to the probability distribution engine for generating the probability distribution in a backward direction over the vertices of the graph representing the collection of web pages.

4. A computer-readable medium having computer-executable components comprising the system of claim 1.

5. A computer-implemented method for characterizing a web page, comprising:

receiving a plurality of anchor sets of web pages;

determining a quality measure of a characterization of a web page using the plurality of anchor sets of web pages; and

outputting an indication of the characterization of the web page.

6. The method of claim 5 wherein determining the quality measure of the characterization of the web page using the plurality of anchor sets of web pages comprises:

determining one or more quality measures of one or more characterizations of the web page using one or more anchor sets of the plurality of anchor sets of web pages; and

combining the one or more quality measures of the one or more characterizations of the web page to generate the quality measure of the characterization of the web page.

7. The method of claim 6 wherein determining the one or more quality measures of the one or more characterizations of the web page using the one or more anchor sets of the plurality of anchor sets of web pages comprises propagating a probability distribution following a forward walk of vertices of a graph representing a collection of web pages.

8. The method of claim 7 wherein propagating the probability distribution following the forward walk of vertices of the graph representing the collection of web pages comprises employing a technique of personalized pagerank.

9. The method of claim 7 wherein propagating the probability distribution following the forward walk of vertices of the graph representing the collection of web pages comprises employing a technique of harmonic rank.

10. The method of claim 6 wherein determining the one or more quality measures of the one or more characterizations of the web page using the one or more anchor sets of the plurality of anchor sets of web pages comprises propagating a probability distribution following a backward walk of vertices of a graph representing a collection of web pages.

11. The method of claim 10 wherein propagating the probability distribution following the backward walk of vertices of the graph representing the collection of web pages comprises employing a technique of personalized pagerank.

12. The method of claim 10 wherein propagating the probability distribution following the backward walk of vertices of the graph representing the collection of web pages comprises employing a technique of harmonic rank.

13. The method of claim 6 wherein determining the one or more quality measures of the one or more characterizations of the web page using the one or more anchor sets of the plurality of anchor sets of web pages comprises generating the one or more characterizations following a forward walk of vertices of a graph representing a collection of web pages without flow conservation.

14. The method of claim 6 wherein determining the one or more quality measures of the one or more characterizations of the web page using the one or more anchor sets of the plurality of anchor sets of web pages comprises generating the one or more characterizations following a backward walk of vertices of a graph representing a collection of web pages without flow conservation.

15. The method of claim 5 wherein determining the quality measure of the characterization of the web page using the plurality of anchor sets of web pages comprises:

determining a first quality measure of a first characterization of the web page using an anchor set with a positive characterization of the plurality of anchor sets of web pages;

determining a second quality measure of a second characterization of the web page using a second anchor set with a negative characterization of the plurality of anchor sets of web pages; and

dividing the first quality measure of the first characterization of the web page by the sum of the first quality measure of the first characterization of the web page and the second quality measure of the second characterization of the web page to generate the quality measure of the characterization of a web page.

16. A computer-readable medium having computer-executable instructions for performing the method of claim 5.

17. A computer system for characterizing a web page, comprising:

means for receiving an anchor set of web pages with a known characterization;

means for determining a quality measure of a characterization of a web page using the anchor set of web pages; and

means for outputting an indication of the characterization of the web page.

18. The computer system of claim 17 further comprising:

means for receiving another anchor set of web pages with a different characterization; and

means for determining another quality measure of a characterization of a web page using the another anchor set of web pages.

19. The computer system of claim 17 wherein means for determining the quality measure of the characterization of the web page using the anchor set of web pages comprises means for propagating a probability distribution on vertices of a graph representing a collection of web pages.

20. The computer system of claim 19 wherein means for propagating the probability distribution on vertices of the graph representing the collection of web pages comprises means for determining a direction for propagating the probability distribution among vertices of the graph.