Simulated Annealing for Edge Partitioning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2017

Simulated Annealing for Edge Partitioning

Hlib Mykhailenko
  • Fonction : Auteur
  • PersonId : 779720
  • IdRef : 202659275
Giovanni Neglia
Fabrice Huet

Résumé

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.
Fichier principal
Vignette du fichier
RR-9019.pdf (822.48 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01446677 , version 1 (26-01-2017)
hal-01446677 , version 2 (01-02-2017)

Identifiants

  • HAL Id : hal-01446677 , version 2

Citer

Hlib Mykhailenko, Giovanni Neglia, Fabrice Huet. Simulated Annealing for Edge Partitioning. [Research Report] RR-9019, Inria Sophia Antipolis. 2017. ⟨hal-01446677v2⟩
238 Consultations
600 Téléchargements

Partager

Gmail Facebook X LinkedIn More