Leopard
Authors:
Open Access
- 1 March 2016
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 9 (7) , 540-551
Abstract
This paper introduces a dynamic graph partitioning algorithm, designed for large, constantly changing graphs. We propose a partitioning framework that adjusts on the fly as the graph structure changes. We also introduce a replication algorithm that is tightly integrated with the partitioning algorithm, which further reduces the number of edges cut by the partitioning algorithm. Even though the proposed approach is handicapped by only taking into consideration local parts of the graph when reassigning vertices, extensive evaluation shows that the proposed approach maintains a quality partitioning over time, which is comparable at any point in time to performing a full partitioning from scratch using a state-the-art static graph partitioning algorithm such as METIS. Furthermore, when vertex replication is turned on, edge-cut can improve by an order of magnitude.Keywords
This publication has 10 references indexed in Scilit:
- LogGPProceedings of the VLDB Endowment, 2014
- SWORD2013
- Sharding social networks2013
- Balanced label propagation for partitioning massive graphs2013
- SchismProceedings of the VLDB Endowment, 2010
- Modularity and community structure in networksProceedings of the National Academy of Sciences of the United States of America, 2006
- Parallel static and dynamic multi‐constraint graph partitioningConcurrency and Computation: Practice and Experience, 2002
- Consistent hashing and random trees1997
- A linear-time heuristic for improving network partitions1982
- An Efficient Heuristic Procedure for Partitioning GraphsBell System Technical Journal, 1970