TripleRush1 is a parallel in-memory triple store designed to address the need for e cient graph stores that quickly answer queries over large-scale graph data. To that end it leverages a novel, graph-based architecture. Speci cally, TripleRush is built on a parallel and distributed graph processing framework. The index structure is represented as a graph where each index vertex corresponds to a triple pattern. Partially matched copies of a query are routed in parallel along di erent paths of this index structure. Among the existing triple stores, we only know of Trinity.RDF [3] to be implemented on top of a distributed graph processing abstraction. Trinity.RDF represents the graph with adjacency lists and combines traditional query processing with graph exploration. In TripleRush, an RDF triple is represented as a vertex and SPARQL queries are answered with a purely exploration-based approach. In other words, TripleRush does not use any joins in the traditional sense but searches the index graph in parallel. Whilst traditional stores pipe data through query processing operators, TripleRush routes query descriptions to data. We implemented TripleRush on top of our graph processing framework Signal/Collect [2]. TripleRush takes less than a third of the time to answer queries compared to the fastest of three state-of-the-art triple stores, when measuring time as the geometric mean of all queries for two benchmarks.
Signal/Collect [
The key features of Signal/Collect are: a) it is suitable for expressing data- ow algorithms and transparently parallelizes them, using vertices as processing elements and edges for message propagation, b) it supports di erent types of vertices, c) the graph structure can be changed during computation, d) it supports bulk-messaging and combiners for message-passing e ciency, e) it supports asynchronous scheduling, and f) it is exible with regard to edge representation, messages can be routed directly. TripleRush is a triple store with three types of Signal/Collect vertices: 1 Source code at https://github.com/uzh/triplerush
Elvis inspired Dylan Elvis * *
Triple vertices (level 4, Fig. 1) represent triples in the database. Each contains subject, predicate, and object information.
Index vertices (levels 1-3, Fig. 1) represent triple patterns and are responsible for routing partially matched copies of queries (referred to as query particles ) towards triple vertices that match their respective patterns. They also contain subject, predicate, and object information, but one or several of them are wildcards.
Query vertices (Fig. 2) are added to the graph for each query that is being executed. The query vertex emits the rst query particle that traverses the index structure. Once all query particles|successfully matched or not| get routed back to their respective query vertex, it reports the results and removes itself from the graph.
The graph is built bottom-up, starting by creating a triple vertex for each RDF triple. These vertices are added to Signal/Collect, which turns them into parallel processing units. A triple vertex will add its immediate index vertices (if they do not exist yet) and an edge from these vertices to itself. The construction process continues recursively for the index vertices until the parent vertex has already been added or the index vertex has no parent.
To ensure the uniqueness of a path from an index vertex to all triple vertices below it, an index vertex adds an edge from at most one parent index vertex, always according to the structure that is illustrated in Fig. 1.
The index graph we just described is di erent from traditional index structures, because it is designed for the e cient parallel routing of messages to triples that correspond to a given triple pattern. All vertices that form the index structure are active parallel processing elements that only interact via message passing.
Consider the subgraph shown in Fig. 2 and the query processing for the query: (unmatched = [ ?X inspired ?Y ], [ ?Y inspired ?Z ]; bindings = fg). The query execution starts by adding the query vertex to the TripleRush graph. 1
The query vertex emits a single query particle, which is routed (by Signal/Collect) to the index vertex that matches its rst unmatched triple 1
Query Vertex 6
Failure Success ?X inspired ?Y ?Y inspired ?Z
5 No vertex with id [ Jobs inspired * ] 4
2 Dylan inspired * * inspired Jobs
We further perform some optimizations: a) we do dictionary encoding, b) we remove the triple vertices and turn the third index level into binding index vertices, which hold a compact representation of all the triples that match their pattern, c) the index vertices on levels 1 and 2, in addition to a compact edge representation, use delta-encoding and variable length integers to further reduce memory usage, d) we use a query optimizer that reorders patterns based on cardinalities, e) we only send the tickets of the failed particles back to the query vertex, and f) we use bulk-messaging and message-combiners. 4
In order to evaluate TripleRush, we wanted to compare it with the fastest
related approaches. Trinity.RDF [
Consistent with the parallel Trinity.RDF [
The execution time covers everything from the point where a query is dispatched to TripleRush until the results are returned. Consistent with the Trinity.RDF setup, the execution times do include the time used by the query optimizer, but do not include the dictionary encoding and the triple materialization.
The results in Figure 3 show the fastest execution time of 10 runs for all
stores. The results for the other stores are from the Trinity.RDF paper [
LUBM-‐160 Benchmark
DBPSB-‐10 Benchmark
TripleRush Trinity.RDF RDF-‐3X (In Memory) BitMat (In Memory)
TripleRush Trinity.RDF RDF-‐3X (In Memory) BitMat (In Memory) L1 L2 L3 L4 L5 L6 L7
D1 D2 D3 D4 D5 D6 D7 D8
The need for e cient querying of large graphs lies at the heart of most Semantic Web applications. During the last decade, research in this area has made tremendous progress based on a database-inspired paradigm. Parallelizing these centralized architectures is a complex task. The advent of multi-core computers, however, calls for approaches that exploit parallelization.
With TripleRush we presented an in-memory triple store that divides the work among a large number of active processing elements that work towards a solution in parallel, and our evaluation shows that the performance of this approach is promising.