Efficient computation of web page rankings
First Claim
1. A computer-readable storage medium including computer-executable instructions facilitating iterative updating of a ranking of one or more objects in a collection of interconnected ranked objects characterized by a random walk transition matrix A and a page transition matrix P, the computer-executable instructions comprising steps of:
- selecting a vector x representing an approximation of the ranking of the one or more objects;
updating the ranking by, at each iteration;
selecting a subset of the collection of objects;
computing an update vector y′
as a vector difference Px−
x;
selecting a vector z representing a set of values for propagation through the collection of interconnected ranked objects;
modifying the vector x by adding to the vector x the vector z;
propagating the selected set of values to at least one other object in the collection and outside the subset; and
storing as errors, for each other object in the collection, an effect of the propagation on each other object'"'"'s ranking by modifying the update vector y′
by adding to the update vector y′
a vector difference Az−
z; and
using the updated ranking to generate search results.
2 Assignments
0 Petitions
Accused Products
Abstract
Methods and systems are provided for efficiently computing page rankings of web pages or other interconnected objects. The rankings are produced by efficiently computing a principal eigenvector of a page ranking transition matrix. The methods and systems provided herein can be used to produce page rankings in a distributed and/or incremental manner, and can be used to allocate computing resources to processing page rankings for those pages that most demand them.
-
Citations
14 Claims
-
1. A computer-readable storage medium including computer-executable instructions facilitating iterative updating of a ranking of one or more objects in a collection of interconnected ranked objects characterized by a random walk transition matrix A and a page transition matrix P, the computer-executable instructions comprising steps of:
-
selecting a vector x representing an approximation of the ranking of the one or more objects; updating the ranking by, at each iteration; selecting a subset of the collection of objects; computing an update vector y′
as a vector difference Px−
x;selecting a vector z representing a set of values for propagation through the collection of interconnected ranked objects; modifying the vector x by adding to the vector x the vector z; propagating the selected set of values to at least one other object in the collection and outside the subset; and storing as errors, for each other object in the collection, an effect of the propagation on each other object'"'"'s ranking by modifying the update vector y′
by adding to the update vector y′
a vector difference Az−
z; andusing the updated ranking to generate search results. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A computer implemented method for facilitating iterative updating of a ranking of one or more objects in a collection of interconnected ranked objects characterized by a random walk transition matrix A and a page transition matrix P wherein the method is executed by a processor, the method comprising:
-
selecting a vector x representing an approximation of the ranking of the one or more objects; updating the ranking by, at each iteration; selecting a subset of the collection of objects; computing an update vector y′
as a vector difference Px−
x;selecting a vector z representing a set of values for propagation through the collection of interconnected ranked objects; modifying the vector x by adding to the vector x the vector z; propagating the selected set of values to at least one other object in the collection and outside the subset; and storing as errors in memory, for each other object in the collection, an effect of the propagation on each other object'"'"'s ranking by modifying the update vector y′
by adding to the update vector y′
a vector difference Az−
z; andusing the updated ranking to generate search results. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A system for facilitating iterative updating of a ranking of one or more objects in a collection of interconnected ranked objects characterized by a random walk transition matrix A and a page transition matrix P, the system comprising:
-
a processor operative to execute computer-executable instructions; and memory having stored therein computer-executable instructions for performing steps comprising; selecting a vector x representing an approximation of the ranking of the one or more objects; updating the ranking by, at each iteration; selecting a subset of the collection of objects; computing an update vector y′
as a vector difference Px−
x;selecting a vector z representing a set of values for propagation through the collection of interconnected ranked objects; modifying the vector x by adding to the vector x the vector z; propagating the selected set of values to at least one other object in the collection and outside the subset; and storing as errors, for each other object in the collection, an effect of the propagation on each other object'"'"'s ranking by modifying the update vector y′
by adding to the update vector y′
a vector difference Az−
z; andusing the updated ranking to generate search results. - View Dependent Claims (12, 13, 14)
-
Specification