BINGO: Radix-based Bias Factorization for Random Walk on Dynamic Graphs
Published in EuroSys 25, 2025
Recommended citation: Wang, Pinhuan and Huan, Chengying and Wang, Zhibin and Tian, Chen and Ji, Yuede and Liu, Hang. "BINGO: Radix-based Bias Factorization for Random Walk on Dynamic Graphs." In Proceedings of the Twentieth European Conference on Computer Systems. pp. 605-620. 2025. https://doi.org/10.1145/3689031.3717456
This paper presents Bingo, a GPU-based random walk engine designed for dynamic graphs. Unlike existing systems that struggle with updates, Bingo supports both fast streaming updates and high-throughput batch updates. To achieve this, the authors propose a radix-based bias factorization for constant-time sampling, a group-adaption method to save space, and GPU-friendly designs for efficient updates. Experiments show that Bingo significantly outperforms previous methods, with up to 271× speedup on various tasks and datasets.
Recommended citation: Wang, Pinhuan and Huan, Chengying and Wang, Zhibin and Tian, Chen and Ji, Yuede and Liu, Hang. “BINGO: Radix-based Bias Factorization for Random Walk on Dynamic Graphs.” In Proceedings of the Twentieth European Conference on Computer Systems. pp. 605-620. 2025.