Query-Oriented Summarization of RDF Graphs
Résumé
RDF is the data model of choice for Semantic Web applications. RDF graphs are often large and heterogeneous, thus users may have a hard time getting familiar with the structure and semantics of a graph, or determining whether a graph is useful for a certain application.
We consider answering such questions by inspecting a graph summary, a compact structure conveying as much information as possible about the input graph. A summary is representative of a graph if it represents both its explicit and implicit triples, the latter resulting from RDF Schema constraints. To ensure represen- tativeness, we define a novel RDF-specific summarization framework based on RDF node equivalence and graph quotients; our framework can be instantiated with many different RDF node equivalence relations. We show that our summaries are representative, and establish a sufficient condition on the RDF equivalence relation to ensure that a graph can be efficiently summarized, without materializing its implicit triples. We demonstrate that the state-of-the art bisimulation equivalence relations between graph nodes fit into our framework. Further, we instantiate the framework through four novel summaries, based on the new concept of property cliques, specifically tailored to cope with highly heterogeneous RDF graphs; we show that they are orders of magnitude more compact than bisimulation summaries. Finally, we show that the bisimulation and two of our clique summaries can be built efficiently so that they represent the explicit and implicit data of the input graph without saturating the graph. The performance benefits of our efficient summarization method is confirmed through a set of experiments.
RDF est le modèle de données du W3C, fondé sur les graphes, pour les applications du Web Séman- tique. Les graphes RDF sont souvent larges et hétérogènes, ce qui complique la tâche des utilisateurs qui tentent de se familiariser avec leurs structure et sémantique, ou de déterminer si un graphe est utile pour une application donnée.
Nous étudions comment répondre à ces besoins en inspectant un résumé de graphe, une structure com- pacte portant autant d’information que possible à propos du graphe d’entrée. Un résumé est représen- tatif d’un graphe s’il représente à la fois ses triplets explicites et implicites, ces derniers découlant de contraintes de RDF Schema. Pour garantir la représentativité, nous définissons un nouvau cadre de ré- sumé de graphe spécifique à RDF, fondé sur une relation d’équivalence de noeuds RDF et le quotient de graphe ; notre cadre peut être instancié avec une multitude de relations d’équivalence de noeuds RDF. Nous montrons que nos résumés sont représentatifs et nous établissons une condition suffisante sur la relation d’équivalence de noeuds RDF pour garantir qu’un graphe peut être efficacement résumé, sans matérialiser ses triplets implicites. Nous démontrons que les relations d’équivalence entre noeuds de l’état de l’art, fondées sur la bissimulation de graphes, satisfont notre condition. De plus, nous instancions notre cadre avec quatre nouvelles relations d’équivalence de noeuds RDF, donnant lieu à quatre nouveaux types de résumés, fondées sur les cliques de propriétés, spécialement adaptées à la grande hétérogénéité des graphes RDF ; nous montrons que ces types de résumé sont plusieurs ordres de magnitude plus compacts que les résumés à base de bissimulation. Enfin, nous montrons que les résumés à base de bissimulation et deux de nos résumés à base de cliques peuvent être construits efficacement, de sorte qu’ils représentent les triplets explicites et implicites du graphe d’entrée sans avoir à le saturer. Les bénéfices de performance de notre méthode de résumé sont confirmés au travers d’un ensemble d’expériences.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...