Space/time-efficient RDF stores based on circular suffix sorting

Abstract:

In recent years, RDF has gained popularity as a format for the standardized publication and exchange of information in the Web of Data. In this paper we introduce RDFCSA, a data structure that is able to self-index an RDF dataset in small space and supports efficient querying.

RDFCSA regards the triples of the RDF store as short circular strings and applies suffix sorting on those strings, so that triple-pattern queries reduce to prefix searching on the string set. The RDF store is then represented compactly using a Compressed Suffix Array (CSA), a proved technology in text indexing that efficiently supports prefix searches.

Our experiments show that RDFCSA provides a compact RDF representation, using less than 60\% of the space required by the raw data, and yields fast and consistent query times when answering triple-pattern queries (a few microseconds per result). We also support join queries, a key component of most SPARQL queries. RDFCSA is shown to provide an excellent space/time tradeoff, typically using much less space than alternatives that compete in time.

Dataset

• We used a pre-processed version of the English DBPedia dataset (3.5.1), where triples are represented as sequences of integer ids. It is available here [Dbpedia351.SPO.7z].

  The original English DBPedia dataset (3.5.1) is available at [Dbpedia].

Source code for RDFCSA

• The source code for RDFCSA is available here [sources.rdfcsa.v2.tar.gz]. It includes a Readme file, the source code, and scripts to build the index and run the querying experiments from the draft-paper including both simple-pattern queries and join queries.