Efficiently ranking web pages via matrix index manipulation and improved caching

• US 20060026191A1
• Filed: 07/30/2004
• Published: 02/02/2006
• Est. Priority Date: 07/30/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank David
• Granted Patent: US 7,379,947 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and systems are described for computing page rankings more efficiently. Using an interconnectivity matrix describing the interconnection of web pages, a new matrix is computed. The new matrix is used to compute the average of values associated with each web page'"'"'s neighboring web pages. The secondary eigenvector of this new matrix is computed, and indices for web pages are relabeled according to the eigenvector. The data structure storing the interconnectivity information is preferably also physically sorted according to the eigenvector. By reorganizing the matrix used in the web page ranking computations, caching is performed more efficiently, resulting in faster page ranking techniques. Methods for efficiently allocating the distribution of resources are also described.

Claims

1. A method of ranking objects in a collection of objects, one or more of the objects in the collection having links to other objects in the collection, the method comprising:

ordering the objects according to their proximity to other objects in the collection with respect to the links; and

storing the links between objects in a memory according to the ordering of the objects.

2. The method of claim 1, the collection of objects and links is represented by a first matrix, the ordering comprising:

computing a second matrix relative to the first matrix;

approximating a secondary eigenvector of the second matrix; and

labeling the objects relative to the values in the approximation to the secondary eigenvector.

3. The method of claim 2 wherein the second matrix represents a function that computes for each object an approximate average of values associated with objects linked to the each object.

4. The method of claim 1, the method further comprising:

computing rankings for the objects using the links stored in the memory.

5. The method of claim 4, the computing comprising using a cache to temporarily store links recently accessed from the memory.

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

7. A computer-readable medium including computer-executable instructions facilitating the ranking of objects in a collection of objects, one or more of the objects in the collection having links to other objects in the collection, the computer-executable instructions performing the steps of:

ordering the objects according to their proximity to other objects in the collection with respect to the links; and

storing the links between objects in a memory according to the ordering of the objects.

8. The computer-readable medium of claim 7, the collection of objects and links is represented by a first matrix, the ordering comprising the steps of:

computing a second matrix relative to the first matrix;

approximating a secondary eigenvector of the second matrix; and

labeling the objects relative to the values in the approximation to the secondary eigenvector.

9. The computer-readable medium of claim 8 wherein the second matrix represents a function that computes for each object an approximate average of values associated with objects linked to the each object.

10. The computer-readable medium of claim 7, the computer-executable instructions further performing the step of:

computing rankings for the objects using the links stored in the memory.

11. The computer-readable medium of claim 10, the computing rankings comprising using a cache to temporarily store links recently accessed from the memory.

12. A method of ordering objects from a collection of interconnected objects, the interconnection of objects represented by a first matrix, the method comprising:

computing a second matrix relative to the first matrix;

approximating a secondary eigenvector of the second matrix; and

ordering the objects relative to the values in the approximation to the secondary eigenvector.

13. The method of claim 12 wherein the objects are web pages.

14. The method of claim 12 wherein the second matrix represents a function that computes for each object an approximate average of values associated with objects connected to the each object.

15. The method of claim 12 wherein approximating a secondary eigenvector comprises:

selecting initial values for a first vector; and

repeating the steps of;

multiplying the second matrix by the first vector to obtain a second vector;

centering the second vector; and

replacing the values of the first vector by the values of the second vector;

until a termination condition is satisfied.

16. The method of claim 15 wherein centering the second vector comprises adding a fixed amount to each entry in the second vector such that the average of the second vector'"'"'s entries is zero.

17. The method of claim 15 further comprising normalizing the second vector.

18. A computer-readable medium including computer-executable instructions facilitating the ordering of objects in a collection of interconnected objects, the interconnection of objects represented by a first matrix, the computer-executable instructions performing the steps of:

computing a second matrix relative to the first matrix;

approximating a secondary eigenvector of the second matrix; and

ordering the objects relative to the values in the approximation to the secondary eigenvector.

19. The computer-readable medium of claim 18 wherein the objects are web pages.

20. The computer-readable medium of claim 18 wherein the second matrix represents a function that computes for each object an approximate average of values associated with objects connected to the each object.

21. The computer-readable medium of claim 18 wherein approximating a secondary eigenvector comprises:

selecting initial values for a first vector; and

repeating the steps of;

multiplying the second matrix by the first vector to obtain a second vector;

centering the second vector; and

replacing the values of the first vector by the values of the second vector;

until a termination condition is satisfied.

22. The computer-readable medium of claim 21 wherein centering the second vector comprises adding a fixed amount to each entry in the second vector such that the average of the second vector'"'"'s entries is zero.

23. The computer-readable medium of claim 18, wherein the objects are resources in a distributed computing system comprising a plurality of servers, the computer-readable medium further facilitating the allocating of one or more of the interconnected resources among the plurality of servers, and further performing the step of:

allocating the resources to the plurality of servers in accordance with the ordering.

24. A computer-readable medium including computer-executable instructions facilitating the ranking of objects in a collection of interconnected objects, a description of the interconnection stored in a memory according to a first ordering of the objects, the computer-executable instructions performing the step of:

re-ordering the objects relative to their proximity to the other objects via the interconnection.

25. The computer-readable medium of claim 24, the computer-executable instructions further performing the step of:

computing rankings for the objects by using the re-ordering of the objects.

26. The computer-readable medium of claim 25, the computing comprising using a cache to temporarily store interconnection description information recently accessed from the memory.