Streaming Graph Partitioning: An Experimental Study

Summary: Taxonomy and experiments on online streaming graph partitioning using a unified Flink runtime. Findings: low-cut partitioners excel for communication-heavy workloads but incur higher costs; model-agnostic approaches favor locality with lower costs in data-parallel graphs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11832
Venue: VLDB
Year: 2018
Pagerank: 8.9260308e-05
Overall Rank: 2,221 | 84.77%
DOI: 10.14778/3236187.3236208

Incoming Non-self Citations Over Time

Authors

1. Zainab Abbas (KTH Royal Institute of Technology)
2. Vasiliki Kalavri (ETH Zurich)
3. Paris Carbone (KTH Royal Institute of Technology)
4. Vladimir Vlassov (KTH Royal Institute of Technology)

BibTeX Citation

@article{abbas_vldb18,
        title = {{Streaming Graph Partitioning: An Experimental Study}},
        author = {Abbas, Zainab and Kalavri, Vasiliki and Carbone, Paris and Vlassov, Vladimir},
        journal = {PVLDB},
        series = {{VLDB} '18},
        volume = {11},
        number = {11},
        pages = {1590--1603},
        doi = {10.14778/3236187.3236208},
        url = {https://doi.org/10.14778/3236187.3236208},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,760	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	9.8157819e-05
3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.4833791e-05
3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	7.15217e-05
4,697	Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent	2019	VLDB	6.5575113e-05
7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	5.6338252e-05
7,418	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	5.6236086e-05
7,900	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB	5.5193e-05
8,454	D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks	2024	VLDB	5.4226e-05
9,053	CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics	2025	VLDB	5.3251649e-05
10,361	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	5.093636e-05
10,600	Chipmink: Efficient Delta Identification for Massive Object Graphs	2026	VLDB	5.093636e-05
10,899	Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study	2025	VLDB	5.093636e-05
10,903	Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
389	One Trillion Edges: Graph Processing at Facebook-Scale	2015	VLDB	0.00019386526
1,422	State Management in Apache Flink: Consistent Stateful Distributed Stream Processing	2017	VLDB	0.00010823039
1,865	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.5915721e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,246	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB
2	11,238	FSM: A Fine-grained Splitting and Merging Framework for Dual-balanced Graph Partition	2024	VLDB
3	3,225	A Scalable Distributed Graph Partitioner	2015	VLDB
4	4,365	Application Driven Graph Partitioning	2020	SIGMOD
5	6,410	A Holistic View of Stream Partitioning Costs	2017	VLDB
6	5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD
7	6,566	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD
8	7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB
9	1,865	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB
10	3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD