Compressed and queryable self-indexes for RDF archives

Abstract

La compresión y la consulta de RDF son temas consolidados en la Web de los Datos, donde existe una amplia variedad de soluciones que permiten almacenar y consultar de forma eficiente colecciones de datos estáticos. Sin embargo, los datos RDF evolucionan a lo largo del tiempo y esto hace necesario conservar diferentes versiones de los mismos, lo que se conoce como un archivo RDF. En el caso de archivos de gran tamaño, las técnicas básicas utilizadas para su almacenamiento presentan importantes problemas de escalabilidad. En este artículo se presenta v-RDF-SI, una de las primeras soluciones de archivado RDF cuyo objetivo es combinar tanto la compresión como la consulta eficiente. En v-RDF-SI se extienden representaciones RDF existentes basadas en estructuras de datos compactas, con el fin de proporcionar un soporte eficiente para consultas basadas en versiones en un espacio comprimido. Se presentan dos implementaciones de v-RDF-SI, denominadas v-RDFCSA y v-HDT, basadas, respectivamente, en RDFCSA (un autoíndice RDF) y en HDT (una representación RDF comprimida respaldada por el W3C). El artículo presenta una evaluación experimental exhaustiva de v-RDF-SI utilizando el benchmark BEAR, cuyos resultados muestran que v-RDF-SI reduce drásticamente los requisitos de almacenamiento, llegando a utilizar hasta 40 veces menos espacio que los baselines proporcionados por BEAR, consolidando representaciones que utilizan un cuarto del espacio requerido por las alternativas basadas en estructuras de datos compactas. Asimismo, v-RDF-SI ofrece tiempos de consulta significativamente más rápidos en la mayoría de los casos. En promedio, las variantes más rápidas de v-RDF-SI superan al resto de las alternativas estudiadas en casi un orden de magnitud.

RDF compression and querying are consolidated topics in the Web of Data, with a plethora of solutions to efficiently store and query static datasets. However, as RDF data changes along time, it becomes necessary to keep different versions of RDF datasets, in what is called an RDF archive. For large RDF datasets, naive techniques to store these versions lead to significant scalability problems. In this paper, we present v-RDF-SI, one of the first RDF archiving solutions that aim at joining both compression and fast querying. In v-RDF-SI, we extend existing RDF representations based on compact data structures to provide efficient support of version-based queries in compressed space. We present two implementations of v-RDF-SI, named v-RDFCSA and v-HDT, based, respectively, on RDFCSA (an RDF self-index) and HDT (a W3C-supported compressed RDF representation). We experimentally evaluate v-RDF-SI over a public benchmark named BEAR, showing that v-RDF-SI drastically reduces space requirements, being up to 40 times smaller than the baselines provided by BEAR, and 4 times smaller than alternatives based on compact data structures, while yielding significantly faster query times in most cases. On average, the fastest variants of v-RDF-SI outperform the alternatives by almost an order of magnitude.