Realtime topk personalized pagerank over large graphs on GPUs

Jieming Shi, Renchi Yang, Tianyuan Jin, Xiaokui Xiao, Yin Yang

Research output: Journal article publicationConference articleAcademic researchpeer-review

3 Citations (Scopus)

Abstract

Given a graph G, a source node s ∈ G and a positive integer k, a top-k Personalized PageRank (PPR) query returns the k nodes with the highest PPR values with respect to s, where the PPR of a node v measures its relevance from the perspective of source s. Top-k PPR processing is a fundamental task in many important applications such as web search, social networks, and graph analytics. This paper aims to answer such a query in realtime, i.e., within less than 100ms, on an Internet-scale graph with billions of edges. This is far beyond the current state of the art, due to the immense computational cost of processing a PPR query. We achieve this goal with a novel algorithm kPAR, which utilizes the massive parallel processing power of GPUs. The main challenge in designing a GPU-based PPR algorithm lies in that a GPU is mainly a parallel computation device, whereas PPR processing involves graph traversals and value propagation operations, which are inherently sequen- tial and memory-bound. Existing scalable PPR algorithms are mostly described as single-thread CPU solutions that are resistant to parallelization. Further, they usually involve complex data structures which do not have efficient adaptations on GPUs. kPAR overcomes these problems via both novel algorithmic designs (namely, adaptive forward push and inverted random walks) and system engineering (e.g., load balancing) to realize the potential of GPUs. Meanwhile, kPAR provides rigorous guarantees on both result quality and worst-case efficiency. Extensive experiments show that kPAR is usually 10x faster than parallel adaptations of existing methods. Notably, on a billion-edge Twitter graph, kPAR answers a top-1000 PPR query in 42.4 milliseconds.

Original languageEnglish
Pages (from-to)15-28
Number of pages14
JournalProceedings of the VLDB Endowment
Volume13
Issue number1
DOIs
Publication statusPublished - 2020
Event46th International Conference on Very Large Data Bases, VLDB 2020 - Virtual, Japan
Duration: 31 Aug 20204 Sep 2020

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Computer Science(all)

Cite this