Double iterative flavored rank

Patent metadata

Field	Value
Publication number	US-9286387-B1
Application number	US-16562305-A
Country	US
Kind code	B1
Filing date	Jun 22, 2005
Priority date	Jan 14, 2005
Publication date	Mar 15, 2016
Grant date	Mar 15, 2016

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.

First claim

What is claimed is:

1. A method of determining relevance of a web node comprising:
computing, by a computer system, an unbiased probability vector for a collection of nodes, the collection of nodes comprising one or more seed nodes included within a seed set of nodes, the web node, and one or more evaluation nodes, the unbiased probability vector setting forth a plurality of reachability relationships, each corresponding to a different pair of nodes of the collection of nodes and setting forth a probability that a random surfer beginning on a first node of the different pair of nodes will end up on a second node of the different pair of nodes;
assigning, by the computer system, one or more source score values to one or more seed nodes;
setting, by the computer system, a source expansion factor to a value that allows some probability set forth in the unbiased probability vector with respect to the one or more seed nodes to spread out into other nodes within the collection of nodes, while retaining a portion of the probability within the one or more seed nodes;
deriving, by the computer system, a destination score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the one or more seed nodes and the web node; and
deriving, by the computer system as limited by the source expansion factor, a source score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the web node and the one or more evaluation nodes and based on a derived destination score associated, respectively, with each of the one or more evaluation nodes.

2. The method of claim 1 wherein a first seed node included in the seed set of nodes is assigned a first source score value and wherein a second seed node included in the seed set of nodes is assigned a second source score value.

3. The method of claim 1 wherein at least one seed node of the one or more seed nodes is also a web node.

4. The method of claim 1 wherein the destination score values associated with each of the one or more evaluation nodes are based at least in part on an exponential decay.

5. The method of claim 1 wherein deriving the destination score value for the web node is performed iteratively and includes summing results of multiple iterations with respect to the web node.

6. The method of claim 1 wherein deriving the destination score value for the web node is performed iteratively and includes averaging results of multiple iterations with respect to the web node.

7. The method of claim 1 further comprising updating the seed set of nodes.

8. A system for determining relevance of a web node comprising:
one or more processors;
memory operably connected to the one or more processors; and
the memory storing one or more modules programmed to:
compute an unbiased probability vector for a collection of nodes, the collection of nodes comprising one or more seed nodes included within a seed set of nodes, the web node, and one or more evaluation nodes, the unbiased probability vector setting forth a plurality of reachability relationships, each corresponding to a different pair of nodes of the collection of nodes and setting forth a probability that a random surfer beginning on a first node of the different pair of nodes will end up on a second node of the different pair of nodes;
assign one or more source score values to the one or more seed nodes;
set a source expansion factor to a value that allows some probability set forth in the unbiased probability vector with respect to the one or more seed nodes to spread out into other nodes within the collection of nodes, while retaining a portion of the probability within the one or more seed nodes;
derive a destination score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the one or more seed nodes and the web node; and
derive, as limited by the source expansion factor, a source score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the web node and the one or more evaluation nodes and based on a derived destination score associated, respectively, with each of the one or more evaluation nodes.

9. The system of claim 8 wherein the one or more processors are further configured to update the seed set of nodes.

10. The system of claim 8 wherein at least one web node that was not in the seed set of nodes is subsequently added to the seed set of nodes.

11. A computer program product for determining relevance of a web node, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:
computing an unbiased probability vector for a collection of nodes, the collection of nodes comprising one or more seed nodes included within a seed set of nodes, the web node, and one or more evaluation nodes, the unbiased probability vector setting forth a plurality of reachability relationships, each corresponding to a different pair of nodes of the collection of nodes and setting forth a probability that a random surfer beginning on a first node of the different pair of nodes will end up on a second node of the different pair of nodes;
assigning one or more source score values to the one or more seed nodes;
setting a source expansion factor to a value that allows some probability set forth in the unbiased probability vector with respect to the one or more seed nodes to spread out into other nodes within the collection of nodes, while retaining a portion of the probability within the one or more seed nodes;
deriving a destination score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the one or more seed nodes and the web node;
deriving, as limited by the source expansion factor, a source score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the web node and the one or more evaluation nodes and based on a derived destination score associated, respectively, with each of the one or more evaluation nodes.

12. A method of determining relevance of a web node comprising:
computing, by a computer system, an unbiased probability vector for a collection of nodes, the collection of nodes comprising one or more seed nodes included within a seed set of nodes, the web node, and one or more evaluation nodes, the unbiased probability vector setting forth a plurality of reachability relationships, each corresponding to a different pair of nodes of the collection of nodes and setting forth a probability that a random surfer beginning on a first node of the different pair of nodes will end up on a second node of the different pair of nodes;
assigning, by the computer system, one or more destination score values to the one or more seed nodes;
setting, by the computer system, a destination expansion factor to a value that allows some probability set forth in the unbiased probability vector with respect to the one or more seed nodes to spread out into other nodes within the collection of nodes, while retaining a portion of the probability within the one or more seed nodes;
deriving, by the computer system, a source score value for the web node based on a mapping of a reachability relationship of the plurality of reachability relationships between the one or more seed nodes and the web node; and
deriving, by the computer system as limited by the destination expansion factor, a destination score value

Assignees

• Rajaraman Anand
• Wal Mart Stores Inc

Inventors

• Rajaraman Anand

Classifications

• G06F17/30867

  Physics · mapped topic

• G06F17/3071

  Physics · mapped topic

• G06F17/30864 Primary

  Physics · mapped topic

• G06F17/30321

  Physics · mapped topic

• G06F17/30598

  Physics · mapped topic