Bingo : Radix-based Bias Factorization for Random Walk on Dynamic Graphs

Pinhuan Wang, Chengying Huan, Zhibin Wang, Chen Tian, Yuede Ji, Hang Liu · 2025

Read Bingo : Radix-based Bias Factorization for Random Walk on Dynamic Graphs by Pinhuan Wang, Chengying Huan, Zhibin Wang, Chen Tian, Yuede Ji, Hang Liu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10233.txt.

Description

Wang and five co-authors present Bingo, a graphics-chip engine for random walks on graphs that change over time, in a paper from twenty twenty-five. Random walks extract key signals from large networks in many applications. Real graphs change constantly, yet prior engines handle updates poorly. Bingo aims for fast streaming and batched updates plus rapid sampling.

A radix-based factorization of walk bias allows constant-time sampling with fast updates. A group-adaptive layout slashes memory use dramatically. Graphics-aware batching exploits massive parallelism for bulk updates. Across applications and data sets, Bingo beats prior engines by wide margins. Top speedups exceed two hundred seventy times the best rival system.

Catalog record

CREATORPinhuan Wang, Chengying Huan, Zhibin Wang, Chen Tian, Yuede Ji, Hang Liu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10233

Browse the full library · About the Tower of Babel