Advertisement
Published in:
2007 | OriginalPaper | Chapter
Parallelizing the Computation of PageRank
Authors : John Wicks, Amy Greenwald
Published in: Algorithms and Models for the Web-Graph
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper presents a technique we call
ParaSolve
that exploits the sparsity structure of the web graph matrix to improve on the degree of parallelism in a number of distributed approaches for computating PageRank. Specifically, a typical algorithm (such as power iteration or GMRES) for solving the linear system corresponding to PageRank, call it
LinearSolve
, may be converted to a distributed algorithm,
Distrib(LinearSolve)
, by partitioning the problem and applying a standard technique (i.e.,
Distrib
). By reducing the number of inter-partition multiplications, we may greatly increase the degree of parallelism, while achieving a similar degree of accuracy. This should lead to increasingly better performance as we utilize more processors. For example, using
GeoSolve
(a variant of Jacobi iteration) as our linear solver and the 2001 web graph from Stanford’s WebBase project, on 12 processors
ParaSolve(GeoSolve)
outperforms
Distrib(GeoSolve)
by a factor of 1.4, while on 32 processors the performance ratio improves to 2.8.