This thesis falls within the field of large-scale graph analysis, with a particular focus on triangle enumeration. The search for triangles is a fundamental problem that allows us to detect all structures composed of three adjacent vertices, all interconnected by edges. These triangles play a crucial role in many graph-related applications, such as determining the clustering coefficient, assessing the age of a community in a social network, and detecting cliques.To address this study, we conducted an in-depth literature review on triangle detection in graphs. We identified two main categories of approaches: (a) those that assume the graph can fit in main memory, and (b) those that consider that the graph cannot be entirely stored in main memory. Analyzing these works, we found that the first approaches (which rely on main memory management) are effective when the graph can be fully loaded into memory, but this does not always apply to large-scale graphs that do not entirely fit into main memory. Therefore, it is essential to develop efficient algorithms for these types of graphs, which poses a major challenge for the scientific community.In the context of this thesis, we proposed a randomized algorithm (also known as adaptive algorithm) for triangle enumeration in large-scale graphs using distributed Relational Database Management System (RDBMS) technology. We chose Vertica, an RDBMS that is based on a column-oriented storage model, unlike traditional RDBMSs that use a row-oriented model. Our solution also leveraged the distributed $k-machines$ computing model. In this approach, the graph is represented as tables and processed through SQL queries executed across a set of machines while ensuring workload balancing among these nodes. To evaluate this workload balancing, we developed a tool called "PandaSQL," which allows us to analyze the graph's structure and compare our solution to existing algorithms dedicated to triangle enumeration. Furthermore, we made another contribution by studying the behavior of our randomized algorithm in a distributed environment using Python, while managing data communication between machines via the Message Passing Interface (MPI). A theoretical analysis of our algorithm, implemented in the two aforementioned environments, was also conducted.Finally, we conducted a series of experiments using large-scale graphs with different structures while varying the number of machines in the $k-machines$ model (4, 9, and 16 machines). These experiments focused on the performance of the randomized algorithm and its comparison against competing systems in different environments. Specifically, the classic solution on RDBMS, Networkx in Python, Spark Graphx, and G-thinker in a Big Data environment. The results obtained during this thesis highlight the benefits of combining RDBMS technology and parallel algorithms for efficient triangle enumeration in large-scale graphs.
Authors
- Bibliographic Reference
- Abir Farouzi. Exploration des bases de données orientées graphe : Énumération des triangles dans les graphes à grande échelle. Autre [cs.OH]. ISAE-ENSMA Ecole Nationale Supérieure de Mécanique et d'Aérotechique - Poitiers; Ecole Nationale Supérieure d'Informatique (ESI) - Alger, 2023. Français. ⟨NNT : 2023ESMA0012⟩. ⟨tel-04326161⟩
- HAL Collection
- ['Université de Poitiers', "Ecole Nationale Supérieure de Mécanique et d'Aérotechnique", 'STAR - Dépôt national des thèses électroniques', "Laboratoire d'Informatique et d'Automatique pour les Systèmes"]
- HAL Identifier
- 4326161
- Institution
- ['Université de Poitiers', 'École Nationale Supérieure de Mécanique et d’Aérotechnique [Poitiers]']
- Laboratory
- Laboratoire d'Informatique et d'Automatique pour les Systèmes
- Published in
- France
Table of Contents
- Table des matières 8
- Liste des figures 12
- Liste des tableaux 14
- Introduction générale 18
- I Concepts fondamentaux et état de l'art 32
- Notions de base 34
- Introduction 36
- Notations et fondements mathématiques 36
- Symbole 36
- Nombre et complexité 36
- Classes de complexité de problèmes 37
- Théorie de graphe 37
- Généralités sur les graphes 37
- Représentation des graphes 38
- Matrice d'incidence 39
- Propriétés du graphe 40
- Triangles 42
- Modèle distribué de stockage de données et partitionnement 43
- Systèmes distribués et bases de données distribuées 43
- Traitement distribué: avantages et défis 44
- Architectures physiques des bases de données distribuées 46
- Architectures logiques des bases de données distribuées 48
- Traitement parallèle des données 50
- Système de gestion de données et d'exploration de graphes 54
- Représentation des graphes dans les bases de données relationnelles 56
- Conclusion 58
- Travaux connexes : Techniques d'énumération et de comptage des triangles 60
- Introduction 62
- Les systèmes d'analyse de graphe 62
- Analyse des graphes dans les SGBD 63
- Traitement des données massives sur les SGBD 63
- Problématiques des graphes dans les SGBD 64
- Énumération et comptage des triangles 66
- Méthodes centralisées 66
- Méthodes parallèles et distribuées 68
- Discussion 74
- Conclusion 76
- II Contributions 78
- Algorithme adapté pour l'énumération équilibrée des triangles dans les graphes à grande échelle 80
- Introduction 82
- Définition du problème d'énumération des triangles 82
- Partitionnement des données 83
- Modèle de calcul parallèle 84
- Partitionnement randomisé des sommets 85
- Algorithme randomisé pour l'énumération des triangles 86
- Partitionnement du graphe 86
- Énumération locale des triangles 88
- Analyse du modèle de calcul et de l'algorithme randomisé 88
- Équilibrage de charge 91
- Étude de complexité 97
- Algorithme adapté 98
- Définition du problème d'énumération des triangles dans les bases de données relationnelles 98
- Modèle conceptuel de données 99
- Algorithme adapté pour l'énumération des triangles 101
- Exemple d'application 106
- Équilibrage de charge de l'algorithme adapté 108
- Complexité de l'algorithme adapté 108
- Conclusion 111
- PandaSQL : Énumération randomisée et parallèles des triangles à base des requêtes SQL 114
- Introduction 116
- Architecture physique 116
- Architecture logique 117
- PandaSQL 119
- Algorithme classique d'énumération et de comptage de triangles 119
- Algorithme randomisé d'énumération et de comptage de triangles 120
- Comparaison entre l'algorithme adapté et l'algorithme classique 120
- Démonstration de l'outil 121
- Objectifs de la Démonstration 121
- Présentation de la démonstration 121
- Conclusion 124
- Évaluation de l'algorithme adapté pour l’énumértion et du comptage des Triangles 126
- Introduction 128
- Modèle de calcul 128
- Configuration matérielle 128
- Configuration logicielle 129
- Les données utilisées dans nos expérimentations 130
- Techniques d'optimisation des requêtes 131
- Optimisation de l'espace mémoire dans les SGBD en colonnes 131
- Réplication des petites tables 135
- Replication de la table de l'auto-jointure 135
- Élimination des résultats redondants 136
- Validation des résultats de l'algorithme adapté 137
- Évaluation des optimisations 138
- Évaluation des résultats de l'algorithme adapté 141
- Efficacité de l'algorithme adapté sur l'environnement parallèle 145
- Discussion 150
- Conclusion 153
- Conclusion générale 153
- Bibliographie 160
- Résumé des symboles utilisés 176
- Plan d'exécution 178
