Computational & Technology Resources
an online resource for computational,
engineering & technology publications
Civil-Comp Proceedings
ISSN 1759-3433
CCP: 105
PROCEEDINGS OF THE NINTH INTERNATIONAL CONFERENCE ON ENGINEERING COMPUTATIONAL TECHNOLOGY
Edited by:
Paper 29

Parallel Computation of Pagerank using Extrapolation and Relaxation Techniques

H. Migallón1, V. Migallón2, J.A. Palomino2 and J. Penadés2

1Department of Physics and Computer Architectures, University Miguel Hernández, Elche, Alicante, Spain
2Department of Computer Science and Artificial Intelligence, University of Alicante, Spain

Full Bibliographic Reference for this paper
, "Parallel Computation of Pagerank using Extrapolation and Relaxation Techniques", in , (Editors), "Proceedings of the Ninth International Conference on Engineering Computational Technology", Civil-Comp Press, Stirlingshire, UK, Paper 29, 2014. doi:10.4203/ccp.105.29
Keywords: pagerank, parallel algorithms, power method, relaxation and extrapolation, shared memory, distributed memory..

Summary
The pagerank algorithm for determining the importance of web pages has become a central technique in web search. This algorithm uses the power method to compute successive iterates that converge to the principal eigenvector of the Markov chain representing the web link graph. In this paper we present an effective heuristic relaxed and extrapolated algorithm based on the power method that accelerates its convergence. Two strategies of data distribution have been used: row-wise partitioning and nonzero elements partitioning. An hybrid parallel implementation has been designed by combining various OpenMP threads for each MPI process. The results show that the proposed algorithms can speed up the convergence time significantly with respect to the parallel Power algorithm.

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £45 +P&P)