  The Web of Data has been gaining momentum and this leads to increasingly
publish more semi-structured datasets following the RDF model, based on atomic
triple units of subject, predicate, and object. Although it is a simple model,
compression methods become necessary because datasets are increasingly larger
and various scalability issues arise around their organization and storage.
This requirement is more restrictive in RDF stores because efficient SPARQL
resolution on the compressed RDF datasets is also required.
  This article introduces a novel RDF indexing technique (called k2-triples)
supporting efficient SPARQL resolution in compressed space. k2-triples, uses
the predicate to vertically partition the dataset into disjoint subsets of
pairs (subject, object), one per predicate. These subsets are represented as
binary matrices in which 1-bits mean that the corresponding triple exists in
the dataset. This model results in very sparse matrices, which are efficiently
compressed using k2-trees. We enhance this model with two compact indexes
listing the predicates related to each different subject and object, in order
to address the specific weaknesses of vertically partitioned representations.
The resulting technique not only achieves by far the most compressed
representations, but also the best overall performance for RDF retrieval in our
experiments. Our approach uses up to 10 times less space than a state of the
art baseline, and outperforms its performance by several order of magnitude on
the most basic query patterns. In addition, we optimize traditional join
algorithms on k2-triples and define a novel one leveraging its specific
features. Our experimental results show that our technique overcomes
traditional vertical partitioning for join resolution, reporting the best
numbers for joins in which the non-joined nodes are provided, and being
competitive in the majority of the cases.
