ExpRalytics : Expressive and Efficient Analytics for RDF Graphs

ExpRalytics : analyse expressive et efficace de graphes RDF Les données ouvertes sont souvent partagés sous la forme de graphes RDF, qui sont une incarnation du principe Linked Open Data.De telles données n'ont toutefois pas atteint leur entier potentiel d'utilisation et de partage.L'obstacle pour ce faire réside principalement au niveau de la capacité des utilisateurs à explorer, découvrir et saisir le contenu et des graphes RDF; cette tâche est complexe car les graphes sont naturellement hétérogènes, et peuvent être à la fois volumineux et complexes.Dans la première partie de cette thèse, nous proposons de nouvelles méthodes pour résumer de grands graphes de données, avec un accent particulier sur les graphes RDF.Un outil particulièrement puissant pour cette tâche est un résumé structurel d'un graphe RDF structurels; ce résumé informe les utilisateurs sur les différentes connexions entre les nœuds de graphe RDF.À cette fin, nous avons proposé une nouvelle approché pour la construction de résumés structurels de graphes RDF, à savoir RDFQuotient; les résumés qu'il construit peuvent servir de première visualisation de la structure d'un graphe RDF, tout en étant plusieurs plus compacts, souvent de plusieurs ordres de grandeur.Nous avons identifié une famille de quatre tels résumés, utilisant différentes relations d'équivalence entre les noeuds et/ou utilisant de différentes manière les types éventuellement présents dans les graphes RDF.Nous avons proposé des algorithmes capables de construire ces résumés; tous ces algorithmes sont très efficace puisque complexité de calcul dépend de façon linéaire de la taille du graphe.Nous avons aussi proposé des variantes incrémentales de nos algorithmes, qui le font évoluer de manière efficace en appliquant juste les modifications nécessaires afin de lui permettre de refléter des modifications dans le graphe d'entrée.Dans la deuxième partie de cette thèse, nous considérons le problème d'identifier automatiquement les requêtes d'agrégation les plus intéressantes qui peuvent être évaluées sur un graphe RDF, étant donnée une fonction d'intérêt spécifiée par l'utilisateur.Les requêtes d'agrégation sont couramment utilisées pour analyser des entrepôts de données relationnelles, et certaines recherches antérieures ont abordé le problème de la recommandation automatique des requêtes d'agrégation les plus intéressantes.Cependant, le problème est assez différent dans le contexte d'un entrepôt de données RDF:- Dans un graphe RDF, nous devons identifier les faits, les dimensions et les mesures qui composent une requête d'agrégation, alors que dans le cadre relationnel, ces informations sont déterminées par le schéma de l'entrepôt;- Les algorithmes OLAP capable d'évaluer efficacement, conjointement, plusieurs requêtes d'agrégation ne s'appliquent pas en présence de dimensions à valeurs multiples pour un fait donné ; de telles dimensions sont assez fréquentes dans les données RDF (où un fait peut avoir zéro, une ou plusieurs valeurs pour chaque dimension).Nous avons proposé Spade, un approche nouvelle, complète et extensible, qui permet l'identification et l'évaluation de requêtes d'agrégation intéressantes.Au coeur de l'exploration est MVDCube, notre nouvel algorithme spécialement conçu pour RDF, capable d'évaluer efficacement un treillis d'agrégats.Par ailleurs, nous avons proposé une nouvelle technique d'arrêt précoce du calcul d'un aggrégat (avec des garanties probabilistes); cette technique permet d'épargner du temps de calcul sur des agrégats qui s'avèrent sans intérêt, et réduit les coûts associé à notre travail d'exploration de requêtes d'agrégation.Des expériences utilisant à la fois des graphes réels et synthétiques démontrent sa à trouver des agrégats intéressants dans un grand espace de recherche, l'efficacité de nos algorithmes (dont la performance est meilleure que celle de PostgreSQL pour des tâches où les systèmes sont comparables), et étudié leur évaluation lorsque la taille et la complexité des données augmentent.