AESOP home

Publications

Hypergraph Partitioning for Faster Parallel PageRank Computation

Jeremy T. Bradley, Douglas de Jager, William J. Knottenbelt, Aleksandar Trifunovic

Conference or Workshop Paper
EPEW'05, Proceedings of the 2nd European Performance Evaluation Workshop
August, 2005
Lecture Notes in Computer Science
Volume 3670
pp.155–171
Springer-Verlag
DOI 10.1007/11549970_12
Abstract

The PageRank algorithm is used by search engines such as Google to order web pages. It uses an iterative numerical method to compute the maximal eigenvector of a transition matrix derived from the web's hyperlink structure and a user-centred model of web-surfing behaviour. As the web has expanded and as demand for user-tailored web page ordering metrics has grown, scalable parallel computation of PageRank has become a focus of considerable research effort. In this paper, we seek a scalable problem decomposition for parallel PageRank computation, through the use of state-of-the-art hypergraph-based partitioning schemes. These have not been previously applied in this context. We consider both one and two-dimensional hypergraph decomposition models. Exploiting the recent availability of the Parkway 2.1 parallel hypergraph partitioner, we present empirical results on a gigabit PC cluster for three publicly available web graphs. Our results show that hypergraph-based partitioning substantially reduces communication volume over conventional partitioning schemes (by up to three orders of magnitude), while still maintaining computational load balance. They also show a halving of the per-iteration runtime cost when compared to the most effective alternative approach used to date.

PDF of full publication (224 kilobytes)
(need help viewing PDF files?)
GZipped Postscript of full publication (89.7 kilobytes)
(need help viewing GZipped Postscript files?)

Information from pubs.doc.ic.ac.uk/hypergraph-fast-pagerank.