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: 5684
Venue: SIGMOD
Year: 2019
Pagerank: 6.1087614e-05
Overall Rank: 4,525 | 68.56%
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,488	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	7.0460627e-05
5,199	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	5.6294232e-05
5,711	EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal in GPUs	2021	VLDB	5.3603407e-05
5,811	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	5.3168243e-05
7,157	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	4.8097601e-05
7,226	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	4.7910164e-05
7,711	Accelerating Exact Constrained Shortest Paths on GPUs	2021	VLDB	4.6670758e-05
10,079	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD	4.1905499e-05
10,161	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	4.1905499e-05
10,320	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1905499e-05
10,323	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	4.1905499e-05
11,029	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	4.1905499e-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,670	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010944596
3,235	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	7.3298263e-05
3,674	A Distributed Multi-GPU System for Fast Graph Processing	2018	VLDB	6.8502146e-05
3,839	GTS: A Fast and Scalable Graph Processing Method based on Streaming Topology to GPUs	2016	SIGMOD	6.7108721e-05
4,249	Fast Sparse Matrix-Vector Multiplication on GPUs: Implications for Graph Mining	2011	VLDB	6.3173602e-05
4,578	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.0651154e-05
5,693	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	5.3683002e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,138	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	0.00013715114
4,146	Accelerating Triangle Counting on GPU	2021	SIGMOD	6.4065776e-05
5,711	EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal in GPUs	2021	VLDB	5.3603407e-05
3,976	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5694893e-05
9,070	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB	4.3982218e-05
5,039	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD	5.7369993e-05
1,102	Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture	2021	VLDB	0.00014011556
5,811	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	5.3168243e-05
7,226	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	4.7910164e-05
6,983	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD	4.8682622e-05