Soutenance mémoire
Échantillonnage et interrogation de flux de graphes RDF
Nous étendons le langage de requête et le système C-SPARQL pour l’échantillonnage à la volée de flux de données RDF. Dans le but de préserver la sémantique des données dans l’échantillon, nous adoptons une approche orientée graphe à la place des successions de triplets RDF utilisés par C-SPARQL. L’objectif de cette extension est d’une part l’ajout d’opérateurs d’échantillonnage dans la syntaxe de requête de C-SPARQL et d’autre part l’extension de ses modules continu et statique avec des algorithmes d’échantillonnage correspondants à ces opérateurs. En guise de validation de cette implémentation, nous choisissons les algorithmes d’échantillonnage Uniform, Reservoir et Chain correspondant respectivement aux opérateurs de requêtes UNIFORM, RESERVOIR et CHAIN.
Cette première contribution constitue un cas particulier de la réduction de la charge par un système RSP via de nouveaux opérateurs de requêtes, un module permettant l’implémentation de n’importe quelle technique de délestage en continu d’une partie des données en entrée tout en maintenant une cohérence entre les données conservées. Cependant, avec l’échantillonnage orienté graphe, notre module d’extension arrive à réduire la charge de traitement mais ne permet pas d’extraire les informations les plus pertinentes du graphe. Nous avons, dans notre deuxième contribution, approfondi ce module (d’abord au sein d’un système RSP et plus tard dans un système que nous avons implémenté de bout en bout) avec un nouvel algorithme de résumé de flux de graphes RDF qui accorde plus d’importance aux nœuds et liens les plus « pertinents » du graphe RDF.
Résumé orienté graphe de flux de graphes RDF
Dans cette deuxième contribution, nous proposons une approche de résumé de flux de graphes RDF en étendant la mesure de centralité appelée centralité de proximité (betweeness centrality) issue de l’analyse des réseaux sociaux. L’objectif de cette contribution est de réduire la charge de traitement par l’exploitation de la richesse des graphes RDF afin de générer des résumés assez représentatifs des données. Avec l’extension de la mesure de centralité de proximité, nous concevons une analyse à la volée de graphes RDF en entrée afin d’en extraire, selon un pourcentage de résumé donné, les nœuds ainsi que les liens les plus informatifs avant de se délaisser du reste du graphe. De plus, cette approche de génération continue de résumés de graphes RDF est orientée besoin de l’utilisateur. En effet, elle combine les besoins exprimés par les utilisateurs (à travers les requêtes SPARQL continues) aux algorithmes étendus de mesure de centralité des éléments du graphe RDF.
Interrogation de flux de données RDF compressées au format RDSZ
Afin de pousser la qualité de la réduction de la charge en matière d’espace de stockage, nous adoptons dans cette troisième contribution un format compressé des flux de données RDF et proposons une approche de traitement de requêtes SPARQL continues sur données RDF compressées au format RDSZ[40] (un algorithme de compression de flux de données RDF). Pour les systèmes RSP ayant adopté ce format de compression de données, nous éliminons ainsi les phases assez complexes et coûteuses (en termes de ressource mémoire et de temps de calcul) de décompression suivi de traitement des requêtes sur données RDF. Nous exécutons directement les requêtes SPARQL sur un ensemble de données de taille beaucoup moins importante dans le but de gagner en performance en termes de temps de calcul de requêtes et d’espace de stockage. Une fois la charge de traitement réduite, les systèmes de traitement de flux de données RDF nécessitent une montée en charge et des temps de latences ultra faibles pour faire face à la fois aux flux massifs de données RDF statiques et dynamiques. Ainsi, notre quatrième contribution initie nos approches de gestion continue et distribuée de flux de graphes RDF autour de notre première architecture distribuée DRSS (Distributed RDF SPARQL Streaming).
Système de traitement distribué de flux de graphes RDF (DRSS)
DRSS constitue à la fois notre premier langage et moteur de traitement de flux de graphes RDF implémenté de bout en bout au dessus de la plateforme de traitement temps réel Apache Storm. Nous avons d’abord proposé DRSS comme système socle avec un nouveau langage de requête continue et une nouvelle approche de distribution des données et du traitement. Il s’agit d’abord de définir un langage de requête avec trois nouvelles variantes de fenêtrage (intégrant le maximum de contexte des flux de données) mais aussi une architecture distribuée composée d’une partie statique et d’une partie temps réel. La partie statique nous permet d’analyser les requêtes utilisateurs, regrouper celles qui partagent des sousstructures communes avant de les partitionner. L’un des avantages du partitionnement de la requête avant l’arrivée des flux RDF est d’adopter le partitionnement des graphes RDF statiques et dynamiques aux partitions de requêtes obtenues dans le but de distribuer et de dupliquer les partitions de graphes à destination de nœuds de traitement précis. Ce déploiement assez stratégique nous permet de réduire considérablement les communications entre nœuds de traitement pour une exécution locale et parallèle des partitions de requêtes SPARQL continues. Nous adoptons dans DRSS une approche de partitionnement de graphes de requête SPARQL centrée sur les nœuds de jointure autour desquels nous définissons les notions de pattern complet (full pattern) et pattern léger (light pattern). Les patterns complets constituent les centres des partitions de requête et sont, si besoin, dupliqués entre partitions nécessitant d’échanger des données pour compléter l’exécution d’une requête. Les patterns légers quant à eux, restent figés à leurs partitions et ne sont jamais dupliqués. Cette procédure nous permet de traiter toutes les partitions d’une requête parallèlement en échangeant peu ou pas de données entre les nœuds de traitement. Les systèmes de traitement distribué de flux de données RDF existants sont moins performants en cas de croisement des flux RDF avec de larges volumes de données RDF statiques (stockées) dans des dépôts (bases de données orientées triplets) locaux ou distants. DRSS a apporté une première solution permettant de gérer l’importation, le croisement avec des données dynamiques et le rafraichissement des données statiques sans blocage dans le traitement. Cependant, dans la dernière contribution de cette thèse, nous avons approfondi l’approche de DRSS en nous intéressant au problème de jointure entre graphes RDF statiques et dynamiques.
Approche de jointure distribuée entre graphes RDF statiques et dynamique (JSS-RDF)
Notre dernière contribution, ajoute entre autres à la solution DRSS un module de gestion des données statiques et un module de jointure rapide entre données statiques et dynamiques. Nous proposons principalement dans JSS-RDF une approche de jointures continues et distribuées entre des données statiques et dynamiques en utilisant les filtres de Bloom. De cette approche de jointure, découle une grande réduction des résultats intermédiaires durant le processus de jointure et un pré calcul des partitions de requête en fonction des variables de requête SPARQL sélectionnées entre les deux natures (statiques et dynamiques) des données RDF. Nous réalisons un appariement en mémoire (si nécessaire) de chaque triplet de graphe entrant (côté flux) avec un triplet de graphe stocké. JSS-RDF assure l’opération de jointure continue sans interrogation de dépôts locaux ou distants durant l’exécution de la requête ainsi qu’un rafraichissement périodique (jour, semaine, mois, etc.) des données statiques. JSS-RDF est une solution complète et performante de gestion continue et distribuée de flux de graphes RDF statiques et dynamiques.
|
Table des matières
1 Introduction
1.1 Motivations
1.2 Problématique et défis
1.2.1 Volume de données
1.2.2 Structure de données
1.2.3 Croisement de données statiques et dynamiques
1.2.4 Partitionnement de requête
1.3 Contributions
1.3.1 Échantillonnage et interrogation de flux de graphes RDF
1.3.2 Résumé orienté graphe de flux de graphes RDF
1.3.3 Interrogation de flux de données RDF compressées au format RDSZ
1.3.4 Système de traitement distribué de flux de graphes RDF (DRSS)
1.3.5 Approche de jointure distribuée entre graphes RDF statiques et dynamique (JSS-RDF)
1.4 Jeu de données
1.5 Organisation du manuscrit
2 État de l’art sur les systèmes et approches non distribués pour la gestion des flux de données RDF
2.1 Introduction
2.2 Concepts et définitions
2.2.1 Le web sémantique
2.2.1.1 URL/URI/IRI
2.2.1.2 Le modèle RDF (Resource Description Framework)
2.2.1.3 RDFS (RDF Schema)
2.2.2 Interrogation de données RDF (langage de requête SPARQL)
2.2.2.1 Syntaxe
2.2.2.2 Sémantique
2.2.3 Flux de données
2.2.3.1 Définition et domaines d’application des flux de données
2.2.3.2 Domaine d’application des flux de données
2.2.3.3 Systèmes de Gestion des flux de données (SGFD)
2.2.3.4 Notion de Fenêtre
2.2.3.5 Les flux de données sémantiques
2.3 Systèmes RSP centralisés
2.3.1 Streaming SPARQL
2.3.2 C-SPARQL
2.3.2.1 Langage de requête C-SPARQL
2.3.2.2 Système C-SPARQL
2.3.3 CQELS
2.3.3.1 Langage CQELS
2.3.3.2 Système CQELS
2.3.4 SPARQLst r eam
2.3.4.1 Langage SPARQLst r eam
2.3.4.2 Système SPARQLst r eam : Morph−streams
2.3.5 Event Processing SPARQL (EP-SPARQL)
2.3.5.1 Langage EP-SPARQL
2.3.5.2 Système EP-SPARQL : ETALIS
2.3.6 Sparkwave
2.3.6.1 Système Sparkwave
2.3.7 Autres systèmes
2.3.8 Bilan
2.4 Conclusion
3 État de l’art sur les résumés de flux de données
3.1 Introduction
3.2 Définition d’un résumé de flux de données
3.3 Conception de résumés de flux de données
3.3.1 Conception simple d’un résumé de flux de données
3.3.1.1 Échantillonnage
3.3.1.2 Agrégats
3.3.1.3 Histogrammes
3.3.1.4 Sketchs
3.3.2 Conception complexe d’un résumé de flux de données
3.3.2.1 Organisation temporelle complexe
3.3.2.2 Algorithmes de résumés généralistes
3.3.3 Bilan
3.4 Conception de résumés de flux de graphes RDF
3.4.1 Agrégation et regroupement
3.4.1.1 Définition de quelques notions essentielles
3.4.1.2 Approche de résumé utilisée
3.4.2 Extraction structurelle
3.4.3 Bilan
3.5 Conclusion
4 Conclusion
Télécharger le rapport complet
