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: 5607
Venue: SIGMOD
Year: 2019
Pagerank: 6.7120651e-05
Overall Rank: 3,839 | 73.30%
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,690	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	8.293714e-05
3,646	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8853079e-05
5,949	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2595857e-05
6,566	Reliable Data Distillation on Graph Convolutional Network	2020	SIGMOD	5.0074274e-05
7,675	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	4.6817479e-05
7,924	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB	4.6154072e-05
8,900	CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics	2025	VLDB	4.427232e-05
9,471	Nezha: An Efficient Distributed Graph Processing System on Heterogeneous Hardware	2025	SIGMOD	4.3341665e-05
10,647	Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study	2025	VLDB	4.1945683e-05
10,763	TuskFlow: An Efficient Graph Database for Long-Running Transactions	2025	VLDB	4.1945683e-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.0019005923
209	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00034468292
281	LinkBench: a Database Benchmark Based on the Facebook Social Graph	2013	SIGMOD	0.0002906793
536	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00020722862
1,408	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012133511
1,968	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.9071968e-05
2,494	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.6508229e-05
2,595	LEOPARD: Lightweight Edge-Oriented Partitioning and Replication for Dynamic Graphs	2016	VLDB	8.4735292e-05
3,573	A Scalable Distributed Graph Partitioner	2015	VLDB	6.954939e-05
4,885	GraphJet: Real-Time Content Recommendations at Twitter	2016	VLDB	5.8534354e-05
7,687	Experimental Analysis of Distributed Graph Systems	2018	VLDB	4.677974e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,629	A Holistic View of Stream Partitioning Costs	2017	VLDB	4.9880986e-05
1,976	Towards Effective Partition Management for Large Graphs	2012	SIGMOD	9.8844201e-05
3,573	A Scalable Distributed Graph Partitioner	2015	VLDB	6.954939e-05
4,867	Application Driven Graph Partitioning	2020	SIGMOD	5.8651797e-05
1,877	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010236803
6,446	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD	5.0588808e-05
5,949	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2595857e-05
8,254	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	4.5491792e-05
1,968	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.9071968e-05
2,494	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.6508229e-05