System and method for rapid computation of PageRank

• US 7,089,252 B2
• Filed: 04/25/2002
• Issued: 08/08/2006
• Est. Priority Date: 04/25/2002
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Arasu, Arvind, Tomlin, John Anthony, Tomkins, Andrew S.
• Primary Examiner(s): LE, UYEN T
• Application Number:
  US10/132,047
• Publication Number:
  US 20030204502A1
• Time in Patent Office: 1,566 Days
• Field of Search: 707/1, 707/100, 707/101, 707/102, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: G06F 17/12 Simultaneous equations , e.g. systems of linear equations
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method of ranking a plurality of linked documents. The method comprises obtaining a plurality of documents, and determining a rank of each document. The rank of each document is generally a function of a rank of all other documents in the plurality of documents which point to the document and is determined by solving, by equation-solving methods (including Gauss-Seidel iteration and partitioning) of a set of equations wherein:

$x_i=\left(1-\alpha \right)+\alpha \sum _j^{}{a}_{\mathrm{ij}}{x}_j,$
where x_i is the rank of the page indexed by i, α is a number strictly between 0 and 1.0, the summation is over all indices j such that page j points to page i, and a_ij is defined to be the reciprocal of the number of links pointing out from page j (denoted d_j) if page j points to page i, and zero otherwise.

Claims

1. A method for determining a ranking of each page in a network of linked pages, some pages being linked to other pages and at least some pages being linking pages or a combination thereof, the method comprising;

obtaining the linked pages from a web-based structure comprising a plurality of input segments I with input nodes P, a plurality of output segments O with output nodes Q, a plurality of strongly connected segments S connected to both the input segments, and output segments, and nodes T interconnecting the input and output segments;

forming a matrix structure defined by the input segments I, the input nodes P, the output segments O, the output nodes Q, the strongly connected segments S, and the nodes T, such that the input segments I, the input nodes P, the output segments O, the output nodes Q, the strongly connected segments S, and the nodes T are arranged along the main diagonal of the matrix structure; and

partitioning the matrix structure in order to solve for the rank of each page via a sequence of smaller systems of equations.

2. The method of claim 1 wherein a subset of the sequence of smaller systems of equations are solved in order.

3. The method of claim 1 wherein a subset of the sequence of smaller systems of equations are solved in parallel.

4. The method of claim 1 wherein one of the sequence of smaller systems of equations is resolved after a rank vector is computed.