Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs
| 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 |
| FullText | Text: Availability: 0 CustomLinks: – Url: http://arxiv.org/abs/2504.10233 Name: EDS - Arxiv Category: fullText Text: View this record from Arxiv MouseOverText: View this record from Arxiv – Url: https://resolver.ebsco.com/c/xy5jbn/result?sid=EBSCO:edsarx&genre=article&issn=&ISBN=&volume=&issue=&date=20250414&spage=&pages=&title=Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs&atitle=Bingo%3A%20Radix-based%20Bias%20Factorization%20for%20Random%20Walk%20on%20Dynamic%20Graphs&aulast=Wang%2C%20Pinhuan&id=DOI:10.1145/3689031.3717456 Name: Full Text Finder (for New FTF UI) (s8985755) Category: fullText Text: Find It @ SCU Libraries MouseOverText: Find It @ SCU Libraries |
|---|---|
| Header | DbId: edsarx DbLabel: arXiv An: edsarx.2504.10233 RelevancyScore: 1147 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 1146.59143066406 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Wang%2C+Pinhuan%22">Wang, Pinhuan</searchLink><br /><searchLink fieldCode="AR" term="%22Huan%2C+Chengying%22">Huan, Chengying</searchLink><br /><searchLink fieldCode="AR" term="%22Wang%2C+Zhibin%22">Wang, Zhibin</searchLink><br /><searchLink fieldCode="AR" term="%22Tian%2C+Chen%22">Tian, Chen</searchLink><br /><searchLink fieldCode="AR" term="%22Ji%2C+Yuede%22">Ji, Yuede</searchLink><br /><searchLink fieldCode="AR" term="%22Liu%2C+Hang%22">Liu, Hang</searchLink> – Name: TitleSource Label: Source Group: Src Data: Proceedings of the Twentieth European Conference on Computer Systems, 2025, pp. 605-620 – Name: DatePubCY Label: Publication Year Group: Date Data: 2025 – Name: Subset Label: Collection Group: HoldingsInfo Data: Computer Science – Name: Subject Label: Subject Terms Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+Science+-+Distributed%2C+Parallel%2C+and+Cluster+Computing%22">Computer Science - Distributed, Parallel, and Cluster Computing</searchLink> – Name: Abstract Label: Description Group: Ab Data: 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.<br />Comment: 17 pages, Published in EuroSys'25 – Name: TypeDocument Label: Document Type Group: TypDoc Data: Working Paper – Name: DOI Label: DOI Group: ID Data: 10.1145/3689031.3717456 – Name: URL Label: Access URL Group: URL Data: <link linkTarget="URL" linkTerm="http://arxiv.org/abs/2504.10233" linkWindow="_blank">http://arxiv.org/abs/2504.10233</link> – Name: AN Label: Accession Number Group: ID Data: edsarx.2504.10233 |
| PLink | https://login.libproxy.scu.edu/login?url=https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&scope=site&db=edsarx&AN=edsarx.2504.10233 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1145/3689031.3717456 Subjects: – SubjectFull: Computer Science - Distributed, Parallel, and Cluster Computing Type: general Titles: – TitleFull: Bingo: Radix-based Bias Factorization for Random Walk on Dynamic Graphs Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Wang, Pinhuan – PersonEntity: Name: NameFull: Huan, Chengying – PersonEntity: Name: NameFull: Wang, Zhibin – PersonEntity: Name: NameFull: Tian, Chen – PersonEntity: Name: NameFull: Ji, Yuede – PersonEntity: Name: NameFull: Liu, Hang IsPartOfRelationships: – BibEntity: Dates: – D: 14 M: 04 Type: published Y: 2025 |
| ResultId | 1 |