Efficient computation of web page rankings

• US 20060004811A1
• Filed: 07/01/2004
• Published: 01/05/2006
• Est. Priority Date: 07/01/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank David
• Granted Patent: US 7,512,587 B2
• Time in Patent Office: Days
• 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 method of iteratively updating a ranking of one or more objects in a collection of interconnected ranked objects comprising:

at each iteration;

selecting a subset of the collection of objects;

modifying the ranking for objects in the subset by removing errors;

propagating the modification across the interconnection of objects; and

storing as errors, for each object in the collection, the effect of the propagation on each object'"'"'s ranking.

2. The method of claim 1 wherein the objects are web pages.

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

4. The method of claim 1 wherein the method is performed 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.

5. A computer-readable medium including computer-executable instructions facilitating the iterative updating of a ranking of one or more objects in a collection of interconnected ranked objects, computer-executable instructions executing the steps of:

at each iteration;

selecting a subset of the collection of objects;

modifying the ranking for objects in the subset by removing errors;

propagating the modification across the interconnection of objects; and

storing as errors, for each object in the collection, the effect of the propagation on each object'"'"'s ranking.

6. The computer-readable medium of claim 5 wherein the objects are web pages.

7. The computer-readable medium of claim 5 wherein selecting the subset comprises selecting the same subset at each iteration.

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

9. The computer-readable medium of claim 5 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.

10. A computer-readable medium including computer-executable instructions facilitating the ranking one or more objects from an interconnected collection of objects, the interconnection of the objects described by an interconnection description and the objects having an initial ranking description, computer-executable instructions executing the steps of:

initially computing an error description relative to the ranking description and the interconnection description; and

repeatedly performing the steps of;

generating an iterative updater;

updating the ranking description with the iterative updater; and

updating the error description with respect to the interconnection description and the iterative updater.

11. The computer-readable medium of claim 10 wherein generating the updater corresponds to selecting a subset of objects.

12. The computer-readable medium of claim 11 wherein generating the updater further corresponds to selecting a subset of objects with relatively large error in the error description.

13. The computer-readable medium of claim 10 wherein the objects are web pages.

14. The computer-readable medium of claim 10 wherein updating the error description comprises propagating the updated ranks across the interconnection of objects.

15. The computer-readable medium of claim 10 wherein initially computing an error description further comprises applying a change to a second error description, wherein the second error description corresponds to a second ranking description for a second interconnection of the objects, and wherein the second interconnection of the objects differs incrementally from the first interconnection of the objects.

16. The computer-readable medium of claim 10 wherein the method is performed 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.

17. A method of distributively updating a ranking of one or more objects in a collection of interconnected ranked objects comprising:

updating, by a first processor, rankings for objects in a first subset of the collection;

transmitting, by the first processor, errors in the rankings of objects; and

applying, by a second processor, the errors transmitted by the first processor to rankings for objects in a second subset of the collection.

18. The method of claim 17 wherein the first subset and the second subset are disjoint.

19. The method of claim 17 wherein updating by the first processor comprises iteratively:

modifying the ranking for objects in the first subset by removing errors;

propagating the modification across the interconnection of objects; and

storing as errors, for each object in the collection, the effect of the propagation on each object'"'"'s ranking.

20. The method of claim 17 wherein the objects are web pages.

21. A system for distributively updating a ranking of one or more objects in a collection of interconnected ranked objects comprising:

a first processing node for updating rankings of objects in a first subset of the collection; and

a second processing node for updating rankings in a second subset of the collection;

wherein the first processing node transmits to the second processing node errors introduced by its updating of the rankings.

22. The system of claim 21 further comprising a first data structure for storing errors produced by the first processing node'"'"'s updating of the rankings.

23. The system of claim 21 wherein the objects are web pages.

24. The system of claim 21 wherein the first subset and the second subset are disjoint.