Simulated Annealing for Edge Partitioning

Giovanni Neglia 1 Hlib Mykhailenko 2 Fabrice Huet 3
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
3 SCALE - Safe Composition of Autonomous applications with Large-SCALE Execution environment
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In distributed graph computation, graph partitioning is an important preliminary step, because the computation time can significantly depend on how the graph has been split among the different executors. In this paper, we propose a framework for distributed edge partitioning based on simulated annealing. The framework can be used to optimize a large family of partitioning metrics. We provide sufficient conditions for convergence to the optimum as well as discuss which metrics can be efficiently optimized in a distributed way. We implemented our partitioners in Apache GraphX and performed a preliminary comparison with JA-BE-JA-VC, a state-of-the-art partitioner that inspired our approach. We show that our approach can provide improvements, but further research is required to identify suitable metrics to optimize as well as to design a more efficient exploration phase for our algorithm without sacrificing convergence properties.
Type de document :
Communication dans un congrès
Computer Communications Workshops (INFOCOM WKSHPS), 2017 IEEE Conference on, May 2017, Atlanta, United States
Liste complète des métadonnées
Contributeur : Giovanni Neglia <>
Soumis le : mardi 19 décembre 2017 - 20:23:44
Dernière modification le : jeudi 6 décembre 2018 - 08:56:01


  • HAL Id : hal-01668207, version 1



Giovanni Neglia, Hlib Mykhailenko, Fabrice Huet. Simulated Annealing for Edge Partitioning. Computer Communications Workshops (INFOCOM WKSHPS), 2017 IEEE Conference on, May 2017, Atlanta, United States. 〈hal-01668207〉



Consultations de la notice