Distributed edge partitioning

Hlib Mykhailenko 1
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Pour traiter un graphe de manière répartie, le partitionnement est une étape préliminaire importante car elle influence de manière significative le temps final d’exécutions. Dans cette thèse nous étudions le problème du partitionnement réparti de graphe. Des travaux récents ont montré qu’une approche basée sur le partitionnement des sommets plutôt que des arêtes offre de meilleures performances pour les graphes de type power-laws qui sont courant dans les données réelles. Dans un premier temps nous avons étudié les différentes métriques utilisées pour évaluer la qualité d’un partitionnement. Ensuite nous avons analysé et comparé plusieurs logiciels d’analyse de grands graphes (Hadoop, Giraph, Giraph++, Distributed GrahpLab et PowerGraph), les comparant `a une solution très populaire actuellement, Spark et son API de traitement de graphe appelée GraphX. Nous présentons les algorithmes de partitionnement les plus récents et introduisons une classification. En étudiant les différentes publications, nous arrivons à la conclusion qu’il n’est pas possible de comparer la performance relative de tous ces algorithmes. Nous avons donc décidé de les implémenter afin de les comparer expérimentalement. Les résultats obtenus montrent qu’un partitionneur de type Hybrid-Cut offre les meilleures performances. Dans un deuxième temps, nous étudions comment il est possible de prédire la qualité d’un partitionnement avant d’effectivement traiter le graphe. Pour cela, nous avons effectué de nombreuses expérimentations avec GraphX et effectué une analyse statistique précise des résultats en utilisation un modèle de régression linéaire. Nos expérimentations montrent que les métriques de communication sont de bons indicateurs de la performance. Enfin, nous proposons un environnement de partitionnement réparti basé sur du recuit simulé qui peut être utilisé pour optimiser une large partie des métriques de partitionnement. Nous fournissons des conditions suffisantes pour assurer la convergence vers l’optimum et discutons des métriques pouvant être effectivement optimisées de manière répartie. Nous avons implémenté cet algorithme dans GraphX et comparé ses performances avec JA-BE-JA-VC. Nous montrons que notre stratégie amène a` des améliorations significatives.
Type de document :
Thèse
Other [cs.OH]. Université Côte d'Azur, 2017. English. 〈NNT : 2017AZUR4042〉
Liste complète des métadonnées

Littérature citée [44 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01551107
Contributeur : Abes Star <>
Soumis le : mardi 3 octobre 2017 - 15:53:07
Dernière modification le : lundi 30 avril 2018 - 14:30:10

Fichier

2017AZUR4042.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01551107, version 2

Citation

Hlib Mykhailenko. Distributed edge partitioning. Other [cs.OH]. Université Côte d'Azur, 2017. English. 〈NNT : 2017AZUR4042〉. 〈tel-01551107v2〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

174