Speedup Graph Processing by Graph Ordering

Summary: Graph ordering to speed up graph processing by minimizing cache misses, without altering algorithms. NP-hard; bounded-approximation algorithm and a faster variant with a data structure; experiments vs METIS on 8 graphs and 9 algorithms show cache-miss reductions. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h1f38151ed3fea01c
Venue: SIGMOD
Year: 2016
Pagerank: 0.00010641888
Overall Rank: 1,440 | 90.32%
DOI: 10.1145/2882903.2915220

Incoming Non-self Citations Over Time

Authors

1. Hao Wei (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)
3. Can Lu (Chinese University of Hong Kong)
4. Xuemin Lin (University of New South Wales)

BibTeX Citation

@inproceedings{wei_sigmod16,
        title = {{Speedup Graph Processing by Graph Ordering}},
        author = {Wei, Hao and Yu, Jeffrey Xu and Lu, Can and Lin, Xuemin},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915220},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915220},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
1,613	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010072237
2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1750421e-05
2,068	Traversing Large Graphs on GPUs with Unified Memory	2020	VLDB	9.0920811e-05
3,847	Terrace: A Hierarchical Graph Container for Skewed Dynamic Graphs	2021	SIGMOD	6.9831533e-05
3,880	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.9510799e-05
4,207	GPU-based Graph Traversal on Compressed Graphs	2019	SIGMOD	6.7343908e-05
5,172	CGgraph: An Ultra-fast Graph Processing System on Modern Commodity CPU-GPU Co-processor	2024	VLDB	6.2439642e-05
5,672	Subgraph Matching over Graph Federation	2022	VLDB	6.0433033e-05
5,734	Cache-Efficient Fork-Processing Patterns on Large Graphs	2021	SIGMOD	6.0137932e-05
6,249	Self-adaptive Graph Traversal on GPUs	2021	SIGMOD	5.8358127e-05
6,528	DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training	2025	SIGMOD	5.7553643e-05
7,587	Scalable Graph Indexing using GPUs for Approximate Nearest Neighbor Search	2026	SIGMOD	5.4891389e-05
7,747	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4601389e-05
9,166	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2148514e-05
9,233	Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study	2025	VLDB	5.2056825e-05
9,452	Sage: A System for Uncertain Network Analysis	2022	VLDB	5.1745448e-05
9,905	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1103839e-05
9,957	Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment	2025	VLDB	5.1038322e-05
10,423	Bw-Graph: An Efficient Graph Storage System Harmonizing Topology-Aware Tree with Paged CSR	2026	SIGMOD	4.9793485e-05
10,451	FaaSBoard: Efficient Graph Processing with a Disaggregated Architecture on Serverless Services	2026	SIGMOD	4.9793485e-05
10,573	GraphTwin: Cache-Centric Bit-Level Graph Representation for Fast and Exact Graph Queries	2026	SIGMOD	4.9793485e-05
10,818	ThunderGNN: Unlocking Tensor Cores for Graph Neural Networks	2026	VLDB	4.9793485e-05
11,179	Clementi: Efficient Load Balancing and Communication Overlap for Multi-FPGA Graph Processing	2025	SIGMOD	4.9793485e-05
11,292	Locality-Aware Cache Replacement Policy for Graph Traversals	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
69	Making B+-Trees Cache Conscious in Main Memory	2000	SIGMOD	0.00037950385
110	DBMSs On A Modern Processor: Where Does Time Go?	1999	VLDB	0.00032700879
207	Cache Conscious Indexing for Decision-Support in Main Memory	1999	VLDB	0.00024970987
496	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00017323054
548	Improving Index Performance through Prefetching	2001	SIGMOD	0.00016569534
959	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00012854625
1,442	The More the Merrier: Efficient Multi-Source Graph Traversal	2015	VLDB	0.00010639351
1,963	Fast Iterative Graph Computation with Block Updates	2013	VLDB	9.3063317e-05
4,027	Cache-conscious Frequent Pattern Mining on a Modern Processor	2005	VLDB	6.8456902e-05
5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.0472942e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,567	On the Complexity of Approximate Query Optimization	2002	PODS
2	1,963	Fast Iterative Graph Computation with Block Updates	2013	VLDB
3	11,540	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD
4	6,545	Ranked Enumeration of Join Queries with Projections	2022	VLDB
5	9,784	Memory Efficient Scheduling of Query Pipeline Execution	2022	CIDR
6	8,039	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
7	11,292	Locality-Aware Cache Replacement Policy for Graph Traversals	2025	VLDB
8	12,530	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
9	10,254	A Comprehensive Survey of Subgraph Matching: [Experiments & Analysis]	2026	SIGMOD
10	3,767	Multi-Query Optimization for Subgraph Isomorphism Search	2017	VLDB