Compacting frequent star patterns in RDF graphs
- PDF / 3,352,635 Bytes
- 25 Pages / 439.642 x 666.49 pts Page_size
- 4 Downloads / 213 Views
Compacting frequent star patterns in RDF graphs ¨ Farah Karim1,2 · Maria-Esther Vidal1 · Soren Auer1 Received: 16 July 2019 / Revised: 10 November 2019 / Accepted: 4 February 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Knowledge graphs have become a popular formalism for representing entities and their properties using a graph data model, e.g., the Resource Description Framework (RDF). An RDF graph comprises entities of the same type connected to objects or other entities using labeled edges annotated with properties. RDF graphs usually contain entities that share the same objects in a certain group of properties, i.e., they match star patterns composed of these properties and objects. In case the number of these entities or properties in these star patterns is large, the size of the RDF graph and query processing are negatively impacted; we refer these star patterns as frequent star patterns. We address the problem of identifying frequent star patterns in RDF graphs and devise the concept of factorized RDF graphs, which denote compact representations of RDF graphs where the number of frequent star patterns is minimized. We also develop computational methods to identify frequent star patterns and generate a factorized RDF graph, where compact RDF molecules replace frequent star patterns. A compact RDF molecule of a frequent star pattern denotes an RDF subgraph that instantiates the corresponding star pattern. Instead of having all the entities matching the original frequent star pattern, a surrogate entity is added and related to the properties of the frequent star pattern; it is linked to the entities that originally match the frequent star pattern. Since the edges between the entities and the objects in the frequent star pattern are replaced by edges between these entities and the surrogate entity of the compact RDF molecule, the size of the RDF graph is reduced. We evaluate the performance of our factorization techniques on several RDF graph benchmarks and compare with a baseline built on top gSpan, a state-of-the-art algorithm to detect frequent patterns. The outcomes evidence the efficiency of proposed approach and show that our techniques are able to reduce execution time of the baseline approach in at least three orders of magnitude. Additionally, RDF graph size can be reduced by up to 66.56% while data represented in the original RDF graph is preserved. Keywords Semantic Web · RDF compaction · Linked data · Knowledge graph
Farah Karim
[email protected] 1
Leibniz University of Hannover, Welfengarten 1B, 30167 Hannover, Germany
2
Mirpur University of Science and Technology (MUST), Mirpur, 10250 (AJK), Pakistan
Journal of Intelligent Information Systems
1 Introduction Knowledge graphs have gained momentum as flexible and expressive structures for representing not only data and knowledge but also actionable insights (Vidal et al. 2019); they provide the basis for effective and intelligent applications. Currently, knowledge graphs are utilized in diverse domains e.g
Data Loading...
