Experimental Analysis of Streaming Algorithms for Graph Partitioning

Summary: Systematic study of streaming graph partitioning across edge-cut and vertex-cut for analytics and online workloads. Finds that a no-partitioning baseline often wins; partitioning choice depends on graph type, workload, and application requirements. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5608
Venue: SIGMOD
Year: 2019
Pagerank: 6.7098606e-05
Overall Rank: 3,840 | 73.32%
DOI: 10.1145/3299869.3300076

Incoming Non-self Citations Over Time

Authors

1. Anil Pacaci
2. M. Tamer Özsu

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,692	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.2857267e-05
3,644	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8842065e-05
5,951	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2547916e-05
6,553	Reliable Data Distillation on Graph Convolutional Network	2020	SIGMOD	5.0100594e-05
7,674	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.677258e-05
7,924	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB	4.6109814e-05
8,900	CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics	2025	VLDB	4.4229886e-05
9,473	Nezha: An Efficient Distributed Graph Processing System on Heterogeneous Hardware	2025	SIGMOD	4.3300131e-05
10,655	Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study	2025	VLDB	4.1905499e-05
10,769	TuskFlow: An Efficient Graph Database for Long-Running Transactions	2025	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
208	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00034478612
281	LinkBench: a Database Benchmark Based on the Facebook Social Graph	2013	SIGMOD	0.00029084275
530	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020823189
1,410	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012127229
1,971	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.898018e-05
2,497	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.6427191e-05
2,596	LEOPARD: Lightweight Edge-Oriented Partitioning and Replication for Dynamic Graphs	2016	VLDB	8.4690558e-05
3,577	A Scalable Distributed Graph Partitioner	2015	VLDB	6.9485009e-05
4,889	GraphJet: Real-Time Content Recommendations at Twitter	2016	VLDB	5.8480413e-05
7,688	Experimental Analysis of Distributed Graph Systems	2018	VLDB	4.6735925e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,628	A Holistic View of Stream Partitioning Costs	2017	VLDB	4.9833118e-05
1,977	Towards Effective Partition Management for Large Graphs	2012	SIGMOD	9.8780062e-05
3,577	A Scalable Distributed Graph Partitioner	2015	VLDB	6.9485009e-05
4,868	Application Driven Graph Partitioning	2020	SIGMOD	5.8595544e-05
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
6,443	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD	5.0540558e-05
5,951	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2547916e-05
8,250	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	4.5448177e-05
1,971	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.898018e-05
2,497	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.6427191e-05