SPARQL query answering with bitmap indexes - Archive ouverte HAL Access content directly
Conference Papers Year : 2012

SPARQL query answering with bitmap indexes

(1, 2, 3)


When querying RDF data, one may use reasoning to reach intensional data, i.e., data defined by sets of rules. This is usually achieved through forward chaining, with space and maintenance overheads, or backward chaining, with high query evaluation and optimization costs. Recent approaches rely on pre-computing the terminological closure of the data rather than the full saturation. In this setting, one can even query the data without resorting to backward chaining, using a so-called semantic index. However, these techniques are limited in the type of queries they can support. In this paper, we introduce a data storage technique which mitigates the space issues of forward-chaining. We show that it can also be used with a semantic index. We propose a new structure for the index that relies on bitmaps making it resilient to updates. Our experimental results demonstrate that our storage model significantly reduces the space required to store the data. We show that the indexes can be computed quickly and fit well in memory even for very large ontologies. Finally, we analyze how query answering is affected by the data layout.
Fichier principal
Vignette du fichier
swim2012-leblay.pdf (314.25 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-00691235 , version 1 (26-05-2012)


  • HAL Id : hal-00691235 , version 1


Julien Leblay. SPARQL query answering with bitmap indexes. SWIM - 4th International Workshop on Semantic Web Information Management - 2012, May 2012, Scottsdale, AZ, United States. ⟨hal-00691235⟩
216 View
297 Download


Gmail Facebook Twitter LinkedIn More