Pour mener des expérimentations sur de très grands graphes (plusieurs centaines de millions d’éléments), les chercheurs doivent se tourner vers des infrastructures distribuées. Les middlewares existants de calculs distribués sur les graphes affichent certaines limites quand à leurs modèles et leurs performances. À partir de l’étude de ces middlewares, l’ADT BigGraphs vise à développer une solution adaptée aux besoins des EPI COATI, DIANA et SCALE qui permettra de traiter les très grands graphes rencontrés dans leurs problèmes de recherche.
Dans une vaste majorité des cas, l’expérimentation d’algorithmes de graphes est effectuée à l’aide d’outils tels que JGraphT, JUNG, Grph, Boost, LEDA, etc., qui sont des bibliothèques proposant des structures de données et les algorithmes de graphes associés. La nature non-distribuée de ces bibliothèques limite à quelques millions le nombre de noeuds et d’arêtes que l’on peut considérer. Les techniques efficaces de représentation de données utilisées dans Boost et Grph repoussent cette limite de façon significative, sans pour autant changer d’ordre de grandeur la taille des graphes supportés.
L’étude de grands graphes qui sont constitués de plusieurs milliards d’éléments tels que ceux de Twitter, de Facebook, ou le graphe du Web, a motivé la mise en place de frameworks distribués dédiés. Les plus connus sont Apache Giraph, Spark/GraphX, et Google Pregel, pour lequel Google n’a pas publié le code.
L’utilisation du modèle d’exécution BSP (Bulk-Synchronous Parallel) est une charactéristique commune à toutes ces plateformes.
L’ADT a évalué deux de ces frameworks Giraph et Spark/GraphX sur des jeux de données provenant des dépots SNAP (Stanford Network Analysis Project) et GTA (Game Trace Archive). La principale limite de ces plateformes est une consommation de mémoire suffisament importante pour empécher leur utilisation sur des graphes de plus de 2 milliards d’arcs, sur le cluster NEF.
