RNTI

MODULAD
Enumération Randomisée des Triangles dans des Graphes à Grande Echelle à base de SQL
In EDA 2020, vol. RNTI-B-16, pp.33-46
Résumé
Chercher tous les triangles dans un graphe donné est un problème théorique classique avec un nombre important d'applications pratiques. Plusieurs algorithmes d'énumération de triangles dans des graphes à grande échelle ont été proposés et implémentés dans des environnements centralisés/distribués avec des langages comme C/Python. Dans le contexte des bases de données, il existe une grande masse de données qui peuvent être modélisées et analysées sous forme de graphes. Offrir des solutions d'énumération de triangles avec des requêtes SQL pour ces graphes représente un enjeu important pour la communauté. Dans cet article, nous proposons un algorithme distribué randomisé implémenté à l'aide de requêtes SQL pour l'énumération des triangles dans des graphes à grande échelle. Cet algorithme assure l'équilibrage de charge entre les processeurs grâce à sa stratégie de partitionnement visant à éliminer les échanges coûteux de données entre les hôtes lors de l'énumération de triangles. Nos expériences ont montré le passage à l'échelle de notre approche déployée sur un cluster de 8 hôtes et hébergeant le SGBD Vertica.