GPU-based Graph Traversal on Compressed Graphs

Summary: GPU-based graph traversal on compressed graphs enables processing graphs larger than device memory. Introduces Two-Phase Traversal and Task-Stealing to mitigate SIMT divergence and workload imbalance, plus Warp-centric Decoding and Residual Segmentation for power-law graphs, achieving 2x–18x compression with competitive efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5683
Venue: SIGMOD
Year: 2019
Pagerank: 6.1146374e-05
Overall Rank: 4,522 | 68.55%
DOI: 10.1145/3299869.3319871

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,641	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	6.8884895e-05
5,197	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	5.6347409e-05
5,699	EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal in GPUs	2021	VLDB	5.3654927e-05
5,799	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	5.3219334e-05
7,158	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	4.8143783e-05
7,225	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	4.7956162e-05
7,712	Accelerating Exact Constrained Shortest Paths on GPUs	2021	VLDB	4.6715558e-05
10,079	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD	4.1945683e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1945683e-05
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05
10,311	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1945683e-05
11,026	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,676	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010946423
3,233	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	7.3361904e-05
3,670	A Distributed Multi-GPU System for Fast Graph Processing	2018	VLDB	6.8567044e-05
3,834	GTS: A Fast and Scalable Graph Processing Method based on Streaming Topology to GPUs	2016	SIGMOD	6.7173094e-05
4,254	Fast Sparse Matrix-Vector Multiplication on GPUs: Implications for Graph Mining	2011	VLDB	6.3213177e-05
4,577	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.0709631e-05
5,680	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	5.3734643e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,138	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	0.00013727765
4,168	Accelerating Triangle Counting on GPU	2021	SIGMOD	6.391271e-05
5,699	EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal in GPUs	2021	VLDB	5.3654927e-05
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05
9,072	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB	4.4024417e-05
5,040	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD	5.7425187e-05
1,103	Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture	2021	VLDB	0.00014025101
5,799	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	5.3219334e-05
7,225	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	4.7956162e-05
6,985	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8729387e-05