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: 5745
Venue: SIGMOD
Year: 2019
Pagerank: 6.8629037e-05
Overall Rank: 4,157 | 71.49%
DOI: 10.1145/3299869.3319871

Incoming Non-self Citations Over Time

Authors

1. Mo Sha (National University of Singapore)
2. Yuchen Li (Singapore Management University)
3. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@inproceedings{sha_sigmod19,
        title = {{GPU-based Graph Traversal on Compressed Graphs}},
        author = {Sha, Mo and Li, Yuchen and Tan, Kian-Lee},
        series = {{SIGMOD} '19},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3299869.3319871},
        url = {https://dl.acm.org/doi/10.1145/3299869.3319871},
        year = {2019}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,607	GPU-Accelerated Subgraph Enumeration on Partitioned Graphs	2020	SIGMOD	8.3489531e-05
4,585	Data-Parallel Query Processing on Non-Uniform Data	2020	VLDB	6.6175897e-05
5,075	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	6.3740128e-05
5,480	EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal in GPUs	2021	VLDB	6.2040237e-05
7,011	GPU-Accelerated Graph Label Propagation for Real-Time Fraud Detection	2021	SIGMOD	5.7263348e-05
7,491	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	5.6059269e-05
7,573	Accelerating Exact Constrained Shortest Paths on GPUs	2021	VLDB	5.5938767e-05
10,370	Fast Optimal Group Steiner Tree Search using GPUs	2026	SIGMOD	5.093636e-05
10,450	Enabling Efficient Direct Update on Rule-Based Compressed Graph	2026	SIGMOD	5.093636e-05
10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	5.093636e-05
10,609	Efficient Temporal Edge-Core Maintenance in Streaming Graphs	2026	VLDB	5.093636e-05
11,236	Improving Graph Compression for Efficient Resource-Constrained Graph Analytics	2024	VLDB	5.093636e-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,511	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010538011
2,874	iBFS: Concurrent Breadth-First Search on GPUs	2016	SIGMOD	8.0094569e-05
3,303	A Distributed Multi-GPU System for Fast Graph Processing	2018	VLDB	7.5405596e-05
3,740	GTS: A Fast and Scalable Graph Processing Method based on Streaming Topology to GPUs	2016	SIGMOD	7.1593902e-05
4,088	Fast Sparse Matrix-Vector Multiplication on GPUs: Implications for Graph Mining	2011	VLDB	6.912485e-05
4,171	Accelerating Dynamic Graph Analytics on GPUs	2018	VLDB	6.8537202e-05
5,250	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB	6.2992176e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,686	Accelerating Triangle Counting on GPU	2021	SIGMOD
2	5,480	EMOGI: Efficient Memory-access for Out-of-memory Graph-traversal in GPUs	2021	VLDB
3	10,205	Bound-Tightened Densest Subgraph Discovery on GPU	2026	SIGMOD
4	3,503	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB
5	9,218	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB
6	1,234	Large Graph Convolutional Network Training with GPU-Oriented Data Communication Architecture	2021	VLDB
7	4,144	Tile-based Lightweight Integer Compression in GPU	2022	SIGMOD
8	7,491	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD
9	5,075	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB
10	6,408	CompressGraph: Efficient Parallel Graph Analytics with Rule-Based Compression	2023	SIGMOD