De nombreux algorithmes de calculs parallèles dans les graphes GraphX Camelia Constantin Prénom.Nom@lip6.fr basé sur la présentation de J. Gonzalez Exemple de calcul de PageRank: Les Graphes sont au centre de l'analyse de données Web Raw Wikipedia Rang de l'util. i Somme pondérée des rangs des voisins Les calculs des mises à jour des rangs peuvent être fait en parallèle On itère jusqu'à la convergence Text Table Title Body Hyperlinks PageRank Top 20 Pages Title PR Term-Doc Topic Model Word Topics Graph (LDA) Word Topic Community User Community Discussion Editor Graph Detection Community Topic Com Com Table User Topic User Disc. Les mêmes données peuvent avoir différentes “vues” table ou “vues” graphe (souvent utile de changer entre les deux vues) Systèmes orientés graphe pour chaque vue Data-parallel L'abstraction Graph-Parallel Graph-Parallel Table Modèle / Alg. Etat Graphe de propriétés Résultat Le calcul dépend uniquement des voisins L’abstraction Graph-Parallel Systèmes Graph-Parallel Un programme dé2ni par l’utilisateur s’exécute sur chaque sommet Le graphe contraint les interactions le long des arêtes: en utilisant des messages (e.g. Pregel [PODC’09, SIGMOD’10])  ou via des états partagés (e.g., GraphLab [UAI’10, VLDB’12]) oogle  Proposent des APIs spécialisées pour simplifier la programmation sur des graphes.  Nouvelles techniques de partitionnement du graphe, restriction des types d'opérations qui peuvent être utilisées.  Exploitent la structure du graphe pour obtenir des gains en performance de plusieurs ordres de magnitude comparé aux systèmes de données parallèles (Data-Parallel) plus génériques. Inconvénients: difficile d'exprimer les différentes étapes d'un pipeline de traitement sur des graphes (contruire/modifier le graphe, calculs sur plusieurs graphes) Parallélisme: lance plusieurs programmes d’arêtes simultannément L'abstraction Pregel Illustration Tro