Imperial College London
Alternate

ProfessorWilliamKnottenbelt

Faculty of Engineering, Department of Computing

Professor of Applied Quantitative Analysis
 
 
 
//

Contact

 

+44 (0)20 7594 8331w.knottenbelt Website

 
 
//

Location

 

E363ACE ExtensionSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@inproceedings{Bradley:2005:10.1007/11549970_12,
author = {Bradley, JT and de, Jager DV and Knottenbelt, WJ and Trifunovic, A},
doi = {10.1007/11549970_12},
pages = {155--171},
publisher = {Springer-Verlag},
title = {Hypergraph Partitioning for Faster Parallel PageRank Computation},
url = {http://dx.doi.org/10.1007/11549970_12},
year = {2005}
}
Download

RIS format (EndNote, RefMan)

TY  - CPAPER
AB  - 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.
AU  - Bradley,JT
AU  - de,Jager DV
AU  - Knottenbelt,WJ
AU  - Trifunovic,A
DO  - 10.1007/11549970_12
EP  - 171
PB  - Springer-Verlag
PY  - 2005///
SN  - 0302-9743
SP  - 155
TI  - Hypergraph Partitioning for Faster Parallel PageRank Computation
UR  - http://dx.doi.org/10.1007/11549970_12
UR  - http://pubs.doc.ic.ac.uk/hypergraph-fast-pagerank/
ER  -
Download