A Scalable Distributed Graph Partitioner

Summary: Sheep is a scalable distributed graph partitioner for graphs beyond main memory, faster than METIS and Fennel. Maps graph to elimination tree via distributed map-reduce; partitioning this tree bounds internode comm. and is input-distribution agnostic. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11213
Venue: VLDB
Year: 2015
Pagerank: 7.6245396e-05
Overall Rank: 3,225 | 77.88%
DOI: 10.14778/2824032.2824052

Incoming Non-self Citations Over Time

Authors

1. Daniel Margo (Harvard University)
2. Margo Seltzer (Harvard University)

BibTeX Citation

@article{margo_vldb15,
        title = {{A Scalable Distributed Graph Partitioner}},
        author = {Margo, Daniel and Seltzer, Margo},
        journal = {PVLDB},
        series = {{VLDB} '15},
        volume = {8},
        number = {12},
        pages = {1478--1489},
        doi = {10.14778/2824032.2824052},
        url = {https://doi.org/10.14778/2824032.2824052},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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,365	Application Driven Graph Partitioning	2020	SIGMOD	6.740899e-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
9,053	CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics	2025	VLDB	5.3251649e-05
10,606	Efficient Partition-based Approaches for Diversified Top-k Subgraph Matching	2026	VLDB	5.093636e-05
11,096	A Single Machine System for Querying Big Graphs with PRAM	2025	VLDB	5.093636e-05
11,197	Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing	2024	SIGMOD	5.093636e-05
11,892	Dynamic Scaling for Parallel Graph Computations	2019	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
259	Database Cracking	2007	CIDR	0.00023119313
1,654	Navigating the Maze of Graph Analytics Frameworks using Massive Graph Datasets	2014	SIGMOD	0.00010104703

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,362	A Study of Partitioning Policies for Graph Analytics on Large-scale Distributed Platforms	2019	VLDB
2	11,238	FSM: A Fine-grained Splitting and Merging Framework for Dual-balanced Graph Partition	2024	VLDB
3	1,865	An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing	2017	VLDB
4	6,566	Play like a Vertex: A Stackelberg Game Approach for Streaming Graph Partitioning	2024	SIGMOD
5	3,362	Experimental Analysis of Streaming Algorithms for Graph Partitioning	2019	SIGMOD
6	1,803	Towards Effective Partition Management for Large Graphs	2012	SIGMOD
7	5,252	Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner	2017	VLDB
8	2,221	Streaming Graph Partitioning: An Experimental Study	2018	VLDB
9	3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB
10	5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD