IBM Granted Patent for Pagerank

At the Eleventh International World Wide Web Conference, a poster from John Tomlin, Andrew Tomkins, Jasmine Novak, and Arvind Arasu was presented titled PageRank Computation and the Structure of the Web: Experiments and Algorithms (pdf). The first three authors wrote the paper as IBM employees, and co-author Arvind Arasu is listed on the document as a member of the Computer Science Department at Stanford University.

Three of those four authors are listed as the inventors of a newly granted patent which describes a way to rapidly compute pagerank, which was filed with the US Patent Office around the same time as the presentation of the paper. John Tomlin and Andrew Tomkins are now at Yahoo, and Arvind Arasu is a researcher at Microsoft.

System and method for rapid computation of PageRank
Invented by John Anthony Tomlin, Andrew S. Tomkins, and Arvind Arasu
Assigned to IBM
US Patent 7,089,252
Granted August 8, 2006
Filed April 25, 2002

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:.alpha..alpha..times..times..times..times. ##EQU00001## where x.sub.i is the rank of the page indexed by i, .alpha. 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.sub.ij is defined to be the reciprocal of the number of links pointing out from page j (denoted d.sub.j) if page j points to page i, and zero otherwise.

Rather than describing what the patent contains, I’m going to recommend looking at the paper I refer to in the first paragraph of this post, which is an excellent summary of many of the ideas in the patent. Both patent and paper discuss how difficult it is to compute pagerank for all of the pages on the web, and offer a few solutions which increase speed while also reducing possible errors. As the authors note in a “conclusion” within the patent:

The present invention is directed to web-scale computation of the PageRank static ranking function, incorporating both algorithmic techniques drawn from numerical analysis, and particular structure in the problem instance drawn from web characterization.

Algorithmically, the features of the present invention approach the problem using equation solving rather than eigensystem techniques.

This approach yields significant performance improvements over power iteration. Further, it allows exploitation of the well-known “bow tie” characterization of the web to partition the problem into independent subproblems.

Finally, the characterization of the expansion properties of the graph as a whole versus the graph of inter-site connectivity explains the poor performance of power iteration.

For any who read the patent and paper and want to delve deeper, the following are cited in the patent as references:

U.S. Patent Documents

Other References

5 thoughts on “IBM Granted Patent for Pagerank”

  1. Pingback: IBM получила патент, касающийся PageRank « СоНоты
  2. Hi Enrique,

    There are a couple of patents for PageRank, and both of them were originally assigned to Stanford University, since they were created while the inventors were working/students at Stanford. Google does not own the PageRank patents, but the did sign a deal for the exclusive use of the technology described in the patents until 2011.

    The “PageRank” described in this IBM patent differs from the PageRank described in the Stanford patents in a number of ways.

  3. Hi Peter,

    I think a lot of people probably think that as well. Google, Yahoo, and Microsoft have all followed up with newer patent filings that provide variations on PageRank since the first couple of PageRank Patents were published, but the original two come from Stanford University.

Comments are closed.