Enumération Randomisée des Triangles dans des Graphes à Grande Echelle à base de SQL
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.