The permuted trie index {#sec:permuted}
=======================

In this section we introduce our trie-based index that solves the *triple indexing problem* mentioned in Section \[sec:intro\]: compressing a large set of integer triples by granting the efficient resolution of sequences of triple selection patterns. In particular, in Section \[subsec:core\] we introduce the base indexing data structure and in Section \[subsec:remapping\] and \[subsec:twotries\] we discuss two variants aimed at reducing redundancies in the representation.

In order to better support our design choices and explain the intuition behind the described ideas, we show in the following the results of some motivating experiments conducted on the dataset, dubbed as “the nucleus for a Web of Data” [@auer2007dbpedia], that is the English version of DBpedia (version 3.9) containing more than 351 millions of triples (see also Table \[tab:datasets\]). In Section \[sec:experiments\] we will report on the comprehensive set of experiments conducted to assess the performance in space and time of our implementations versus state-of-the-art competitors on publicly available RDF datasets of varying size and characteristics.

Data structure {#subsec:core}
--------------

As a high-level overview, our index maintains three different permutations of the triples, with each permutation sorted to allow efficient searches and effective compression as we are going to detail next. The permutations chosen are , and in order to (symmetrically) support all the six different triple selection patterns with one or two wildcard symbols: and over ; and over ; and over . The two additional patterns with, respectively, all symbols specified or none, can be resolved over any permutation, e.g., over the canonical in order to avoid permuting back each returned triple.

![A trie data structure representing a set of triples. Shaded boxes indicate pointers whereas the others refer to the nodes of the trie. The dashed arrows are just for representational purposes and point to the position written in the corresponding originating box. []{data-label="fig:trie"}]({{imgs/trie}})

Each permutation of the triples is represented as a 3-level trie data structure, with nodes at the same level concatenated together to form an integer sequence. We keep track of where groups of siblings begin and end in the concatenated sequence of nodes by storing such pointers as absolute positions in the sequence of nodes. Therefore, the pointers are integer sequences as well. Moreover, since the triples are represented by the trie data structure in sorted order, the $n$ node IDs in the first level of each trie are always complete sequences of integers ranging from 0 to $n-1$ and, thus, can be omitted. We can model each trie data structure with an array *levels*\[0..2\] of three objects, each one having two integer sequences of and . An exception is represented by \[0\] for which, as above discussed, nodes are missing, and by \[2\] for which pointers are missing. Refer to Figure \[fig:trie\] for a pictorial example in which the ordered set of triples $\{$(0,0,2), (0,0,3), (0,1,0), (1,0,4), (1,2,0), (1,2,1), (2,0,2), (2,1,0), (3,2,1), (3,2,2), (4,2,4)$\}$ is indexed.

The advantage of this layout is *two-fold*: first, we can effectively compress the integer sequences that constitute the levels of the tries to achieve small storage requirements; second, the triple selection patterns are made *cache-friendly* and, hence, efficient by requiring to simply *scan* ranges of consecutive nodes in the trie levels. We now explore the impact of these two advantages.

The pseudo code reported in Figure \[alg:select\] illustrates how triple patterns with one or two wildcard symbols are supported by our index. Given a sequence , function .($i$, $j$, $x$) finds the ID $x$ in the range $[i,j)$ and returns its absolute position in the sequence. If $x$ is not found in the range, a default position (e.g., $-1$) will be returned to signal the event and the number of matches will be 0 (for simplicity, in the pseudo code, we assume the to be valid, i.e., indexed by the data structure). Function .($i$) instead instantiates an iterator starting at $[i]$. We assume that accessing the pointers at position $i$ fetches a pair of adjacent values (, ), such that = $[i]$ and = $[i+1]$ with the value ( $-$ ) giving the number of children of the node at position $i$ in the previous level of the trie (line 3 and 9). Furthermore, the algorithm creates two iterators to scan ranges of the second and third levels of the trie, respectively. These iterators are then used to define a final iterator that combines the iterating capabilities of both objects (line 12).

Apart from the cost of the operation called for patterns with one wildcard symbol and the time needed to access the pointer sequences, the time spent per matched triple is $O(1)$, that is optimal. In the following, we discuss how the operation and the random can be efficiently supported directly over the compressed node sequences.

A key characteristic of the trie data structure is to conceptually replace runs of the same ID $x$ in a sequence with the pair ($x$, ), where the information indicates the run length and where the run is located in the sequence. This already produces significant space savings when triples share many repeated IDs, as it holds for large RDF datasets. Again, refer to Figure \[fig:trie\] for a basic graphical evidence of this fact. We note that the sequences of and on each trie level can be effectively compressed using a wealth of available techniques, developed for compactly represent (long) integer sequences with excellent search capabilities, e.g., the ones appearing in inverted indexes [@zobel2006inverted; @pibiri2018inverted]. A review and discussion of such techniques is out of scope for the contents of this paper: we point the interested reader to the more general survey by Zobel and Moffat [@zobel2006inverted] and the one by Pibiri and Venturini [@pibiri2018inverted] discussing the most recent developments.

Therefore, the problem we face now is the one of compactly representing the levels of each trie by achieving, at the same time, an efficient execution of algorithm that, besides the function, demands fast random to the pointer sequences (see Figure \[alg:select\]). Below we discuss some different options to achieve this goal, chosen as representative of the many available.

A first (obvious) option would be to minimize the number of bits needed to encode a single integer, taking $\lceil \log_2 \var{max} \rceil$ bits per value with being the maximum one in the sequence. The advantage of this technique, that we indicate as in the following, is simplicity and efficiency, given that a few bit-wise operations are needed to implement the random operation and, consequently, the (, , ) function that can be supported by binary searching the interval $[i,j)$.

Instead, an elegant integer encoder fulfilling the requirements is *Elias-Fano* () [@elias; @fano] that combines a fast, namely constant-time, random algorithm with compressed space close to the information theoretic minimum. Again, see [@pibiri2018inverted] for a detailed description of such encoding as well as of its *partitioned* variant  [@ottaviano2014partitioned]. We test this encoder as (one of the) representative of the best space/time trade-off in the literature. Not surprisingly, the adoption of this encoder to model the levels of a trie has been recently advocated in [@pibiri2017efficient] and shown to reduce the space of massive $n$-gram datasets by a factor of 2 over the most compact trie representation and to provide state-of-the-art time performance.

Other approaches focus on representing a sequence of $d$-gaps, i.e., differences between successive integers [@zobel2006inverted], with the requirement of computing a prefix-sum when decoding the d-gapped stream. A common way of speeding up the operations on the compressed sequence, is to divide the sequence into fixed-size blocks, e.g., 128 integers. As a meaningful representative of such technique, we use  [@thiel1972program] that achieves the highest decompression speed in the literature, especially when combined with the SIMD-ized decoding algorithm devised by Plaisance et al. [@maskedvb].

Table \[tab:compressors\] reports the performance of the mentioned techniques when applied to represent the node ID sequences of the tries of . In order to operate in a meaningful benchmarking setting for the algorithm, instead of accessing random positions in the sequences or resolving a in random intervals, we use a set of 5000 actual triples randomly extracted from the indexed dataset. Given a triple $(s,p,o)$ belonging to the trie , we report in the table the time required to the second level at the position of $p$ (pre-calculated); similarly, we measure the time needed for finding the position of $p$ among the children of $s$ (). The time reported for indicates the time spent per node, when decoding the level sequentially. The same hold for the third level of , as well as for the other tries  and . The details of the experimental setting are reported at the beginning of Section \[sec:experiments\].

By looking at the results reported in Table \[tab:compressors\] we can observe the following.

-   All the tested techniques require about the same space for representing the sequences of subjects and objects, with being the most space-efficient.

-   There is only a little difference between the space of and when representing the objects of (third level). The reason for this behavior is the *monotonicity* of the sequences required by the Elias-Fano encoder. In fact, while the sequences of pointers are monotone by construction and, thus, are immediately encodable, the same does not hold for node ID sequences where only sub-sequences of sibling nodes are ordered. Node ID sequences are thus formed by *sorted sub-sequences* with the last element of a sub-sequence being not necessarily smaller than the first one of the next one. In order to encode such sequences with a compressor like Elias-Fano we need to apply a simple transformation adding to the value of each node ID the value of the prefix-sum of the previously coded sub-sequence. This transformation makes Elias-Fano codes to be expensive whenever the prefix-sum is updated too frequently as it happens in the presence of many small ranges, because the universe of representation grows (very) quickly, thus enlarging the space of representation. As we will show later, most levels of the tries are indeed populated by such tiny ranges, meaning that each node has only few children on average.

-   is roughly $2\times$ smaller than the other options on the sequences of predicates.

-   The representation is, in general, the fastest for all operations, especially when performing random that requires $1.4 \div 2.6$ nanoseconds. However, it is the largest too.

-   The variant imposes a penalty of roughly $2\times$ over its un-partitioned counterpart when performing random , but results to be faster on average for the operation because it operates inside a partition that is much smaller than the whole sequence. As expected, codes spend more time for because of the (expensive) decompression of blocks that happens to be competitive only when decoding the sequences of predicates.

For the reasons discussed above, we adopt the following design choices. We use to represent all the sequences of node IDs, except for the last of the trie where we adopt the representation. The pointer sequences are represented using plain (not partitioned) given its superior random efficiency.

From now on, we refer to this solution as the index.

Lastly in this subsection, we discuss the space breakdowns reported in parentheses in Table \[tab:compressors\]. These values indicate the percentage of space out of the whole index required to encode with a given compressor the specific sequence of IDs (the space for pointers is excluded from the count).

As a general consideration, we observe that each permutation takes roughly 1/3 of the space of the whole index, with the trie being a little larger than the other two. For example, by considering the values for the encoder, we have that the levels of require 2.51% + 32.95% = 35.46% of the whole index, whereas the ones of 27.06%. Summing up all the values for , we get a total percentage of 91.05%, thus the space for the pointer sequences takes less than 9% of the whole index.

The levels of the index that contribute the most to the overall index space are: the third levels of and ; the second level of . Specifically, we observe that such levels take practically the *whole* space of the single tries which they belong to because the other two levels take just a small fraction of the space (e.g., between 5% and 7.5% for ). The first levels take almost no space because they comprise only the pointers. The second levels of and take little space for different reasons: for the former, because the number of bits needed to represent a predicate is small compared to the number of bits necessary to represent subjects and objects (see Table \[tab:datasets\]); for the latter, because the high associativity of predicates partitions the objects’ space into a few but very long sorted sequences that are highly compressible. For example, only 1.34 are needed for the objects to be represented in the second level of the trie . The former reason also causes the third level of to require a small space.

These considerations suggest that the efforts in trying to reduce the space of our RDF index should be mainly targeted to reduce the space for encoding level three of and and level two of . This will be the objective of the next subsection.

Cross compression {#subsec:remapping}
-----------------

The index layout that we have introduced represents the triples three times in different (cyclic) permutations in order to optimally solve all triple selection patterns. However, the current description does not take advantage of the fact that in this way the same set of triples is represented multiple times and that, consequently, the index has an abundance of redundant information. In this subsection we develop a novel compression framework that does not compress each trie independently but employs levels of the tries to compress levels of other tries, thus holistically *cross-compressing* the different permutations.

![Graphical representation of our cross-compression technique, in which an arrow $(\textsf{X})_i \rightarrow (\textsf{Y})_j$ indicates that level of trie $i$ is used to cross-compress the level of trie $j = (i + 2)$ mod $3$, for $i = 0, 1, 2$.[]{data-label="fig:remapping"}]({{imgs/remapping}})

The compression framework is graphically illustrated in Figure \[fig:remapping\]. In the picture, we depict the three different permutations and highlight that the levels enclosed in the squared boxes are used to cross-compress the (lower) levels enclosed by the shaded boxes as pointed to by the arrows. Cross-compression works by noting this crucial property: *the nodes belonging to a sub-tree rooted in the second level of trie $j$ are a subset of the nodes belonging to a sub-tree rooted in the first level of trie $i$, with* $j = (i + 2)$ mod $3$*, for $i = 0, 1, 2$.* The correctness of this property follows automatically by taking into account that the triples indexed by each permutation are the same. Therefore, the children of $x$ in the second level of trie $j$ can be re-written as the *positions* they take in the (larger, enclosing) set of children of $x$ in the first level of trie $i$. Re-writing the node IDs as positions relative to the set of children of a sub-tree yields a clear space optimization because the number of children of a given node is much smaller (on average) than the number of distinct subjects or objects (see also Table \[tab:datasets\] for the precise statistics).

We claim that the average number of children for the nodes in the first levels of the tries is the key statistic affecting the effectiveness of the described cross-compression technique because smaller numbers require a smaller number of bits to be represented. We report this statistic in Table \[tab:range\_stats\] for the dataset. The data reported in the table is self-explanatory: except for the first level of , the average number of children is *very* low, being actually less than 3 for , across the different permutations. As already mentioned, the high associativity of the predicates causes each predicate to have many children, i.e., several orders of magnitude more than the children of subjects and objects. We also show the maximum number of children, i.e., a maximum of $m$ indicates that there is a least one node that has $m$ children. While this value can be very distant from the average, for some levels like the second of and is actually similar, meaning that the selection patterns and have a robust worst-case guarantee.

Figure \[alg:map-unmap\] shows a compact pseudo code illustrating how a ID can be rewritten conditionally to its ID in the described cross-compression framework. Conversely, the function shows what actions are needed to recover the original ID before returning the result to the user. In particular, this latter function needs to be applied to the third component of *every* triple matched by a selection pattern, hence partially eroding the retrieval efficiency. Note that fast random access is needed by the function, thus it could be convenient to model $[1]$. with a representation (see also Table \[tab:compressors\] for benchmark numbers).

We have seen that the nodes in the third level of the trie can be cross-compressed using the sub-trees rooted in the first level of the trie , whose average number of children is actually less than 3 on real-world datasets. Therefore, what we should expect is to have the third level of mostly populated with values in $\{0,1,2\}$ that requires just two bits to be written instead of more than 20 bits to represent each subject. Therefore, we argue that a significant space saving can be achieved by applying this technique, introducing a slowdown for two (out of eight) selection patterns only, i.e., and that are solved on the trie . As already motivated, the second level of is represented with .

We also argue that cross-compressing the other two permutations, i.e., and , yields only modest advantages. Again, refer to Table \[tab:range\_stats\]. To cross-compress the third level of we use the children branching out from the predicates to the objects. But, as already noted, a predicate has many children, thus dwarfing the corresponding reduction in the average number of bits needed to represent a mapped ID. For the permutation , instead, we have to shrink the node ID of the predicates. But these are already encoded compactly, e.g., in less than 4.8 on average for (see Table \[tab:compressors\]). Thus, given that we can not expect great space savings in these two cases, we consider the cross-compressed index to be the one with cross-compression on the triples and that we indicate with in the following.

Eliminating a permutation {#subsec:twotries}
-------------------------

The low number of predicates exhibited by RDF data in combination to the corresponding very few children of the nodes in the second level of the trie , leads us to consider a different algorithm for the resolution of the query pattern , able to take advantage of such skewed distribution of the predicates. In fact, recall from Table \[tab:range\_stats\] that on the dataset, for a given (, ) pair, just 1.13 predicates are returned on average and 10 at most. Also recall from Section \[subsec:core\] that the pattern is solved by the algorithm in Figure \[alg:select\] by performing a operation followed by a on the trie.

The idea is to pattern match directly over the permutation with the algorithm illustrated in Figure \[alg:enumerate\]. For a given subject $s$ and object $o$, in short, we operate as follows. We consider the set of all the predicates that are children of $s$. For each predicate $p_i$ in the set, we determine if the object $o$ is a child of $p_i$ with the function: if it is, then ($s$, $p_i$, $o$) is a triple to return. We refer to such strategy as the algorithm, whose correctness is immediate.

As partially motivated, we argue that the efficiency of the outlined algorithm is due to several distinct facts.

-   The small number of predicates as children of a given subject implies that the loop in Figure \[alg:enumerate\] performs few iterations: while these children are few per se, e.g., *at most* 52 for , the iterations will be on average far less. For example, less than 6 iterations are needed on average for (see detailed statistics in Table \[tab:range\_stats\]).

-   For a given (subject, predicate) pair, we have a very limited number of children to be searched for $o$, thus making the function run *faster* by *short scans* rather than via binary search. On , an average of 2.32 children have to be scanned per pair.

-   Furthermore, the algorithm operates on the permutation whereas the algorithm on : but if we consider the rows for the encoder in Table \[tab:compressors\], we see that a operation issued on the second level of costs $1.6\times$ more the amount of nanoseconds spent on . Thus, avoiding percolating the trie produces further savings.

In the light of devising a competitive algorithm to pattern match on , we consider another index layout. Combining the design introduced in Section \[subsec:core\] with the present considerations, five of out the eight different selection patterns can be solved efficiently by the trie , i.e.: , , , and . In order to support other two selection patterns, we can either chose to: (1) materialize the permutation for *predicate-based* retrieval (query patterns and ); (2) materialize the permutation for *object-based* retrieval (query patterns and ). The choice of which permutation to maintain depends on the statistics of the selection patterns that have to be supported. We stress that the introduced algorithm allows us to actually *save the space* for a third permutation that, as we have already pointed out in Section \[subsec:core\], costs roughly 1/3 of the whole space of the index. We call this solution the index; with two concrete instantiations (predicate-based) and (object-based).

The only selection pattern that is not immediately supported is for (symmetrically, for ). However, we know that predicates are very associative, thus the list of subject nodes having a predicate parent is, on average, very long and highly compressible. Therefore, we can afford to maintain a two-level structure that, for every predicate $p$, maintains the list of all subjects that appear in triples having predicate $p$. Recall from our discussion concerning the space breakdowns in Section \[subsec:core\] that the similar structure costs just 1.34 for , thus should be only a little more costly given that the pairs are more in number than the pairs (see Table \[tab:datasets\]). Therefore, we proceed as follows.

1.  *Access the list $p \rightarrow [s_1,\ldots,s_n]$.*

2.  *For $i = 1,\ldots,n$, consider the pair $(s_i,p)$ and pattern match $s_i p ?$ against the permutation* *.*

Similarly for the index , if we consider a query pattern with specified object $o$, $|\textsf{P}|$ operations are needed to locate all the occurrences of $o$ in the second level of the trie .

1.  *For every predicate $p$, consider its children.*

2.  *Determine if $o$ is among them with the* *function. If yes, then return all triples* ($s, p, o$) *with $s$ being a child of the pair $(p,o)$.*

Again, the correctness of these two algorithms is immediate. In order to distinguish them from and , in the following analysis we refer to both approaches as .
