Bibliographic Details
| Title: |
Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs |
| Authors: |
Wang, Pinhuan, Huan, Chengying, Wang, Zhibin, Tian, Chen, Ji, Yuede, Liu, Hang |
| Source: |
Proceedings of the Twentieth European Conference on Computer Systems, 2025, pp. 605-620 |
| Publication Year: |
2025 |
| Collection: |
Computer Science |
| Subject Terms: |
Computer Science - Distributed, Parallel, and Cluster Computing |
| More Details: |
Random walks are a primary means for extracting information from large-scale graphs. While most real-world graphs are inherently dynamic, state-of-the-art random walk engines failed to efficiently support such a critical use case. This paper takes the initiative to build a general random walk engine for dynamically changing graphs with two key principles: (i) This system should support both low-latency streaming updates and high-throughput batched updates. (ii) This system should achieve fast sampling speed while maintaining acceptable space consumption to support dynamic graph updates. Upholding both standards, we introduce Bingo, a GPU-based random walk engine for dynamically changing graphs. First, we propose a novel radix-based bias factorization algorithm to support constant time sampling complexity while supporting fast streaming updates. Second, we present a group-adaption design to reduce space consumption dramatically. Third, we incorporate GPU-aware designs to support high-throughput batched graph updates on massively parallel platforms. Together, Bingo outperforms existing efforts across various applications, settings, and datasets, achieving up to a 271.11x speedup compared to the state-of-the-art efforts.
Comment: 17 pages, Published in EuroSys'25 |
| Document Type: |
Working Paper |
| DOI: |
10.1145/3689031.3717456 |
| Access URL: |
http://arxiv.org/abs/2504.10233 |
| Accession Number: |
edsarx.2504.10233 |
| Database: |
arXiv |
