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: hc7bcbdb1ef713618
Venue: VLDB
Year: 2018
Pagerank: 8.756531e-05
Overall Rank: 2,248 | 84.89%
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,613	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010072237
3,390	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.3509644e-05
3,830	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	6.9966388e-05
4,800	Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent	2019	VLDB	6.4107404e-05
7,248	Distributed Hop-Constrained s-t Simple Path Enumeration at Billion Scale	2022	VLDB	5.5746656e-05
7,476	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	5.5161224e-05
8,064	Distributed Graph Embedding with Information-Oriented Random Walks	2023	VLDB	5.3954618e-05
8,623	D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks	2024	VLDB	5.3009314e-05
8,787	CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics	2025	VLDB	5.276816e-05
9,233	Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study	2025	VLDB	5.2056825e-05
10,561	DRPQ: Distributed Evaluation of Regular Path Queries On Streaming Graphs	2026	SIGMOD	4.9793485e-05
11,047	Chipmink: Efficient Delta Identification for Massive Object Graphs	2026	VLDB	4.9793485e-05
11,300	Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure	2025	VLDB	4.9793485e-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.0012092602
394	One Trillion Edges: Graph Processing at Facebook-Scale	2015	VLDB	0.00019191286
1,402	State Management in Apache Flink: Consistent Stateful Distributed Stream Processing	2017	VLDB	0.00010771949
1,907	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.397856e-05

Semantically Similar Papers

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