Efficient computation of web page rankings

• US 7,512,587 B2
• Filed: 07/01/2004
• Issued: 03/31/2009
• Est. Priority Date: 07/01/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank David
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): CAO, PHUONG THAO
• Application Number:
  US10/882,970
• Publication Number:
  US 20060004811A1
• Time in Patent Office: 1,734 Days
• Field of Search: 707/7, 707/2, 707/5, 709/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

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.

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; and

using the updated ranking to generate search results.

2. The computer-readable storage medium of claim 1 wherein the objects are web pages.

3. The computer-readable storage medium of claim 1 wherein selecting the subset comprises selecting the same subset at each iteration.

4. The computer-readable storage medium of claim 1 wherein selecting the subset comprises choosing objects with relatively large stored error.

5. The computer-readable storage medium of claim 1 wherein the steps are executed by a first processing node, and farther comprising:

receiving errors produced by a second processing node; and

applying the errors produced by the second processing node to the stored errors.

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; and

using the updated ranking to generate search results.

7. The method of claim 6 wherein the objects are web pages.

8. The method of claim 6 wherein selecting the subset comprises selecting the same subset at each iteration.

9. The method of claim 6 wherein selecting the subset comprises choosing objects with relatively large stored error.

10. The method of claim 6 wherein the steps are executed by a first processing node, and further comprising:

receiving errors produced by a second processing node; and

applying the errors produced by the second processing node to the stored errors.

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; and

using the updated ranking to generate search results.

12. The system of claim 11 wherein the objects are web pages.

13. The system of claim 11 wherein selecting the subset comprises selecting the same subset at each iteration.

14. The system of claim 11 wherein selecting the subset comprises choosing objects with relatively large stored error.