paint-brush
Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computingby@pagerank

Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computing

by PageRankJanuary 22nd, 2025
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

Dynamic Frontier PageRank evaluation uses a 64-core AMD EPYC-7742 system with diverse datasets, optimizing batch updates and leveraging parallel processing. Key configurations include frontier tolerance, damping factors, and asynchronous computations, balancing runtime and accuracy. Tests with graphs of up to 214M vertices and 1.98B edges confirm superior speedups and scalability compared to other methods.
featured image - Dynamic Frontier PageRank Achieves Efficiency and Accuracy with Batch Updates and Parallel Computing
PageRank HackerNoon profile picture

Author:

(1) Subhajit Sahu, IIIT Hyderabad, Hyderabad, Telangana, India ([email protected]).

Abstract and 1 Introduction

2 Related Work

3 Preliminaries

4 Approach

5.1 Experimental Setup

5.2 Performance of Dynamic Frontier PageRank

5.3 Strong Scaling of Dynamic Frontier PageRan

6 Conclusion, Acknowledgments, and References

5. EVALUATION

5.1 Experimental Setup

5.1.1 System used. We conduct experiments on a system equipped with an AMD EPYC-7742 processor, with 64 cores and operating at a frequency of 2.25 GHz. Each core has a 4 MB L1 cache, a 32 MB L2 cache, and shares a 256 MB L3 cache. The server is configured with 512 GB of DDR4 system memory and operates on Ubuntu 20.04.



5.1.3 Dataset. We use four graph classes sourced from the SuiteSparse Matrix Collection [14], as detailed in Table 1. The number of vertices in these graphs range from 3.07 million to 214 million, with edge counts spanning from 37.4 million to 1.98 billion. To address the impact of dead ends (vertices lacking out-links), a global teleport rank computation is needed in each iteration. We mitigate this overhead by adding self-loops to all vertices in the graph [1, 15].





This paper is available on arxiv under CC BY-NC-SA 4.0 DEED license.