Parallel-friendly personalized pageranks with operation shuffling

• Main Author: Li, Chunbo
• Other Authors: Luo Siqiang
• Format: Thesis-Master by Research
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Engineering::Computer science and engineering
• Online Access: https://hdl.handle.net/10356/172018
• Institution: Nanyang Technological University

Given a graph G and a source node s, the single-source Personalized PageRank (SSPPR) π(s, v) measures the importance of the node v with respect to the source node s, thus SSPPR is widely adopted in many graph analysis technologies. Specifically, π(s, v) is the probability that a random walk starts from s and stops at v. While state-of-the-art solutions for SSPPR are able to handle dynamic graphs with index-based approaches, challenges arise when processing the mixed workload of updates and queries in a multi-core system. Firstly, since it is important to ensure the high accuracy of SSPPR, the updates have to be executed in time, limiting the degree of parallelism due to the contention of data updates. Secondly, the contention of threads for index results in big restrictions. To address these limitations, we propose Parallel-Friendly Shuffling (PFS). PFS efficiently shuffles the updates and queries to a parallel-friendly order, without losing the theoretical accuracy guarantee. This allows for better utilization of multi-core systems and addresses the challenges of limited query parallelism and thread contention for index. We provide an extensive experimental comparison to demonstrate the efficiency of the PFS method. As shown in our experimental results, using 10 threads, PFS achieves up to 5 times smaller response time than baseline approaches.