CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics

Summary: CUTTANA is a streaming graph partitioner that buffers vertices and uses scalable coarsening/refinement to defer assignments and approximate a global view, reducing edge-cut and communication volume. Parallel CUTTANA matches streaming latency while cutting analytics runtimes up to 59% and improving graph-DB throughput up to 23% versus prior streaming partitioners. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13995
Venue: VLDB
Year: 2025
Pagerank: 5.3251649e-05
Overall Rank: 9,053 | 37.89%
DOI: 10.14778/3696435.3696437

Incoming Non-self Citations Over Time

Authors

1. Milad Rezaei Hajidehi (University of British Columbia)
2. Sraavan Sridhar (University of British Columbia)
3. Margo Seltzer (University of British Columbia)

BibTeX Citation

@article{hajidehi_vldb25,
        title = {{CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics}},
        author = {Hajidehi, Milad Rezaei and Sridhar, Sraavan and Seltzer, Margo},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {1},
        pages = {14--27},
        doi = {10.14778/3696435.3696437},
        url = {https://doi.org/10.14778/3696435.3696437},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,903	Triparts: Scalable Streaming Graph Partitioning to Enhance Community Structure	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
426	The LDBC Social Network Benchmark: Interactive Workload	2015	SIGMOD	0.00018692185
2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB	8.9260308e-05
2,332	LEOPARD: Lightweight Edge-Oriented Partitioning and Replication for Dynamic Graphs	2016	VLDB	8.7410236e-05
2,915	GraphScope: A Unified Engine For Big Graph Processing	2021	VLDB	7.9666977e-05
3,225	A Scalable Distributed Graph Partitioner	2015	VLDB	7.6245396e-05
3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD	7.4833791e-05
3,601	TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing	2019	VLDB	7.27018e-05
3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	7.15217e-05
3,924	A1: A Distributed In-Memory Graph Database	2020	SIGMOD	7.015626e-05
4,544	ByteGraph: A High-Performance Distributed Graph Database in ByteDance	2022	VLDB	6.6382612e-05
5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	6.1508076e-05
5,811	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	6.0782651e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,365	Application Driven Graph Partitioning	2020	SIGMOD
2	4,323	TurboGraph++: A Scalable and Fast Graph Analytics System	2018	SIGMOD
3	1,803	Towards Effective Partition Management for Large Graphs	2012	SIGMOD
4	6,566	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD
5	1,865	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB
6	5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD
7	3,225	A Scalable Distributed Graph Partitioner	2015	VLDB
8	7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB
9	3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD
10	2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB