Method, system and computer product for classifying web content nodes based on relationship scores derived from mapping content nodes, topical seed nodes and evaluation nodes

• US 7,739,209 B1
• Filed: 01/06/2006
• Issued: 06/15/2010
• Est. Priority Date: 01/14/2005
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Kosmix Corporation
• Inventors: Rajaraman, Anand
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Kennedy; Adrian L
• Application Number:
  US11/327,833
• Time in Patent Office: 1,621 Days
• Field of Search: None
• US Class Current: 706/20
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways

Abstract

Determining the relevance of a web node is disclosed. A seed score value of a first type is assigned to a seed set of nodes. A score value of a second type is derived for the web node based on a mapping of a reachability relationship between one or more seed nodes and the web node. A score value of the first type is derived for the web node based on a mapping of a reachability relationship between the web node and one or more evaluation nodes having derived weight values of the second type. Content analysis is performed.

Claims

1. A method comprising:

assigning one or more source score values to one or more seed nodes included in a seed set of nodes, wherein the seed set of nodes is representative of a topic;

deriving a destination score value for a first web node based on a mapping of a reachability relationship between one or more seed nodes and the first web node;

deriving a source score value for the first web node based on a mapping of a reachability relationship between the first web node and one or more evaluation nodes, each of the one or more evaluation nodes having, respectively, a derived destination score;

determining, based at least in part on at least one of the destination score value of the first web node and the source score value of the first web node, that additional processing should be performed on the first web node;

determining that additional processing should not be performed on a second web node; and

classifying the content of the first web node.

2. The method of claim 1 further comprising combining at least one score value with at least one content similarity score.

3. The method of claim 1 further comprising computing a term distribution vector.

4. The method of claim 1 further comprising computing a distance metric.

5. The method of claim 4 further comprising adjusting a score value of a node based at least in part on the distance metric.

6. The method of claim 4 further comprising pruning a node based at least in part on the distance metric.

7. A system comprising:

a processor configured to;

assign one or more source score values to one or more seed nodes included in a seed set of nodes, wherein the seed set of nodes is representative of a topic;

derive a destination score value for a first web node based on a mapping of a reachability relationship between one or more seed nodes and the first web node;

derive a source score value for the first web node based on a mapping of a reachability relationship between the first web node and one or more evaluation nodes, each of the one or more evaluation nodes having, respectively, a derived destination score;

determine, based at least in part on at least one of the destination score value of the first web node and the source score value of the first web node, that additional processing should be performed on the first web node;

determine that additional processing should not be performed on a second web node; and

classify the content of the first web node; and

a memory coupled with the processor, wherein the memory provides the processor with instructions.

8. The system of claim 7 wherein the processor is further configured to combine at least one score value with at least one content similarity score.

9. The system of claim 7 wherein the processor is further configured to compute a term distribution vector.

10. The system of claim 7 wherein the processor is further configured to compute a distance metric.

11. The system of claim 10 wherein the processor is further configured to adjust a score value of a node based at least in part on the distance metric.

12. The system of claim 10 wherein the processor is further configured to prune a node based at least in part on the distance metric.

13. A computer program product embodied in a computer readable medium and comprising computer instructions for:

assigning one or more source score values to one or more seed nodes included in a seed set of nodes, wherein the seed set of nodes is representative of a topic;

deriving a destination score value for a first web node based on a mapping of a reachability relationship between one or more seed nodes and the first web node;

deriving a source score value for the first web node based on a mapping of a reachability relationship between the first web node and one or more evaluation nodes, each of the one or more evaluation nodes having, respectively, a derived destination score;

determining, based at least in part on at least one of the destination score value of the first web node and the source score value of the first web node, that additional processing should be performed on the first web node;

determining that additional processing should not be performed on a second web node; and

classifying the content of the first web node.

14. The computer program product of claim 13 further comprising instructions for combining at least one score value with at least one content similarity score.