Towards Effective Partition Management for Large Graphs

Summary: Proposes Sedge, a self-evolving distributed graph manager with primary-plus-dynamic-secondary partitions to cut cross-machine traffic. Uses linear/sublinear workload analytics to adapt partitions in real time to locality-prone queries (BFS, random walk, SPARQL), boosting response time and throughput on commodity clusters. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4612
Venue: SIGMOD
Year: 2012
Pagerank: 9.724402e-05
Overall Rank: 1,803 | 87.64%
DOI: 10.1145/2213836.2213895

Incoming Non-self Citations Over Time

Authors

1. Shengqi Yang (University of California Santa Barbara)
2. Xifeng Yan (University of California Santa Barbara)
3. Bo Zong (University of California Santa Barbara)
4. Arijit Khan (University of California Santa Barbara)

BibTeX Citation

@inproceedings{yang_sigmod12,
        title = {{Towards Effective Partition Management for Large Graphs}},
        author = {Yang, Shengqi and Yan, Xifeng and Zong, Bo and Khan, Arijit},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213895},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213895},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
487	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00017645653
1,387	A Distributed Graph Engine for Web Scale RDF Data	2013	VLDB	0.00010949523
1,983	Pregelix: Big(ger) Graph Analytics on A Dataflow Engine	2015	VLDB	9.3544951e-05
2,363	Clay: Fine-Grained Adaptive Partitioning for General Database Schemas	2017	VLDB	8.6873235e-05
3,601	TopoX: Topology Refactorization for Efficient Graph Partitioning and Processing	2019	VLDB	7.27018e-05
4,297	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD	6.7770261e-05
4,365	Application Driven Graph Partitioning	2020	SIGMOD	6.740899e-05
4,448	LogGP: A Log-based Dynamic Graph Partitioning Method	2014	VLDB	6.6977422e-05
4,787	Systems for Big-Graphs	2014	VLDB	6.5079377e-05
5,675	MOCgraph: Scalable Distributed Graph Processing Using Message Online Computing	2015	VLDB	6.1252874e-05
7,798	A Survey and Experimental Comparison of Distributed SPARQL Engines for Very Large RDF Data	2017	VLDB	5.542286e-05
8,017	Data Management for Social Networking	2016	PODS	5.5064531e-05
8,367	T-Part: Partitioning of Transactions for Forward-Pushing in Deterministic Database Systems	2016	SIGMOD	5.4420052e-05
9,729	Scalable Graph Convolutional Network Training on Distributed-Memory Systems	2023	VLDB	5.2289669e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
126	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030779127
366	Scalable Semantic Web Data Management Using Vertical Partitioning	2007	VLDB	0.00020039981
500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017413839
741	Zephyr: Live Migration in Shared Nothing Databases for Elastic Cloud Platforms	2011	SIGMOD	0.00014442062
2,446	Querying Semantic Web Data with SPARQL	2011	PODS	8.5728114e-05
5,458	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	6.2115011e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,197	Connectivity-Oriented Property Graph Partitioning for Distributed Graph Pattern Query Processing	2024	SIGMOD
2	3,225	A Scalable Distributed Graph Partitioner	2015	VLDB
3	1,875	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB
4	3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB
5	8,651	Distributed Set Reachability	2016	SIGMOD
6	4,787	Systems for Big-Graphs	2014	VLDB
7	5,610	Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints	2021	SIGMOD
8	3,109	Managing Large Dynamic Graphs Efficiently	2012	SIGMOD
9	6,111	Scaling Queries over Big RDF Graphs with Semantic Hash Partitioning	2013	VLDB
10	500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB