Balanced graph partitioning is a fundamental problem that is receiving growing attention with the emergence of distributed graph-computing (DGC) frameworks. In these frameworks, the partitioning strategy plays an important role since it drives the communication cost and the workload balance among computing nodes, thereby affecting system performance. However, existing solutions only partially exploit a key characteristic of natural graphs commonly found in the real-world: their highly skewed power-law degree distributions. In this paper, we propose High-Degree (are) Replicated First (HDRF), a novel streaming vertex-cut graph partitioning algorithm that effectively exploits skewed degree distributions by explicitly taking into account vertex degree in the placement decision. We analytically and experimentally evaluate HDRF on both synthetic and real-world graphs and show that it outperforms all existing algorithms in partitioning quality.
2015, Proceedings of the 24th ACM International on Conference on Information and Knowledge Management, Pages 243-252
HDRF: Stream-based partitioning for power-law graphs (04b Atto di convegno in volume)
Petroni Fabio, Querzoni Leonardo, Daudjee Khuzaima, Kamali Shahin, Iacoboni Giorgio
Gruppo di ricerca: Distributed Systems