Titel:
Parallel and distributed algorithms for pattern matching in big graphs ; Algorithmes parallèles et distribués pour le matching dans les grands graphes
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
L’appariement des sous-graphes (ASG) est un problème classique, souvent modélisé à l’aide de l’isomorphisme de sous-graphes. Il est utilisé dans différents domaines d’application tels que la reconnaissance de motifs et la détection de communautés dans les réseaux sociaux. Néanmoins, en plus du fait qu’il soit NP-Complet, l’isomorphisme de sous-graphes s’avère très strict pour l’ASG dans le contexte actuel des grands graphes. Par conséquence, de nouveaux modèles d’ASG relaxé ont apparu comme la Graph Simulation, permettant d’avoir des résultats intéressants dans un temps polynomial. De plus, les graphes massifs qui sont issus des réseaux sociaux nécessitent un stockage et un traitement distribués sur plusieurs machines, d’où la nécessité de revisiter les algorithmes d’ASG relaxé en adoptant de nouveaux paradigmes, dédiés au traitement des grands graphes, notamment le Think-Like-A-Vertex et ses variantes. Dans cette thèse, nous étudions l’intérêt des systèmes et paradigmes distribués de traitement des grands graphes dans l’évaluation des requêtes d’ASG. L’objectif est d'identifier les modèles de programmation qui sont les mieux adaptés pour ce problème. Par ailleurs, nous visons à proposer de nouveaux algorithmes d’ASG qui sont parallèles, distribués et offrant une scalabilité linéaire. Nos contributions se résument en quatre points : (1) nous proposons une nouvelle classification des approches distribuées d’ASG, en nous basant sur plusieurs critères tels que le modèle d’ASG et le paradigme de programmation, (2) nous introduisons le nouveau modèle d’ASG relaxé BDSim qui permet de mieux capturer les similarités entre les graphes, tout en ayant une complexité cubique. En plus, nous proposons des algorithmes distribués centré sommet pour l’évaluation de BDSim sur des grands graphes, (3) nous développons le premier algorithme scalable et complètement distribué pour évaluer Strong Simulation, un modèle d’ASG relaxé offrant un compromis entre la flexibilité et la faisabilité, (4) enfin, nous proposons la première ...