BitMat is a main memory based bit-matrix structure for representing a large set of RDF triples, designed primarily to allow processing of conjunctive triple pattern (join) queries. The key aspects are as follows: i) its RDF triple-set representation is compact compared to conventional disk-based and existing main-memory RDF stores, ii) basic join query processing employs logical bitwise AND/OR operations on parts of a BitMat, and iii) for multi-joins, intermediate results are maintained in the form of a BitMat containing candidate triples without complete materialization, thereby ensuring that the intermediate result size remains bounded across a large number of join operations, provided there are no Cartesian joins. We present the key concepts of the BitMat structure, its use in processing join queries, describe our experimental results with RDF datasets of different sizes (from 0.2 to 47 million), and discuss the use case scenarios.
RDF [
Most of the other RDF store systems depend on building efficient auxiliary indexes on the RDF data and using them either for specific type of queries or to improve the overall query performance. In contrast, in our approach, BitMat which is an compressed inverted index structure itself makes up the primary storage for RDF triples. Our proposed query processing algorithm voids the need to uncompress this data at any point during query processing.
Generic relational data can have varied dimensions (i.e. number of columns), and hence the SQL query processing algorithms have to encompass this nature of relational data. As opposed to that, an RDF triple is a fixed 3-dimensional (S, P, O) entity and the dimensionality of SPARQL conjunctive triple pattern queries is also fixed (which depend on the number of conjunctive patterns in the query). Hence while building the BitMat structure and query processing algorithms, we made use of this fact.
In essence, BitMat is a 3-dimensional bit-cube, in which each cell is a bit representing a unique triple denoting the presence or absence of that triple by the bit value 1 or 0. This bit-cube is flattened in a 2-dimensional bit matrix for implementation purpose. Figure 1 shows an example of a set of RDF triples and the corresponding BitMat representation.
Subject Predicate :the_matrix :released_in :the_thirteenth_floor :released_in :the_thirteenth_floor :similar_plot_as :the_matrix :is_a :the_thirteenth_floor :is_a
Object "1999" "1999" :the_matrix :movie :movie Distinct subjects: [ :the_matrix, :the_thirteenth_floor ] Distinct predicates: [ :released_in, :similar_plot_as, :is_a ] Distinct objects: [ :the_matrix, "1999", :movie ]
:the_matrix :the_thirteenth_floor 0 1 0 :released_in 0 1 0 :similar_plot_as 0 0 0 1 0 0
:is_a 0 0 1 0 0 1 Note: Each bit sequence represents sequence of objects (:the_matrix, "1999", :movie)
If the number of distinct subjects, predicates, and objects in a given RDF
data are represented as sets Vs, Vp, Vo, then a typical RDF dataset covers a very
small set of Vs × Vp × Vo space. Hence BitMat inherently tends to be very sparse.
We exploit this sparsity to achieve compactness of the BitMat by compressing
each bit-row using D-gap compression scheme [
Since conjunctive triple pattern (join) queries are the fundamental building blocks of SPARQL queries, presently our query processing algorithm supports only those. These queries are processed using bitwise AND, OR operations on the compressed BitMat rows. Note that the bitwise AND, OR operations are directly supported on a compressed BitMat thereby allowing memory efficient execution of the queries. At the end of the query execution, the resulting filtered triples are returned as another BitMat (i.e. a query’s answer is another result BitMat). This process is explained in Section 4.
Figure 2 shows the conjunctive triple pattern for movies that have similar plot
and the corresponding result BitMat. Unlike the conventional RDF triple stores,
1 E.g. In D-gap compression scheme a bit-vector of “0011000” will be represented as
[0]-2,2,3. A bit-vector of “10001100” will be represented as [
Query: (?m :similar_plot ?n . ?m :is_a :movie . ?n :is_a :movie)
:released_in :similar_plot_as :is_a :the_matrix 0 0 0 0 0 0 0 0 1 :the_thirteenth_floor 0 0 0 1 0 0 0 0 1
A conventional SPARQL join query engine produces zero or more
matching subgraphs (each resulting row with variable bindings identifies a matching
subgraph). BitMat join processing returns a set of distinct triples in the result
BitMat that together form all the matching subgraphs. Currently we are
working on an algorithm to enumerate all the matching subgraphs – which is not
presented here. But even without this last phase of result generation, current
query processing algorithms can be used for:
– ‘EXISTS’ or ‘ASK’ queries as very large multi-joins can be performed in
memory using BitMat (existence of one or more 1 bits in the resulting BitMat
indicates that the query will produce at least one matching subgraph).
– As a precursor to an in-memory query processing engine (e.g. Jena-ARQ [
BitMat is designed specifically to process conjunctive triple pattern queries and presently the query processing interface does not support full SPARQL syntax or other SPARQL constructs.
The rest of the paper is organized as follows. Section 2 gives a brief overview of the related work. Section 3 describes the BitMat structure and its composition in greater details. Sections 4 and 5 describe the basic algorithm of single join procedure and an algorithm for multi-join based on the single-join algorithm respectively. Section 6 gives our evaluation of the system, and Section 7 concludes the paper with strengths and weaknesses of the present structure of the BitMat and query processing system. 2
The structure of a BitMat is somewhat similar to the idea of bitmap indexes,
which are used in relational database systems and more recently by the Virtuoso
RDF store [
In addition to these, there are various systems being developed for processing
RDF data. Some notable ones are – Hexastore [
Out of these, Hexastore and RDF-3X exploit the nature of RDF data by creating 6-way indexes (SPO, SOP, PSO, POS, OSP, OPS) on it. RDF-3X goes one step further by compressing these indexes and organizing them as clustered B+-trees. BRAHMS and GRIN mainly use their system for path-based queries on RDF graph. But they have not published results on very large RDF graphs, putting the scalability of their system under question. BRAHMS have used LUBM data of only 6 million triples and GRIN has published results for only upto 17,000 triples3.
The notable difference between these systems and BitMat is that – BitMat’s conjunctive triple pattern query processing algorithm which controls the intermediate memory utilization in a large multi-join query.
The structure that comes closest to BitMat is RDFCube [
SPARQL query language, which is structurally quite similar to the SQL query
language [
A bit-cube of RDF triples is a 3-dimensional structure with subject (S), predicate (P), and object (O) dimensions. Individual cell is a single bit, and 1 or 0 value of the bit represents presence or absence of the triple. This conceptual bit-cube can be represented as a concatenation of (S,O) or (O,S) matrices for all the distinct predicates thereby forming a mat of bits, BitMat. Concatenation done along the subject dimension is referred to as a subject BitMat and concatenation done along the object dimension is referred to as an object BitMat. Altogether, there are 6 ways of flattening a bit-cube into a BitMat (as is the case of six-way 3 GRIN focuses on path-like queries which are not even expressible in current SPARQL query language. indexes on the RDF data). For the current set of experiments, we have used subject BitMats. Exploring other structures of BitMat is a part of future work. 3.1
BitMat is constructed from a set of RDF triples as follows: Let Vs, Vp, and Vo represent the sets of distinct subject, predicate, and object values occurring in a RDF triple set. Let Vso represent the Vs ∩ Vo set. These four sets are mapped to the integer sequence based identifiers as shown below: – Common subjects and objects: Set Vso is mapped to a sequence of integers: 1 to |Vso| in that order. – Subjects: Set Vs − Vso is mapped to a sequence of integers: |Vso| + 1 to |Vs|. – Predicates: Set Vp is mapped to a sequence of integers: 1 to |Vp|. – Objects: Set Vo − Vso is mapped to a sequence of integers: |Vso| + 1 to |Vo|. Basically, each ID-space is treated independently with the exception that URIs which appear as subjects as well as objects are assigned the same sequence identifiers. This is done to facilitate the subject-object (S-O) cross dimensional join as discussed in Section 4. Cross-dimension joins over subject-predicate (SP) or predicate-object (P-O) dimensions are rare in the context of assertional RDF data. Since the large scale RDF data available on the web is predominantly assertional, presently we do not handle S-P or P-O cross dimensional joins.
The above mapping is a direct representation of the position of those triples in the BitMat structure. For the example given in Section 1, :the matrix as a subject is mapped to 1, :the matrix as an object is also mapped to 1, :the thirteenth- floor is mapped to 2, :similar plot as is mapped to 2 etc. Hence triple (:the thirteenth floor :similar plot as :the matrix) is represented as (2 2 1) indicating to set the first bit (O-position) in the second row (S-position) of the second (S,O) matrix (Pposition) (see Figure 1). A complete BitMat is built this way by setting the bit corresponding to each encoded RDF triple. Although this is the conceptual structure of a BitMat, we build the compressed BitMat directly from the encoded triple set as explained further in Section 6. 3.2
The process of evaluating conjunctive triple pattern (join) queries is carried out with three primitive operations on a BitMat. They are as follows: (1) Filter: Filter operation is represented as ‘filter(BitMat, TriplePattern) returns BitMat’. It takes an input BitMat and returns a new BitMat which contains only triples that satisfy the TriplePattern.
Effectively, filter operation on a BitMat involves clearing the bits of the triples that are filtered out. For example, a triple pattern with only bound subject value like filter(BitMat, ‘:s1 ?p ?o’), clears all the bits in all the rows other than the row corresponding to the bound subject value :s1 etc. (2) Fold: Fold function represented as ‘fold(BitMat, RetainDimension) returns bitarray’ folds the input BitMat along the two dimensions other than the RetainDimension.
For example, if RetainDimension is set to ‘object’, then BitMat is folded along the subject and predicate dimensions resulting into a single bitarray. Intuitively, bits set to 1 in this bitarray indicate the presence of at least one triple with the object corresponding to that position in the given BitMat. Typically fold is called on the BitMat returned by filter. E.g. fold(filter(BitMat, ‘:s1 ?p ?o’), ‘object’).
(3) Unfold: Specified as ‘unfold(BitMat, MaskBitArray, RetainDimension) returns BitMat’ takes a BitMat, a bitarray, and unfolds the bitarray on the BitMat.
Intuitively, in the unfold operation, for every bit set to 0 in the MaskBitArray all the bits corresponding to that position of the RetainDimension in a BitMat are cleared. Typically MaskBitArray is generated by a bitwise AND of the bitarrays returned by fold operations before. E.g. unfold(BitMat, ‘101001’, ‘predicate’) would result in clearing all the bits in second, fourth, and fifth (S,O) matrices which correspond to predicates mapped to {2, 4, 5}.
Filter, fold, and unfold operations are implemented to operate on a compressed BitMat without uncompressing it. 4
A conventional SPARQL join query processing engine produces zero or more matching subgraphs (each resulting row with the variable bindings identifies a matching subgraph) (see Figure 3). The query being evaluated is (:s1 ?p ?x . :s3 ?p ?y). Intuitively, every resulting matching subgraph is a proper subgraph of the original RDF graph G, which satisfies the SPARQL query graph pattern (provided there are no Cartesian joins).
BitMat based join algorithm is given in Algorithm 1 and is elaborated as follows.
Algorithm 1 BitMat SingleJoin(BM, tp1, tp2) returns BitMat 1: Let BM be the BitMat of the original triple-set 2: Let tp1 and tp2 be the two triple patterns in the join 3: /* filter and fold */ 4: BMtp1 = filter(BM, tp1) 5: BMtp2 = filter(BM, tp2) 6: BitArr1 = fold(BMtp1, RetainDimensiontp1) 7: BitArr2 = fold(BMtp2, RetainDimensiontp2) 8: BitArrres = BitArr1 AND BitArr2 9: BMtp1 = unfold(BMtp1, BitArrres, RetainDimensiontp1) 10: BMtp2 = unfold(BMtp2, BitArrres, RetainDimensiontp2) 11: /* Produce the final result BitMat */ 12: Let BMres be an empty BitMat 13: BMres = BMtp1OR BMtp2
On lines 4, 5 filter operation is used to get two BitMats containing only triples satisfying the first and second triple pattern respectively. This resembles the selection operator used in SQL style queries. Fold is used on these two BitMats to get BitArr1 and BitArr2. Fold is analogous to the projection operator Join over :s1 ?p ?x :::::::sssssssM1111122a:::::::ppppppppt2231112ri:::::::poooooool2432112es to:::::::sssssssa3322333B:::::::ippppppptM1132331a:::::::ooooooot1433345 :::sss213 :o1111 :o12 :o3:p1:o41 :o15 :o1 :o112 :o:p132 :o14 :o5 :o1 :o2 :o:p11133:s3:o?14p :?oy5 1 fold(retainDIM = predicate)
1 1 :s1 :o11 :o21 :o:3p1 :o4 :o5 :o1 :o2 :p:o23 :o4 :o5 :o1 :o2 :p:o33 :o4 :o5
1 1 1 :p1 :p12 :1p3 fold(retainDIM = predicate) ::ss31 11 AND facFbFisoliioltttrres2errteirhbnsseipotoesopatmhirnemreardaarnpiynttlrisiiogoccwonisttof)ysp:(rsoa:o1sfrde1tahusn?ecedpetfsi:?tgsox2u3)0rB(eaaainttssMhdiepan(ye:ttssera3rtrnhe?aepsllhy?oyw).n :p1 :p2 :p3
Result 1 1 :s3 1 :o1 :o2 :o:p31 :o4 :o5 :o1 :o2:p:2o3 :o4U:nof5old(:wo1ith:ore2tai:no:Dp33IM:=o4pre:doi5cate) :Uon1fo:lod2(wit::hpo13reta:oin4DI:Mo5= p:roe1dic:aot2e):o:p32 :o4 :o5 :o1 :o2 :o:p33 :o4 :o5 :s1 1 1 1 :s3 1 1 1 1 1
Bits cleared
:p1 :p2 :p3 :o1 :o2 :o3 :o4 :o5 :o1 :o2 :o3 :o4 :o5 :o1 :o2 :o3 :o4 :o5 Result triples (with BitMat) Result BitMat:::sss123 11 1 1 1 11 1 ::::::::ssssssss33333111 ::::::::pppppppp11133311 ::::::::oooooooo41543321 1 1 Similar to the filter operation shown as a bit array above, unfold is shown on a bit array for the simplicity of the figure.
Matching subgraphs (as would be produced by a query engine) (variable bindings)
T1.S T1.P T1.O T2.S T2.P T2.O
Ttriple transform ::::::::ssssssss11111111 ::::::::?ppppppppp11133111 ::::::::?oooooooox22233111 ::::::::ssssssss33333333 ::::::::?ppppppppp11133111 ::::::::?ooooooooy44351541 of SQL queries. If RDF triples are presented in a 3-column table (S, P, O), then these bitarrays correspond to a single column in the table and bit positions set to 1 indicate presence of the S, P, or O values corresponding to those bit positions. Bitwise AND is performed on these bitarrays which is same as a relational join on the column represented by RetainDimension. The result of the bitwise AND is unfolded back on the filtered BitMats BMtp1 and BMtp2. Finally the two BitMats obtained after unfold are combined using bitwise OR on the corresponding rows of them. This procedure is depicted in Figure 3.
It can be shown and proved step-by-step that filter, fold, and unfold operators
can be mapped to equivalent SQL operations and the correctness of the algorithm
can be proved. For the scope of this paper, we have omitted these details, but
they can be referred in our technical report [
For simplicity of presentation of the algorithm, we have shown it only for a single join with two triple patterns, but the same algorithm can be extended to ‘n’ triple patterns joining over a single join variable occurring in the same dimension by performing filter and fold on each triple pattern, ANDing all the bitarrays generated by the fold operation, unfolding the AND results on each of the filtered BitMats, and finally combining all these BitMats with bitwise OR on the corresponding rows to get the result BitMat. The procedure for subjectobject cross dimensional join (as shown by an example in Section 3.1) is slightly different and is elaborated in Section 4.1. Bitwise AND operation can be performed on two bitarrays only if the corresponding bit positions have the same URI or literal values mapped to them. This is the case for the same dimension joins.
Cross-dimensional joins need special handling. (?s :p1 ?x . ?y :p2 ?s) is an example of subject-object (S-O) cross-dimensional join, for which we need to perform bitwise AND on the subject and object bitarrays. As elaborated in Section 3.1 and Section 3.2, every bit position in the folded bitarray corresponds to a unique identifier assigned to a URI or literal in the respective subject, predicate, object ID space. Since URIs which appear as subjects as well as objects are allocated the same IDs sequentially from 1 to |Vso|, for a S-O join, bitwise AND is performed only on the first |Vso| bit positions of the respective subject and object bitarrays and rest all bits are cleared.
As mentioned earlier in Section 3.1, other cross-dimensional joins (S-P and P-O) are not that common in the Semantic Web instance (assertional) data and hence are not supported at present. 5
In a multi-join two or more triple patterns join over two or more join variables, e.g. (:s1 ?p ?o . :s2 ?p ?y . ?z :p3 ?o). In a conventional relational join processing, multi-join evaluation can be presented as an operator tree where each internal node is a self-contained representation of the materialized results of the join subtree below it. BitMat single join procedure, as elaborated in Section 4, does not materialize the query results (i.e. does not produce matching subgraphs), but represents the candidate result triples with the result BitMat. Thus, if we simply extend the single-join BitMat algorithm to multi-joins, evaluation of a later join can change the variable bindings produced by an earlier join. Specifically, if the dependency between different join variables is not captured and resolved then a BitMat join can produce false positives. Hence is the need for a different algorithm for multi-join queries. 5.1
BitMat Multi-Join Algorithm ?s ?y ?p ?x eij ?s ?m :o6 ?s :p4 ?y :s1 ?p ?x
?n :p3 ?x :s2 ?p ?y
For the present considerations, we do not handle joins with Cartesian products. For better understanding of the algorithm, we develop the theory by constructing a bipartite graph G which captures the conjunctive triple pattern and join variable dependencies (see Figure 4).
– Each join variable in the multi-join is a node (denoted as jvar-node). – Each triple pattern is a node (denoted as tp-node). – There is an edge between a jvar-node and a tp-node if the join variable represented by the jvar-node appears in the triple pattern represented by the tp-node.
Algorithm 2 BitMat MultiJoin(BM, G) returns BitMat
Although for graph G shown in Figure 4 there are exactly two edges per jvar-node corresponding to a join variable, one could have more than two edges per join variable.
The algorithm to evaluate a multi-join using graph G is given in Algorithm 2. For simplicity, we assume the existence of certain methods without describing them in the algorithm, viz. method getTriplePattern(vj ) returns the triple pattern associated with the tp-node node vj , and getDimension(vi, tp) returns the position (dimension) of the join variable vi in triple pattern tp, e.g. getDimension(?s, (?s :p1 ?x)) returns subject, getDimension(?s, (?y :p2 ?s)) returns object, and getDimension(?s, (?s :p2 ?s)) returns subject and object (this is a special form of S-O cross dimensional join and is captured by the implementation of the BitMat multi-join algorithm, but not shown in Algorithm 2 for simplicity).
Associated with each jvar-node is a bitarray of the most recent result of a join evaluated over that join variable. Initially all the bits in these bitarrays are set to 1 (as explained in the Algorithm 2). Each tp-node has a BitMat associated with it, which is initially set to the result of the filter(BM, getTriplePattern(vj )) where vj is the tp-node. The repeat-until loop (between lines 10 and 31) in Algorithm 2 iterates over all the join variables in the query, processing those joins until none of the BitArri change. For each join variable, it folds the BitMats associated with all the triple patterns which have that join variable (lines 16, 19) and performs a bitwise AND on the generated BitArrays (line 20). At the end of the loop (17-21) the final AND result (BitArri) is unfolded back on all the BitMats in the set T P (line 28). Lastly, after the repeat-until loop ends, result BitMat is generated by a bitwise OR of all the BitMats associated with all the triple patterns (line 34) in the query.
Although the multi-join algorithm is constructed as a continuous loop, it can be proved that this loop will converge in a finite number of iterations. In each iteration of the loop, we are performing a bitwise AND on the previous BitArri and the new T empBitArr folded from the BitMat of the triple pattern having that join variable. After each bitwise AND, the resulting BitArri is unfolded on the BitMats associated with all the triple patterns having that join variable. Since we are doing a bitwise AND operation and unfold which expands the BitArri on the BitMats, only a bit set to 1 can be flipped to 0. Hence the number of set bits (and hence the triples in the BitMats) reduce monotonically per iteration of the loop and the loop ends at a point when none of the BitArri change after an AND (lines 20, 22) (in the worst case when all the bits in all the BitArrays are set to 0, in which case the final join result is null ).
We provide experimental results in Section 6 for the typical number of iterations taken by the loop. It can be seen that for each join variable, we employ the same basic operations as used for a single join operation. 6
This section describes our experiments and evaluation of the BitMat structure and join queries. 6.1
The BitMat structure and join algorithms have been developed as a C program meant to be run on a Linux distribution. All the experiments were carried out on Gentoo Linux distribution on a Dual Core AMD Opteron Processor 870 with 8GB of RAM. The BitMat program was run as a normal user process with the default priority as set by the Linux system. Gcc ver. 4.1.1 compiler is used to compile the code with compiler optimization flag set to -O6. The RDF N-triple file is first preprocessed using a Perl script to generate a raw RDF triple file by encoding all the triples using the sequence based identifiers allocated to URIs and literals (refer to Section 3.1). Simple bash sort command is used to sort these encoded triples on subject-ID, predicate-ID, object-ID. This preprocessing is needed to be carried out only once per dataset, and the time taken by it varies linearly with respect to the size of the triple-set (e.g. it takes around 30 minutes for Wikipedia 47 million triple-set). BitMat’s load function expects either a raw RDF triple file or a disk image of the previously generated BitMat. Given a conjunctive triple pattern (join query), another small script is used to transform the conjunctive triple pattern by encoding all the fixed URIs and literals present in the query using the corresponding identifiers, so that the BitMat join processing can operate on the ID-based values. 6.2
We used different RDF triple sets of varying sizes for testing BitMat structure’s
memory utilization. UniProt-0.2million and UniProt-22million triple sets were
extracted from a larger UniProt dataset [
Dataset #Triples #Subjects #Predicates #Objects Uniprot 0.2million 199,912 30,007 55 45,754
LUBM 1million 1,272,953 207,615 18 155,837 LUBM 6million 6,656,560 1,083,817 18 806,980 Uniprot 22million 22,619,826 5,328,843 91 4,516,903
Wiki 47million 47,054,407 2,162,189 9 8,268,864 and then compressing them. This results into smaller load times to construct a BitMat from a raw RDF file. The memory-image of a compressed BitMat can be written out to the disk as a binary file. Loading from a disk-image just reads this binary file into a BitMat structure in memory, hence loading from a disk image takes even lesser time than loading the BitMat from sorted triple-ID file.
Note that each conjunctive triple pattern query is converted into an
internal representation where all the fixed values in the query are replaced by their
corresponding integer mapping IDs (refer Section 3.1). Although the mapping
dictionary consumes larger space than the primary BitMat structure, it does not
need to be kept in memory while processing the queries.
To test our implementation of the join algorithm, we executed a list of single join
queries on a smaller dataset (UniProt 0.2 million) and also measured the response
times (for the list of queries, see Table 3). Typically, the subject join query
times varied from 0.019sec to 0.04sec, for predicate joins the variation was from
0.0041sec to 0.062sec, for object dimension join it was from 0.0094sec to 0.128sec,
and for S-O cross dimensional joins it was from 0.08sec to 0.28sec. Variation
in the time depended on different factors such as the selectivity4 of the triple
pattern and join condition, number of total variables in the query, dimension of
the variables in the query, etc. as explained further below. For multi-joins, we
used a mix of queries taken from UniProt queries [
Memory requirements: The “Sum of BitMat sizes” is the maximum memory size of all the BitMats associated with the triple patterns including the result BitMat at any point during the query execution. Note that BitMat size for a single pattern is the size obtained after applying the filter, which usually is much smaller than the original BitMat since a majority of the triple patterns have a fixed value in at least one of the S, P, O positions. But we have successfully tried queries having all variable positions in one or more triple patterns as well (e.g. 4 A lower selective triple pattern has more triples associated with it and vice versa. a Wikipedia query in Table 4). The sizes of these BitMats are highest at the beginning of the query, and they go on reducing monotonically as the multi-join algorithm executes. This is due to the fact that filter, fold, and unfold operate on a compressed BitMat, and in every iteration of the multi-join algorithm, triples get eliminated monotonically, hence the BitMat size shrinks. Also we do not materialize the intermediate join results, but represent them as candidate triples in the result BitMat. The size variation also depended on the selectivity of the triple patterns. The higher the selectivity, the lower the BitMat size (due to D-gap compression).
The variation of the query execution times can be attributed to three key factors: i) join-dimension (e.g. whether it is a subject, predicate, object, or S-O cross dimension join), ii) selectivity of the triple patterns, and iii) the order of the join evaluation.
Join dimension: Since we are using a subject BitMat for joins on all the dimensions, subject-dimension joins inherently benefited, as folding and unfolding of a compressed BitMat by retaining the subject dimension involves only updating the relevant subject rows without accessing the compressed content. Since the number of distinct predicates is usually low in the datasets, predicate joins performed well too. However, accessing object dimension in a compressed subject BitMat needed special handling, and hence we observe that the structure of the subject BitMat is unsuited for the object joins since unfold requires accessing every O-bit position within each subject row, and for each predicate in Query (?X rdf:type ub:GraduateStudent) (?Y rdf:type LUBM (1) 2.1MB 994 ub:University) (?Z rdf:type ub:Department) (?X ub:memberOf ?Z) (?Z ub:subOrganizationOf ?Y) (?X ub:undergraduateDegreeFrom ?Y) (?X rdf:type ub:UndergraduateStudent) LUBM (1) 4.6MB 10,113 (?Y rdf:type ub:FullProfessor) (?Z rdf:type ub:Course) (?X ub:advisor ?Y) (?Y ub:teacherOf ?Z) (?X ub:takesCourse ?Z)
LUBM (6) 23.1MB 52,029 (?s :title “Dilbert Bit Characters”) (?s ?p ?x)(?s2 Wikipedia ?p ?y) (?s2 rdf:type wiki:Article) (?s2 ?n ?z) (?s2 (47) wiki:internalLink ?m) (?s :title “Dilbert Bit Characters”) (?s ?p Wikipedia :Bully)(:Johnny the Homicidal Maniac ?p ?o) (47) (?o rdf:type wiki:Article) 1.9GB
1 26.5MB 128 turn. Also for the queries with a triple pattern having variable predicate dimension and a fixed object dimension, e.g. (?s ?p :o1), fold operation will require to access a single bit position within all the subject rows, for all the predicates. This effect was observed specifically on very large datasets when the selectivity of the triple pattern was low. This further brought our attention to the aspect of using all or some of the six possible BitMats that can be flattened from a 3D bit-cube, as we explained in Section 3. Usage of different BitMat structures requires changes in the present multi-join algorithm, as fold and unfold operations have to interoperate between multiple types of BitMats. We are currently exploring this aspect.
Selectivity: Initial selectivity of the triple pattern as well as the selectivity of join played a role in the faster convergence of the multi-join loop. Selectivity of the triple pattern or join result also plays key role in the memory utilization. Higher selectivity of the triple patterns and join results reduces the BitMats’ size faster.
Join order: Although in our experiments the multi-join algorithm’s loop typically converged in 3 or 4 iterations, as it can be noted from Table 4, the second LUBM query took many more iterations (15-18) for 1 million as well as 6 million dataset. As join ordering affects the query execution time and size of the intermediate results in a relational scheme, it affects the number of iterations of the BitMat multi-join algorithm as well. In case of a BitMat join, due to the use of compressed BitMats and the fact that we are not materializing the intermediate results, memory utilization was not affected though. For the second LUBM query, we observe that evaluating join over ?Y first brought down the multi-join algorithm iterations from 15 to 12. We plan to use an augmented version of the multi-join bipartite graph G (not shown in Figure 4) that can be used to capture the cyclic or acyclic dependency, so that we can minimize the number of iterations needed to complete the multi-join processing. 7
As shown by our experiments, one of the main advantages of the BitMat structure and joins is that the memory requirement of the system is very low. Since the intermediate or final results in a multi-join are not completely materialized, the result size is always bounded by the size of the original BitMat. If the size of the original BitMat is SizeBM and n is the number of triple patterns in a multi-join query, then the instantaneous memory utilization while performing a join is always bounded by O(n ∗ SizeBM ) and the final join result size is always bounded by O(SizeBM ).
We are presently developing an efficient algorithm to enumerate all the matching subgraphs from a result BitMat (i.e. final variable bindings). With this the BitMat main-memory triple store can be used as an independent SPARQL join query engine. Also as pointed out in the experimental section, we are exploring the usage of BitMats created by flattening the 3D bit-cube on different dimensions for further improving the performance of the multi-join queries. Development of this algorithm for a fair comparison of query performance and memory utilization with any other state-of-the-art RDF triplestore, is a part of our ongoing work.
The present BitMat query processing algorithm only performs the step of pruning the candidate RDF triples but does not produce final matching subgraphs. Hence in this paper, we have just presented empirical results of query performance and memory utilization.
The key aspect of BitMat’s algorithms is that they always work on compressed data without uncompressing it at any point.
Due to the ability to create a disk image of a BitMat in memory (as explained in Section 3.1), the BitMat system can be used as a persistent data-store as well, by exploiting the benefits of performing all the operations in main-memory once the BitMat is reloaded from the disk image.
Finally, we conjecture that by creating clusters of machines, each deploying BitMats, extremely large RDF stores can be created and processed in memory. Our future work includes exploring how this can be realized on server-farm like clusters as well as shared memory supercomputers for very large RDF datasets. We would like to thank Dr. Jagannathan Srinivasan of Oracle Corp. for his invaluable inputs during the early development of this work.