Title: Fast parallel computation of PageRank scores with improved convergence time
Authors: Hema Dubey; Nilay Khare
Addresses: Department of CSE, Maulana Azad National Institute of Technology, Bhopal, India ' Department of CSE, Maulana Azad National Institute of Technology, Bhopal, India
Abstract: PageRank is a conspicuous link-based approach used by many search engines in order to rank its search results. PageRank algorithm is based on performing iterations for calculating PageRank of web pages until the convergent point is met. The computational cost of this algorithm is very high for very large web graphs. So to overcome this drawback, in this paper we have proposed a fast parallel computation of PageRank which uses standard deviation technique to normalise the PageRank score of each web page. The proposed work is experimented on standard datasets taken from Stanford large network dataset collection, on a machine having multicore architecture using CUDA programming paradigm. We observed from the experiments that the proposed fast parallel PageRank algorithm needs lesser number of iterations to converge as compared to existing parallel PageRank method. We also determined that there is a speed up of about 2 to 10 for nine different standard datasets for the proposed algorithm over the existing algorithm.
Keywords: PageRank; normalisation; standard deviation; parallel computation; graphics processing unit; GPU; compute unified device architecture; CUDA.
DOI: 10.1504/IJDMMM.2022.122039
International Journal of Data Mining, Modelling and Management, 2022 Vol.14 No.1, pp.63 - 88
Received: 23 Nov 2019
Accepted: 06 Jul 2020
Published online: 08 Apr 2022 *