Home Dynamic Batch Parallel Algorithms for Updating PageRank

Publications

Dynamic Batch Parallel Algorithms for Updating PageRank

Author : Dr Subhajit Sahu

Year : 2022

Publisher : Institute of Electrical and Electronics Engineers Inc.

Source Title : Proceedings - 2022 IEEE 36th International Parallel and Distributed Processing Symposium Workshops, IPDPSW 2022

Document Type :

Abstract

The design and implementation of parallel algorithms for dynamic graph problems is attracting significant research attention in the recent years, driven by numerous applications to social network analysis, neuroscience, and protein interaction networks. One such problem is the computation of PageRank values of vertices in a directed graph. This paper presents two new parallel algorithms for recomputing the PageRank values of vertices in a dynamic graph. Our techniques require the recomputation of the PageRank of only the vertices affected by the insertion/deletion of a batch of edges. We conduct detailed experimental studies of our algorithm on a set of 11 real-world graphs. Our results on Intel Xeon Silver 4116 CPU and NVIDIA Tesla V100 PCIe 16GB GPU indicate that our algorithms outperform static and dynamic update algorithms by 6.1times: and 8.6times {on} the CPU, and by 9.8×and 9.3times{on} the GPU respectively. We also compare the performance of the algorithms in batched mode to cumulative single-edge updates.