Compact Summaries of Rich Heterogeneous Graphs

Šejla Čebirić 1, 2, 3 François Goasdoué 4, 1 Pawel Guzewicz 1, 2, 3 Ioana Manolescu 1, 2, 3
1 CEDAR - Rich Data Analytics at Cloud Scale
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
4 SHAMAN - Symbolic and Human-centric view of dAta MANagement
IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Large data graphs with complex and heterogeneous structure, possibly featuring typed data and an ontol- ogy encoding the application-domain semantics, are widely used nowadays. The literature provides many solutions for building succinct representations of graphs, called summaries, in particular based on graph quotients through an equivalence relation between graph nodes. We consider efficient and compact summarization of rich heterogeneous graphs, in particular RDF ones, which may feature data edges, typed nodes, and an ontology. First, we devise new graph node equivalence relations, particularly tolerant of structural heterogeneity; they lead to compact yet informative quotient summaries. Second, we show how to extend any node equivalence relation (including, but not limited to ours) to types and ontologies, and provide the first in-depth study of the interplay between quotient sum- marization and RDF graph saturation, which defines the semantics of an RDF graph, in particular in the presence of an ontology. We establish a sufficient condition on a node equivalence relation, which if met allows an efficient method, called shortcut, for summarizing RDF graphs. We describe novel, efficient, incremental algorithms for summarizing graphs with our node equivalence relations, and experiments validating their performance.
Document type :
Reports
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01325900
Contributor : Ioana Manolescu <>
Submitted on : Wednesday, July 4, 2018 - 10:53:07 AM
Last modification on : Thursday, June 13, 2019 - 11:34:02 AM
Long-term archiving on : Monday, October 1, 2018 - 11:52:24 AM

File

RR-04072018.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01325900, version 6

Citation

Šejla Čebirić, François Goasdoué, Pawel Guzewicz, Ioana Manolescu. Compact Summaries of Rich Heterogeneous Graphs. [Research Report] RR-8920, INRIA Saclay; Université Rennes 1. 2018, pp.1-40. ⟨hal-01325900v6⟩

Share

Metrics

Record views

498

Files downloads

591