Efficiently ranking web pages via matrix index manipulation and improved caching

• US 7,379,947 B2
• Filed: 07/30/2004
• Issued: 05/27/2008
• Est. Priority Date: 07/30/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): PANNALA, SATHYANARAYA R
• Application Number:
  US10/903,345
• Publication Number:
  US 20060026191A1
• Time in Patent Office: 1,397 Days
• Field of Search: 707/5, 707/7, 707/200, 707/104.1
• 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 computer-implemented 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 by 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, wherein centering the second vector comprises adding a fixed amount to each entry in the second vector till the average of the second vector'"'"'s entries is zero; and

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

until a termination condition is satisfied;

ordering the objects relative to the values in the approximation to the secondary eigenvector; and

storing the objects according to the ordering relative to the values in file approximation to the secondary eigenvector.

2. A computer-readable storage 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 by performing the steps of;

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, wherein centering the second vector comprises adding a fixed amount to each entry in the second vector till the average of the second vector'"'"'s entries is zero; and

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

until a termination condition is satisfied;

ordering the objects relative to the values in the approximation to the secondary eigenvector; and

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