RDF-TR: Exploiting structural redundancies to boost RDF compression

Abstract

El número y el volumen de los datos semánticos han crecido de forma notable durante la última década, lo que ha convertido la compresión en una herramienta esencial para la preservación, el intercambio y la gestión de datos RDF. A diferencia de los compresores universales, las técnicas de compresión RDF son capaces de detectar y aprovechar redundancias específicas presentes en RDF. Así, estos compresores destacan por su capacidad para detectar y eliminar redundancias sintácticas y semánticas, es decir, repeticiones en el formato de serialización e información que puede inferirse de manera implícita. Sin embargo, se ha prestado poca atención a la existencia de patrones estructurales dentro de los conjuntos de datos RDF, esto es, a la redundancia estructural. En este trabajo analizamos las regularidades estructurales presentes en conjuntos de datos reales y presentamos tres fuentes de redundancia basadas en el esquema que subyace a la naturaleza flexible de RDF. A continuación, proponemos RDF-Tr (RDF Triples Reorganizer), una técnica de preprocesamiento que descubre y elimina este tipo de redundancia antes llevar a cabo el proceso de compresión, propiamente dicho. En particular, RDF-Tr agrupa sujetos que están descritos mediante los mismos predicados y recodifica localmente los objetos asociados a dichos predicados. Finalmente, integramos RDF-Tr con dos compresores RDF, HDT y k2-triples. Los experimentos realizados muestran que el uso de RDF-Tr junto con estos compresores mejora su efectividad original hasta en un factor de 2,3, superando a las técnicas más destacadas del estado del arte.

=====

The number and volume of semantic data have grown impressively over the last decade, promoting compression as an essential tool for RDF preservation, sharing and management. In contrast to universal compressors, RDF compression techniques are able to detect and exploit specific forms of redundancy in RDF data. Thus, state-of-the-art RDF compressors excel at exploiting syntactic and semantic redundancies, i.e., repetitions in the serialization format and information that can be inferred implicitly. However, little attention has been paid to the existence of structural patterns within the RDF dataset; i.e. structural redundancy. In this paper, we analyze structural regularities in real-world datasets, and show three schema-based sources of redundancies that underpin the schema-relaxed nature of RDF. Then, we propose RDF-Tr (RDF Triples Reorganizer), a preprocessing technique that discovers and removes this kind of redundancy before the RDF dataset is effectively compressed. In particular, RDF-Tr groups subjects that are described by the same predicates, and locally re-codes the objects related to these predicates. Finally, we integrate RDF-Tr with two RDF compressors, HDT and k2-triples. Our experiments show that using RDF-Tr with these compressors improves by up to 2.3 times their original effectiveness, outperforming the most prominent state-of-the-art techniques.