RDFCube

Overview †

RDFCube is an indexing scheme to provide efficient query processing for RDF triples on a distributed environment.

So far, several conventional P2P-based RDF triple stores have been proposed. They, however, designed merely for triple retrieval rather than for triple join query processing. Consequently, they suffer from an unnecessary data transfer problem. Because to perform a join operation they must gather all candidate answers into a node.

Our scheme uses a three-dimensional hash index called RDFCube that is designed based on the structure of an RDF triple. And then, we introduce bit information called an existence flag that represents the presence or absence of triples in the index.

The bit information is useful for processing a join query because we can narrow down the candidate triples by performing AND operation between the bits and transfer only the actual present candidate triples. As a consequence, this scheme markedly reduces the amount of data that is transferred among nodes.

RDFCube Model †

RDFCube consists of a three-dimensional hash space. Axes in RDFCube respectively represent hash spaces for subject, predicate and object as shown below.

This RDFCube scheme consists of a set of cubes of the same size called cells, each of which contains a bit called an existence flag that indicates the presence or absence of triples mapped into the cell. The existence flag of the cell is set to on when an RDF triple is mapped into a cell.

Two Distributed Hash Tables †

We build a distributed hash table called RDFCube DHT to store bit information of RDFCube in a distributed environment. The RDFCube DHT uses a cell matrix as a key (e.g. [*,*,0]). It stores the associated bit matrix as a value (on the left side in the below figure).

RDFCube DHT stores only bit information to efficiently perform join operations. Therefore RDFCube has no RDF triple data. So we use RDFPeers to store triples in a distributed environment.

RDFPeers DHT stores a triple in a P2P network using each element of the triple as a key (on the right side in the below figure). Because RDFCube does not store triples, but stores bit information, RDFCube DHT is used as an index for RDFPeers.

Join Operation using Existence Flag on RDFCube †

Query processing for the join operation is as follows: i) we first get bits information from RDFCube DHT; and then ii) perform AND operations using the bits; and finally iii) we get a set of candidate answer triples from RDFPeers DHT using the results of the AND operation.