Please use this identifier to cite or link to this item: https://oar.tib.eu/jspui/handle/123456789/6168
Files in This Item:
File Description SizeFormat 
Karim2020, Postprint, Compacting Frequent Star Patterns.pdf1.18 MBAdobe PDFView/Open
Title: Compacting frequent star patterns in RDF graphs
Authors: Karim, FarahVidal, Maria-EstherAuer, Sören
Publishers Version: https://doi.org/10.1007/s10844-020-00595-9
Issue Date: 2020
Published in: Journal of Intelligent Information Systems Vol. 55 (2020)
Publisher: Dordrecht : Springer Science + Business Media B.V
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
DDC: 020
License: Es gilt deutsches Urheberrecht. Das Dokument darf zum eigenen Gebrauch kostenfrei genutzt, aber nicht im Internet bereitgestellt oder an Außenstehende weitergegeben werden.
Appears in Collections:Informationswissenschaften



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.