Claudio Martella presents 'Massive-scale graph partitioning with Giraph' - PWL London

We present Spinner, a scalable and adaptive graph partitioning algorithm based on label propagation designed on top of the Pregel model. Spinner scales to massive graphs, produces partitions with locality and balance comparable to the state-of-the-art and efficiently adapts the partitioning upon changes. We describe our algorithm and its implementation in the Pregel programming model that makes it possible to partition billion-vertex graphs. We evaluate Spinner with a variety of synthetic and real graphs and show that it can compute partitions with quality comparable to the state-of-the art. In fact, by using Spinner in conjunction with the Giraph graph processing engine, we speed up different applications by a factor of 2 relative to standard hash partitioning.
The paper was presented in 2017 at the 33rd IEEE International Conference on Data Engineering (ICDE)