Non-Stationary Acceleration Strategies for PageRank Computing

Héctor Migallón, Violeta Migallón and José Penadés
Additional contact information
Héctor Migallón: Department of Physics and Computer Architecture, Miguel Hernández University, Elche, E-03202 Alicante, Spain
Violeta Migallón: Department of Computer Science and Artificial Intelligence, University of Alicante, 03071 Alicante, Spain
José Penadés: Department of Computer Science and Artificial Intelligence, University of Alicante, 03071 Alicante, Spain

Mathematics, 2019, vol. 7, issue 10, 1-18

Abstract: In this work, a non-stationary technique based on the Power method for accelerating the parallel computation of the PageRank vector is proposed and its theoretical convergence analyzed. This iterative non-stationary model, which uses the eigenvector formulation of the PageRank problem, reduces the needed computations for obtaining the PageRank vector by eliminating synchronization points among processes, in such a way that, at each iteration of the Power method, the block of iterate vector assigned to each process can be locally updated more than once, before performing a global synchronization. The parallel implementation of several strategies combining this novel non-stationary approach and the extrapolation methods has been developed using hybrid MPI/OpenMP programming. The experiments have been carried out on a cluster made up of 12 nodes, each one equipped with two Intel Xeon hexacore processors. The behaviour of the proposed parallel algorithms has been studied with realistic datasets, highlighting their performance compared with other parallel techniques for solving the PageRank problem. Concretely, the experimental results show a time reduction of up to 58.4 % in relation to the parallel Power method, when a small number of local updates is performed before each global synchronization, outperforming both the two-stage algorithms and the extrapolation algorithms, more sharply as the number of processes increases.

Keywords: PageRank; power method; non-stationary iterations; parallel processing; distributed shared memory; hybrid MPI/OpenMP (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/10/911/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/10/911/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:7:y:2019:i:10:p:911-:d:272577

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().