Distributed Edge Partitioning for Trillion-edge Graphs

Summary: Distributed NE is a parallel graph partitioner for trillion-edge graphs, using a parallel expansion to grow partitions from seeds while minimizing local vertex cuts. The method enjoys a theoretical upper bound on quality and outperforms state-of-the-art distributed partitioners. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11959
Venue: VLDB
Year: 2019
Pagerank: 6.3355073e-05
Overall Rank: 4,234 | 70.55%
DOI: 10.14778/3358701.3358706

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,949	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2595857e-05
6,193	Incrementalization of Graph Partitioning Algorithms	2020	VLDB	5.1632545e-05
6,446	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD	5.0588808e-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
9,804	Capsule*: An Out-of-Core Training Mechanism for Colossal GNNs	2025	SIGMOD	4.2805224e-05
10,308	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	4.1945683e-05
10,984	Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing	2024	SIGMOD	4.1945683e-05
11,028	FSM: A Fine-grained Splitting and Merging Framework for Dual-balanced Graph Partition	2024	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
37	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.0007522744
396	One Trillion Edges: Graph Processing at Facebook-Scale	2015	VLDB	0.00024424102
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,336	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0109891e-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,895	Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner	2017	VLDB	5.8476644e-05
7,652	LA3: A Scalable Link- and Locality-Aware Linear Algebra-Based Graph Analytics System	2018	VLDB	4.6875579e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,254	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB	4.5491792e-05
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
6,146	Distributed Graph Simulation: Impossibility and Possibility	2014	VLDB	5.1857597e-05
4,867	Application Driven Graph Partitioning	2020	SIGMOD	5.8651797e-05
1,968	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB	9.9071968e-05
1,976	Towards Effective Partition Management for Large Graphs	2012	SIGMOD	9.8844201e-05
4,895	Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner	2017	VLDB	5.8476644e-05
3,573	A Scalable Distributed Graph Partitioner	2015	VLDB	6.954939e-05
4,497	Multi-Dimensional Balanced Graph Partitioning via Projected Gradient Descent	2019	VLDB	6.1387773e-05
5,949	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD	5.2595857e-05