Paper Info
Title
Large-scale bisimulation of RDF graphs
Abstract
RDF datasets with billions of triples are no longer unusual and continue to grow constantly (e.g. LOD cloud) driven by the inherent flexibility of RDF that allows to represent very diverse datasets, ranging from highly structured to unstructured data. Because of their size, understanding and processing RDF graphs is often a difficult task and methods to reduce the size while keeping as much of its structural information become attractive. In this paper we study bisimulation as a means to reduce the size of RDF graphs according to structural equivalence. We study two bisimulation algorithms, one for sequential execution using SQL and one for distributed execution using MapReduce. We demonstrate that the MapReduce-based implementation scales linearly with the number of the RDF triples, allowing to compute the bisimulation of very large RDF graphs within a time which is by far not possible for the sequential version. Experiments based on synthetic benchmark data and real data (DBPedia) exhibit a reduction of more than 90% of the size of the RDF graph in terms of the number of nodes to the number of blocks in the resulting bisimulation partition.
Year
DOI
Venue
2013
10.1145/2484712.2484713
SWIM@SIGMOD Conference
Keywords
Field
DocType
synthetic benchmark data,bisimulation partition,large-scale bisimulation,rdf triple,rdf datasets,diverse datasets,unstructured data,bisimulation algorithm,rdf graph,large rdf graph,semantic web,bisimulation,rdf
SQL,Data mining,Computer science,Cwm,SPARQL,Unstructured data,Theoretical computer science,Bisimulation,RDF Schema,RDF/XML,RDF,Database
Conference
Citations 
PageRank 
References 
2
0.39
19
Authors
4
Name
Order
Citations
PageRank
Alexander Schätzle11579.59
Antony Neu2211.10
Georg Lausen33687526.29
Martin Przyjaciel-Zablocki41619.98