## New Compressed Indices for Multijoins on Graph Databases

Diego Arroyuelo 1,4 † , Fabrizio Barisione 2,4 † , Antonio Fari˜a n 3,5 † , Adri´n G´ omez-Brand´n a o 3,4* † , Gonzalo Navarro 2,4 †

1

Pontificia Universidad Cat´lica, Av. Vicu˜a Mackenna, Santiago, Chile. o n 2 Universidad de Chile, Beauchef, Santiago, Chile. 3 Universidade da Coru˜a, Campus de Elvi˜a, A Coru˜a, Spain. n n n 4 IMFD, Av. Vicu˜a Mackenna, Santiago, Chile. n 5 CITIC, Campus de Elvi˜a, A Coru˜a, Spain. n n

*Corresponding author(s). E-mail(s): adrian.gbrandon@udc.es; Contributing authors: diego.arroyuelo@uc.cl; fbarisio@dcc.uchile.cl; antonio.farina@udc.es; gnavarro@dcc.uchile.cl;

† These authors contributed equally to this work.

## Abstract

A recent surprising result in the implementation of worst-case-optimal (wco) multijoins in graph databases (specifically, basic graph patterns) is that they can be supported on graph representations that take even less space than a plain representation, and orders of magnitude less space than classical indices, while offering comparable performance. In this paper we uncover a wide set of new wco space-time tradeoffs: we (1) introduce new compact indices that handle multijoins in wco time, and (2) combine them with new query resolution strategies that offer better times in practice. As a result, we improve the average query times of current compact representations by a factor of up to 13 to produce the first 1000 results, and using twice their space, reduce their total average query time by a factor of 2. Our experiments suggest that there is more room for improvement in terms of generating better query plans for multijoins.

Keywords: Worst-case-optimal, multijoins, graph databases, compact data structures

## 1 Introduction

Natural joins are fundamental in the relational algebra, and generally the most costly operations. A bad implementation choice can lead to unaffordable query times, so they have been a concern since the beginnings of the relational model. Apart from efficient algorithms to join two tables (i.e., solve pair-wise joins), database management systems sought optimized strategies (e.g., [1]) to solve joins between several tables (i.e., multijoins), as differences between good and bad plans could be huge in terms of efficiency. A query plan for a multijoin was a binary expression tree where the leaves were the tables to join and the internal nodes were the pair-wise joins to perform.

After half a century of revolving around this pairwise-join-based strategy, it was found that it had no chance to be optimal [2], as it could generate intermediate results (at internal nodes of the expression tree) that were much larger than the final output. The concept of a worst-case optimal (wco) algorithm [2] was coined to define a multijoin algorithm taking time ˜ ( O Q ∗ ), where Q ∗ is the largest output size on some database instance with the same table sizes of the given one ( ˜ ( O Q ∗ ) allows multiplying Q ∗ by terms that do not depend, or depend only logarithmically, on the database size). Several wco join algorithms were proposed since then [3-8].

Leapfrog Triejoin (LTJ) [5] is probably the simplest and most popular wco algorithm. At a high level, it can be regarded as reducing the multijoin by one attribute at a time, instead of by one relation at a time as in the classical query plans. LTJ chooses a suitable order in which the joined attributes will be eliminated (which means finding all their possible values in the output and branching on the subset of the output matching each such value). To proceed efficiently, LTJ needs the rows of each relation stored in a trie (or digital tree) where the root-to-leaf attribute order is consistent with the chosen attribute elimination order. Even though LTJ is wco with any elimination order, it turns out that, just like with the traditional query plans, there can be large performance differences when choosing different orders [5, 9]. This means, first, that choosing a good order is essential and, second, that LTJ needs tries storing each relation in every possible order of its attributes , that is, d ! tries for a relation with d attributes.

This high space requirement shows up, in one form or another, in all the existing wco algorithms, and has become an obstacle to their full adoption in database systems. Wco algorithms are of particular interest in graph databases , which can be regarded as labeled graphs, or as a single relational table with three attributes: source node, label, and target node. Standard query languages for graph databases like SPARQL [10] feature most prominently basic graph patterns (BGPs) , which essentially are a combination of multijoins and simple selections. The concept of wco algorithms, as well as LTJ, can be translated into solving BGPs on graph databases [9]. This is very relevant because typical BGPs correspond to large and complex multijoins [7, 9, 11, 12], where non-wco algorithms can be orders of magnitude slower than wco ones [11]. Still, LTJ needs 3! = 6 copies of the database in the form of tries, which even for this low arity is sufficiently space-demanding to discourage its full implementation.

The implementation of various wco indices seems to confirm that large space usage will be the price for featuring wco query times. For example, a wco version of Jena [9] doubles the space of the original non-wco version. Efficient wco implementations like

EmptyHeaded [11] and MillenniumDB [13] use many times the space required to store the raw data. Surprisingly, recent research debunks this impression. In particular, the ring [14, 15] is a novel compact index that represents graph databases (the data and the index structures) within less space than that used by the raw data in plain form, while still supporting BGPs within competitive times, often even lower than indices that are orders of magnitude larger.

## 1.1 Our contribution

The unexpected result achieved by small indexes like the ring has opened numerous opportunities for new space-time tradeoffs in index data structures for wco multijoins on graph databases. The ring was aimed at minimum space usage, to demonstrate that competitive query times could be achieved using only as much space as the raw data, and even less. Since this space is much lower than that of traditional indices, there is sufficient slack to introduce larger data structures that, still using a fraction of the space of those traditional indices, are much faster than the ring . Additionally, despite occupying minimal space, the data structures supporting the ring enable efficient computation of information-which would otherwise need to be explicitly stored by conventional indices-that helps compute efficient attribute elimination orders for LTJ [15]. Motivated by this, we contribute with new compact indices that support solving BGPs in wco time, and their combination with new query resolution techniques, thereby uncovering a wide set of new space-time tradeoffs in wco indices for solving BGPs. Concretely:

- 1. We design an alternative to the ring that, using twice its space, is four times faster in the median and twice as fast on the average. This new index, which we call the rdfcsa , builds on an existing compact index representation that only supported single joins [16], so that now it supports full BGPs in wco time.
- 2. We combine the ring and the rdfcsa with an adaptive variable elimination order, which recomputes the best elimination order as the join proceeds and more information is available. We use new estimators for the next variable to bind that are more accurate and can be computed efficiently on our compact indices. In our experiments, the combination obtains the first thousand results 4-13 times faster, on average, than the traditional global-order strategy. We show that our adaptive strategies outperform, in many cases, the best possible global-order strategy.

## 2 Preliminary concepts

## 2.1 Graph joins

## 2.1.1 Edge-Labeled Graphs

Let U be a totally ordered, countably infinite set of constants , which we call the universe . In the RDF model [17], an edge-labeled graph is a finite set of triples G ⊆ U 3 , where each triple ( s, p, o ) ∈ U 3 encodes the directed edge s p - → o from vertex s to vertex o , with edge label p . We call dom( G ) = { s, p, o | ( s, p, o ) ∈ G } the subset of U used as constants in G . For any element u ∈ U , let u + 1 denote the successor of u

in the total order U . We also denote U = maxdom( G ). For simplicity, we will assume that the constants in U have been mapped to integers in the range [1 . . U ], and will even assume U = [1 . . U ].

## 2.1.2 Basic Graph Patterns (BGPs)

A graph G is often queried to find patterns of interest, that is, subgraphs of G that are homomorphic to a given pattern Q . Unlike the graph G , which is formed only by constants in U , a pattern Q can contain also variables , formally defined as follows. Let V denote an infinite set of variables, such that U ∩ V = ∅ . Then, a triple pattern t is a tuple ( s, p, o ) ∈ ( U ∪ V ) 3 , and a basic graph pattern is a finite set Q ⊆ U ∪ V ( ) 3 of triple patterns. Each triple pattern in Q is an atomic query over the graph, equivalent to equality-based selections on a single ternary relation. Thus, a basic graph pattern (BGP) corresponds to a full conjunctive query (i.e., a join query plus simple selections) over the relational representation of the graph.

Let vars( Q ) denote the set of variables used in pattern Q . The evaluation of Q over a graph G is then defined to be the set of mappings Q G ( ) := { µ : vars( Q ) → dom( G ) | µ Q ( ) ⊆ G } , called solutions , where µ Q ( ) denotes the image of Q under µ , that is, the result of replacing each variable x ∈ vars( Q ) in Q by µ x ( ).

## 2.2 Worst-case optimal joins

## 2.2.1 The AGM bound

A well-established bound to analyze join algorithms is the AGM bound , introduced by Atserias et al. [2], which sets a limit on the maximum output size for a natural join query. Let Q denote such a query and D a relational database instance. The AGM bound of Q over D , denoted Q ∗ , is the maximum number of tuples generated by evaluating Q over any database instance D ′ containing a table R ′ for each table R of D , with the same attributes and | R ′ | ≤ | R | tuples. Though BGPs extend natural joins with self joins, constants in U , and the multiple use of a variable in a triple pattern, the AGM bound can still be applied to them by regarding each triple pattern as a relation formed by the triples that match its constants [9].

Given a join query (or BGP) Q and a database instance D , a join algorithm enumerates Q D ( ), the solutions for Q over D . A join algorithm is worst-case optimal (wco) if it has a running time in ˜ ( O Q ∗ ), which is O Q ( ∗ ) multiplied by terms that do not depend, or depend only polylogarithmically, on | D | . Atserias et al. [2] proved that there are queries Q for which no plan involving only pair-wise joins can be wco.

This paper focuses on wco algorithms, precisely on the one described next, which is the one most frequently implemented.

## 2.2.2 Leapfrog TrieJoin (LTJ)

We describe the Leapfrog Triejoin algorithm [5], originally designed for natural joins in relational databases, as it is adapted for BGP matching on labeled graphs [9].

Let Q = { t 1 , . . . , t q } be a BGP and vars( Q ) = { x , . . . , x 1 v } its set of variables. LTJ uses a variable elimination approach, which extends the concept of attribute

VERSION CORREGIDA - v2

Fig. 1 : A labeled graph G ′ with its string to integer mapping and tries for orders pso and pos .

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-3d163f3a-06fc-4d63-b275-0e332527e1ef.jpg)

elimination. The algorithm carries out v = vars( | Q ) | iterations, handling one particular variable of vars( Q ) at a time. This involves defining a total order ⟨ x i 1 , . . . , x i v ⟩ of vars( Q ), which we call a VEO for variable elimination order .

Each triple pattern t i is interpreted as a relation that will be joined, and associated with a suitable trie τ i . The root-to-leaf path in τ i must start with the constants that appear in t i , and the rest of its levels must visit the variables of t i in an order that is consistent with the VEO chosen for Q (this is why we need the 3! = 6 tries). Fig. 1 shows an example graph and the corresponding mapping of the constants in U to integers. We also show two tries representing the graph triples using the orders pso (i.e., predicate, subject, object) and pos . For example, we must use the trie pso to handle a triple pattern ( x, 8 , y ) if the VEO is ⟨ x, y ⟩ , and the trie pos if the VEO is ⟨ y, x ⟩ . If Q has a second triple pattern ( y, 7 , x ), then we need both tries no matter the VEO we use.

The algorithm starts at the root of every τ i and descends by the children that correspond to the constants in t i . We then proceed to the variable elimination phase. Let Q j ⊆ Q be the triple patterns that contain variable x i j . Starting with the first variable, x i 1 , LTJ finds each c ∈ dom( G ) such that for every t ∈ Q 1 , if x i 1 is replaced by c in t , the evaluation of the modified triple pattern t over G is non-empty (i.e., there may be answers to Q where x i 1 is equal to c ). If the trie τ of t is consistent with the VEO, then the children of its current node contain precisely those suitable values c for variable x i 1 .

During the execution, we keep a mapping µ with the solutions of Q . As we find each constant c suitable for x i 1 , we bind x 1 to c , that is, we set µ = { ( x 1 := c ) } and branch on this value c . In this branch, we go down by c in all the virtual tries τ such that t ∈ Q 1 . We now repeat the same process with Q 2 , finding suitable constants d for x i 2 and increasing the mapping to µ = { ( x 1 := c , ) ( x 2 := d ) } , and so on. Once we have bound all variables in this way, µ is a solution for Q (this happens many times because we branch on every binding to c , d , etc.). When it has considered all the bindings c

VERSION ORIGI

for some variable x i j , LTJ backtracks and continues with the next binding for Q j -1 . When this process finishes, the algorithm has reported all the solutions for Q .

Operationally, the values c , d , etc. are found by intersecting the children of the current nodes in all the tries τ i for t i ∈ Q j . LTJ carries out the intersection using the primitive leap ( τ , c i ), which finds the next smallest constant c i ≥ c within the children of the current node in trie τ i ; if there is no such value c i , leap ( τ , c i ) returns a special value ⊥ .

## 2.3 Variable Elimination Orders (VEOs)

Veldhuizen [5] showed that if leap () runs in polylogarithmic time, then LTJ is wco no matter the VEO chosen, as long as the tries used have the right attribute order. In practice, however, the VEO plays a fundamental role in the efficiency of the algorithm [5, 9]. A VEO yielding a large number of intermediate solutions that are later discarded during LTJ execution, will be worse than one that avoids exploring many such alternatives. One would prefer, in general, to first eliminate selective variables (i.e., the ones that yield a smaller candidate set when intersecting).

A heuristic to generate a good VEO in practice [9, 13, 14] computes, for each variable x j , its minimum weight

$$w _ { j } = \min \{ w _ { i j } \ | \ x _ { j } \text{ appears in triple } t _ { i } \},$$

where w ij is the weight of x j in t i . The VEO sorts the variables in increasing order of w j , with a couple of restrictions: (i) each new variable should share some triple pattern with a previous variable, if possible; (ii) variables appearing only once in Q (called lonely ) must be processed at the end.

To compute w ij , we (temporarily) choose a trie τ j where x j appears right after the constants of t i , and descend in τ j by the constants. The number of children of the trie node v we have reached is the desired weight w ij . This is the size of the list in τ i to intersect when eliminating x j .

In this paper we explore the use of adaptive VEOs, which are defined progressively as the query processing advances, and may differ for each different binding of the preceding variables. ADOPT [18] is the first system combining LTJ with adaptive VEOs. The next variables to bind are chosen using reinforcement learning, by partially exploring possibly upcoming orders, and balancing the cost of exploring with that of the obtained improvements. Our adaptive VEOs will be computed, instead, simply as a variant of the formula presented above for global VEOs [9].

We will also explore more refined estimations of w j in Eq. (1), beyond the use of simply the minimum of the set sizes w ij to estimate the size of their intersection.

## 3 The Ring: Wco joins in compact space

The ring [14, 15] is an index that supports the 6 orders needed by LTJ using a single data structure that uses space close to the raw data representation (and possibly less), while supporting the leap () operation on the tries in logarithmic time.

Fig. 2 : Example of the wavelet tree for the sequence { 5 3 1 4 6 6 6 6 6 6 6 6 6 , , , , , , , , , , , , } . The ranges at the left depict the alphabet range of each bitmap. The arrows show the procedure to obtain the 4th value of the sequence.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-85ff28de-98a7-448e-b36e-4e401a0dab20.jpg)

## 3.1 Bitvectors and wavelet trees

We start surveying the compact data structures used by the ring . First, a bitvector B [1 . . n ] is an array of n bits supporting the following queries:

- · access ( B,i ): the bit stored at B i [ ].
- · select b ( B,j ) : the position of the j th occurrence of bit b ∈ { 0 1 , } in B .
- · rank b ( B,i ): the number of bits b ∈ { 0 1 , } in B [1 . . i ].
- · selectnext b ( B,j ) : the position of the leftmost occurrence of b in B j . . n [ ].

These operations can be supported in O (1) time using n + ( ) bits of space [19, 20] o n or, alternatively, nH 0 ( B ) + o n ( ) bits [21], where H 0 ( B ) ≤ 1 denotes the zero-order entropy of B .

The wavelet tree [22, 23] is a binary tree that represents a string S [1 . . n ] of symbols from an alphabet Σ = { 1 , . . . , σ } . Each node v represents a range [ a, b ] of the alphabet, a, b ∈ Σ, with the root representing the whole alphabet [1 , σ ] and each leaf representing a single symbol a , or range [ a, a ]. The range [ a, b ] of internal nodes is divided into two, [ a, ⌊ ( a + ) 2 ] and [ ( b / ⌋ ⌊ a + ) 2 b / ⌋ +1 , b ], which are those of their left and right children.

Each internal node v representing a range [ a, b ] is associated with the subsequence S a,b of S formed by the symbols in [ a, b ] ( S a,b = S if the node is the root). Instead of storing S a,b , the node stores a bitvector B a,b [1 . . | S a,b | ], where B a,b [ i ] = 0 iff S a,b [ i ] ∈ [1 , ⌊ ( a + ) 2 ] (i.e., belongs to the first half of the alphabet range); else b / ⌋ B a,b [ i ] = . 1

Note that the bitvector lengths at any level of the tree sum up to n and we need to support binary rank / select operations on them. Therefore, the wavelet tree represents S using n lg σ + ( o n lg σ ) bits (a plain representation uses almost the same, n lg σ bits), and even within zero-order entropy, nH 0 ( S ) ≤ n lg σ bits. For large alphabets (as occurs in this paper), the additional space for the O σ ( ) tree pointers are eliminated in a pointerless version called wavelet matrix [24].

The wavelet trees support the functionality of access , rank , and select on general alphabets in time O (lg σ ) by traversing the tree from the root to a leaf. For instance, to access S i [ ] we start at position i in the bitmap of the root B 1 ,σ . Depending on

B 1 ,σ [ i ] we know that S i [ ] is represented in the left (0) or right child (1). Hence, we continue by the left (resp. right) child at position rank 0 ( B 1 ,σ , i ) (resp., rank 1 ( B 1 ,σ , i )) when B 1 ,σ [ i ] = 0 (resp., B 1 ,σ [ i ] = 1). Those steps are repeated recursively within the corresponding bitmaps up to reaching a leaf. The symbol of that leaf is the solution to S i [ ]. Fig. 2 shows an example of access operation at position 4. Operation rank is solved analogously, and select involves a further bottom-up traversal using select on the bitmaps.

In addition, the wavelet trees support the following advanced operations that are useful for the ring [25, 26]:

- · range next value ( S, r s , r e , c ): for c ∈ Σ, finds in time O (lg σ ) the smallest symbol c ′ ≥ c that occurs within S r [ s . . r e ]. This is used to simulate the primitive leap () of LTJ on a compact representation of G .
- · range count ( S, x s , x e , [ r , r s e ])): counts how many symbols in S r [ s . . r e ] belong to the range [ x , x s e ] in O (lg σ ) time. This will be used to estimate the costs of different VEOs on compressed representations of G .
- · range intersect ( S 1 ⟨ [ l 1 , r 1 ] , . . . , S k [ l k , r k ] ⟩ ): computes the intersection of the ranges S 1 [ l 1 . . r 1 ] , . . . , S k [ l k . . r k ], reporting the symbols that occur in all the k ranges. It is assumed that all the sequences S i share the same alphabet. This intersection is typically faster than the one performed via leap ().

## 3.2 Indexing the data

To represent a labeled graph G , let us define the table T spo [1 . . n ][1 . . 3] storing the n graph triples sorted according to the spo order. Column 1 of T spo corresponds to s , column 2 to p , and column 3 to o . We denote C o the last column of T spo . Indeed, column C o reads in left-to-right order the last level (i.e., the one corresponding to o ) of the trie for spo . Next, the process moves column C o to the front in T spo , making it the first column. The table is then sorted to obtain table T osp , which conceptually represents the trie for the order osp . Let C p denote the last column of this table. Finally, column C p is moved to the front of T osp and the table is sorted again, obtaining table T pos and column C s . See Fig. 3.

The ring index is then formed by the sequences C ∗ , which are stored using wavelet trees (Section 3.1), with a total space requirement of 3 n lg U + ( o n lg U ) bits. We also build arrays A j , for each C j with j ∈ { s p o , , } , defined as A k j [ ] = |{ i ∈ [1 . . n , ] C i &lt; j [ ] k }| , for k = 1 , . . . , U +1. These arrays store the cumulative number of occurrences of the symbols of U in C j . This adds O U ( lg n ) extra bits, which are o n ( lg U ) if U ∈ o n ( ). In practice, these arrays are represented using bitvectors (Section 3.1), with a total space usage of 3( n + U ) + o n ( + U ) bits. The total space is then close to the 3 n lg U bits needed to represent G in plain form, and it can be even less if we use compressed wavelet trees to represent the columns.

Fig. 3 : The ring representation of the graph of Fig. 1. The horizontal lines mark the values of A s , A o , A p , left to right.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-ce53b21c-b918-4178-a55a-6586adf8423a.jpg)

## 3.3 Moving between tables

We can move from a table to the next one using C j and A j , for j ∈ { s p o , , } , using the function F j : [1 . . n ] → [1 . . n ], defined as follows:

$$F _ { j } ( i ) \ \coloneqq \ A _ { j } [ c ] + \text{rank} _ { c } ( C _ { j }, i ),$$

where c = C i j [ ]. Function F o maps a position in table T spo , using A o and C o , to the corresponding one in T osp . In Fig. 3, the straight dashed line maps from C o [7] = 3 to the position of that 3 in T osp , with F o [7] = A o [3] + rank 3 ( C , o 7) = 6 + 2 = 8. Similarly, F p maps from T osp to T pos , and F s maps from T pos back to T spo . The function takes O (lg U ) time. We can also move in the opposite direction, with the same time complexity, by computing the inverse function of F j from Eq. (2): let c satisfy A c &lt; j [ ] i ′ ≤ A c j [ +1], then

$$F _ { j } ^ { - 1 } ( i ^ { \prime } ) \coloneqq \text{select} _ { c } ( C _ { j }, i ^ { \prime } - A _ { j } [ c ] ). \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

Every node v in the trie of spo corresponds to a range of rows in T spo [ s . . e ] (i.e., a range in C o ): if v is the root, the range is C o [ s . . e ] = [1 . . n ]. If v is in the first level and corresponds to the subject s = x , the range C o [ s . . e ] is that of all triples starting with x . If v is in the second level and corresponds to ( s p , ) = ( x, y ), then C o [ s . . e ] corresponds to the triples starting with xy . A leaf trie node denoting the triple ( s p o , , ) = ( x, y, z ) corresponds to a single position in T spo containing xyz (i.e., a cell in C o ). The same holds, analogously, for tables T osp (column C p ) and T pos (column C s ). The other three tries are also implicitly represented by the tables. Consider the trie for pso . A first-level node for p = x corresponds to a range of rows in T pos (i.e., in C s ), a second-level node representing ( p s , ) = ( x, y ) corresponds to a range of rows in T spo (i.e., in C o ), and so on.

Along the search, each triple pattern will have a bound subset of attributes { s p o , , } , which always matches a prefix X of either spo , osp , or pos , the three tries

we represent via columns C o , C p , and C s . As explained, every concrete value for a prefix X corresponds to a range in some column. As we progress, the set X expands and we may have to switch from one column to another. For example, given the range C o [ s . . e ] (i.e., T spo [ s . . e ]) of the triples sharing a prefix X of spo , we obtain the range C p [ s . . e ′ ′ ] (i.e., T osp [ s . . e ′ ′ ]) of the triples sharing prefix cX of osp with

$$s ^ { \prime } & \, \coloneqq \, A _ { o } [ c ] + \text{rank} _ { c } ( C _ { o }, s - 1 ) + 1, \\ e ^ { \prime } & \, \coloneqq \, A _ { o } [ c ] + \text{rank} _ { c } ( C _ { o }, e ).$$

This is called a backward step . Fig. 3 shows how we descend from the first-level node 8 in T pos (represented by C s [5 . . 9]) to its child with value 6 (represented by C o [5 . . 9]), and from there to its child with value 3 (represented by C p [8 . . 8]). An analogous forward step extends X to Xc , in this case restricting the range C o [ s . . e ] to a smaller range C o [ s . . e ′ ′ ] in the same column; see the original article [14, 15] for details.

## 3.4 Constants in triple patterns

When LTJ starts, we find a range in some suitable column C ∗ for the constants of each triple pattern t i . We choose a table T ∗ ( T spo , T osp , or T pos ) whose attribute order is prefixed by the constant attributes in t i , and find the range corresponding to the constant prefix X in the column that represents T ∗ . For example, if only the attribute o is the constant, we start from T spo [1 . . n ] and apply Eq. (4) to end with some T osp [ s . . e ]; if p and s are the constants, we start from T osp [1 . . n ] and apply (the analogous of) Eq. (4) twice to end with some T spo [ s . . e ]. The total initialization time is O (lg U ) per triple pattern.

## 3.5 Supporting leaps

The remaining piece to support LTJ is function leap ( t , c ′ i ) (Section 2.2.2), where t ′ i is either a triple pattern t i from Q , or one of its progressively bound versions µ t ( i ). This finds the smallest child of the current node of t ′ i with value c x ≥ c . In the context of the ring , this is done differently depending on whether or not the variable appears to the left of the current prefix matched. If it does, for example we are binding o and our range is T spo [ s . . e ], then we use range next value ( T spo , s, e, c ) (Section 3.1) to find the appropriate value of c x , and if we decide to assign that value to o we use Eq. (4). A more difficult case arises when the desired variable is not to the left, as if binding p in T spo [ s . . e ]. This only happens when we have bound just one position so far, so we start from the range T pos [ A c p [ ] + 1 . . n ], rework Eq. (4) for the current value of s , and finally use Eq. (3) to obtain the desired value c x . In all cases, leap () takes O (lg U ) time and the ring solves queries in wco time O Q ( ∗ lg U ).

## 4 RDFCSA: LTJ on a compressed suffix array

We now present a new data structure, which roughly doubles the space of the ring in exchange for being potentially faster. The rdfcsa [16] was designed as a compact representation for labeled graphs that can be queried by single triple patterns and

binary joins. It predates the ring and shares with it the model of viewing the graph triples as cyclic strings of length 3 (in spo order). This set of strings is indexed and compactly represented with a compressed suffix array (CSA, see next). The CSA on the cyclic strings suffices to solve the original rdfcsa queries, but in order to support the LTJ algorithm, the rdfcsa lacks bidirectionality, that is, unlike the ring , it cannot support leap () on variables to the left and to the right of the already bound positions.

We now extend the rdfcsa to support LTJ by storing two CSAs, one for the spo order, and another for the ops order, and adding them the support for leap (), in one direction. We expect this implementation to be faster than that of the ring (Section 3.5) because the CSA is in practice more efficient than the wavelet tree for this problem, even if both algorithms take logarithmic time.

## 4.1 Compressed Suffix Array

Given a string S [1 . . n ] of symbols drawn from an alphabet Σ = { 1 , . . . , σ } (except the special symbol S n [ ] = $, which is lexicographically smaller than all symbols in Σ), the suffix array A of S [27] lists all suffix indices [1 . . n ] of S in increasing lexicographic order; that is, S A i . . n [ [ ] ] &lt; S A i [ [ + 1] . . n ] for all i ∈ [1 . . n -1] . For example, let S = abracadabra $, then A = ⟨ 12 11 8 1 4 6 9 2 5 7 10 3 . Note that all the , , , , , , , , , , , ⟩ occurrences of any given substring pattern P [1 . . m ] are pointed from a contiguous range A r [ s . . r e ] (because they are prefixes of the suffixes S A i . . n , i [ [ ] ] ∈ A r [ s . . r e ]).

The compressed suffix array (CSA) [28] is a compact representation of the suffix array that replaces both S and A . It uses a permutation Ψ[1 . . n ] such that Ψ[ ] = i j if A j [ ] = A i [ ] + 1 (or A j [ ] = 1 if A i [ ] = n ). Therefore, given a position p = A i [ ] in S , j = Ψ[ ] gives the index in i A such that A j [ ] = p + 1, the next position in S . For the example above we have Ψ[1 . . n ] = 4 1 7 8 9 10 11 12 6 3 2 5 . Note that ⟨ , , , , , , , , , , , ⟩ S A [ [7] . . 12] = bra $, Ψ[7] = 3, and so S A [ [3] . . 12] = ra $. The CSA also includes a bitvector D [1 . . n ] that sets D i [ ] = 1 to mark the positions i in A where the first symbol of the suffix pointed to from A i [ ] changes, that is, D i [ ] = 1 iff i = 1 or S A i [ [ -1]] &lt; S A i [ [ ]]. In our example, D = ⟨ 1 1 0 0 0 0 1 0 1 1 1 0 , , , , , , , , , , , ⟩ . The symbol c = S x [ ], pointed from A i [ ] = x , can be obtained as c = rank 1 ( D,i ). Further, S x [ +1] = rank 1 ( D, Ψ[ ]), i S x [ +2] = rank 1 ( D, Ψ[Ψ[ ]]), and in general i S x [ + ] = k rank 1 ( D, Ψ [ ]). k i

Regarding space, Ψ is composed of at most σ increasing sequences, which can be compressed by encoding differences and applying run-length encoding for runs of +1 differences. The required space is nH k ( S ) + O n ( lg lg σ ) bits for any k ≤ α lg σ n and constant α &lt; 1 [29], where H k ( S ) ≤ lg σ is the k -th order entropy of S . Bitvector D adds just n + ( ) bits. o n

## 4.2 Indexing the data

The rdfcsa requires a particular mapping from dom( G ) to integers. Different alphabets [1 . . n s ], [1 . . n p ], and [1 . . n o ] must be considered, respectively, for subjects, predicates, and objects. From them, the first n so symbols in the alphabets of subjects and objects are constants that could occur both as subjects and objects in a triple. It then holds | U | = n p + n s + n o -n so .

Fig. 4 : Structures involved in the construction of rdfcsa spo (i.e., D and Ψ) for the graph in Fig. 1.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-94f78872-65db-44b8-8924-ba4fb478d82c.jpg)

Considering a sequence of n triples sorted in spo order, the rdfcsa creates a unique sequence of integers T [1 . . 3 n ] where, for each triple ( s, p, o ) ∈ G , the string ⟨ s, p, o ′ ′ ′ ⟩ = ⟨ s + gap , p s + gap , o p + gap o ⟩ is appended to T . The offsets ( gap , gap s p , gap o ) = (0 , n s , n s + n p ) enforce disjoint identifiers for subjects, predicates, and objects, and ensure s ′ &lt; p ′ &lt; o ′ . Then, a CSA is built on T . Because of the offsets, there are three regions in the suffix array A (and D ), A [1 . . n ], A n [ +1 . . 2 n ], A [2 n +1 . . 3 n ], with entries pointing respectively to the subjects, predicates, and objects in T . Consequently, Ψ[1 . . n ] contains only values within [ n + 1 2 , n ], whereas the values in Ψ[ n + 1 . . 2 n ] and Ψ[2 n +1 . . 3 n ] are within [2 n +1 3 , n ] and [1 , n ], respectively. Finally, Ψ is modified to make it cycle on the triples, that is, we enforce Ψ[Ψ[Ψ[ ]]] = i i . This is easily done by decrementing the values in Ψ[2 n + 1 . . 3 n ], except that Ψ[ ] = 1 is converted to i Ψ[ ] = i n . To reduce space, Ψ is represented as the sequence Ψ[ ] i -Ψ[ i -1], using Huffman and run-length encoding on those gaps. Access in time O t ( Ψ ) to any Ψ[ ] value is i supported by sampling values Ψ[1 + k · t Ψ ] , k ≥ 0, which requires O (( n/t Ψ ) lg n ) additional bits on top of the compressed sequence (we will asume t Ψ ∈ O (1)). Bitvector D takes 3 n + ( ) further bits. Fig. 4 shows an example. o n

Analogously, we create a second rdfcsa considering triples sorted in ops order, and with offsets ( gap , gap s p , gap o ) = ( n o + n , n p o , 0). We refer to our two rdfcsa structures as rdfcsa spo and rdfcsa ops . In either of them, the triple content pointed at position i is retrieved in O (1) time by extracting rank 1 ( D,i ), rank 1 ( D, Ψ[ ]), and i rank 1 ( D, Ψ[Ψ[ ]])), i permuting them to order spo , and subtracting the corresponding gap values. We now show how we carry out the critical processes of LTJ with these structures.

## 4.3 Constants in triple patterns

We use the text searching capabilities of the rdfcsa to find a suffix array interval corresponding to all the triples that match the constants of a given triple pattern. The subsequent variable intersection process then starts from those intervals, which correspond to trie nodes in LTJ, as with the ring . Recall that, before finding any constant in the rdfcsa , it must be mapped by adding the corresponding gap . We use two operations:

- · [ l, r ] := range ( c ). For a given constant c we obtain the suffix array range A l, r [ ] of the (cyclic) triples starting with c , with l ← select 1 ( D,c ) and r ← select 1 ( D,c + 1) -1. This takes constant time. Note that, since c can be a subject, a predicate, or an object, and those identifiers have disjoint suffix array areas in the rdfcsa , this operation lets us select all the triples with a given subject, a given predicate, or a given object.
- · [ l, r ] := down ( l c , r c , d ). Given a suffix array range [ l c , r c ] ⊆ range ( c ), so the triples in A l , r [ c c ] start with constant c , this operation finds the subrange [ l, r ] ⊆ [ l c , r c ] of those triples where the c is followed by constant d . This is equivalent to stating that ∀ i ∈ [ l, r ] , Ψ[ ] i ∈ range ( d ). Since Ψ is increasing inside range ( c ), we can binary search for the first (last) position l ( r ) in [ l c , r c ] such that Ψ[ ] (Ψ[ l r ]) falls into range ( d ), in O (lg n ) time.

If a triple pattern t has no constants, its range is [1 . . 3 n ] in both rdfcsa spo and rdfcsa ops . If it has a single constant c , then its range in both is range ( c ) (the mapping of c using gap and the resulting range differs in both rdfcsa s). Which rdfcsa will be used depends on whether the next variable to eliminate is to the left or to the right of c . Therefore, some triple patterns will have a range in rdfcsa spo and others in rdfcsa ops .

If t has two constants, we can use either rdfcsa because the next variable to eliminate will be both to the left and to the right of the bound positions. Say we choose rdfcsa spo . Let cd be the two consecutive constants in spo order (i.e., sp = cd , po = cd , or os = cd ). We thus compute [ l c , r c ] := range ( c ) and then the desired range is [ l d , r d ] := down ( l c , r c , d ).

## 4.4 Supporting leaps

To support the operation leap () we define new primitives:

- · l ′ := findTarget Ψ ( l, r, t l , t r ). Given a range [ l . . r ] where Ψ is increasing, it returns the smallest l ′ ∈ [ l . . r ] such that Ψ[ l ′ ] ∈ [ t l . . t r ], and 0 if there is none. It proceeds as for down , yet it needs only one binary search in [ l, r ].
- · L := limitV ( v ). It returns the highest offset in D for any constant of the same type as variable v . For example, if v is a subject this is n in rdfcsa spo and 3 n in rdfcsa ops .
- · l ′ := findTarget ΨΨ ( l, r, t l , t r ). Given a range [ l . . r ] where Ψ is increasing, it returns the smallest l ′ ∈ [ l . . r ] such that Ψ[Ψ[ l ′ ]] ∈ [ t l . . t r ], or zero if there is none.

Recall that leap ( t , c ′ i ) returns the first constant c x ≥ c where a given variable x has occurrences in t ′ i , where t ′ i is either a triple pattern t i from Q , or one of its progressively bound versions µ t ( i ). The way we solve leap () depends on where the constant(s) and the variable x appear in t ′ i .

If there are no constants in t ′ i , the answer is simply c x := c , because our mapping makes all the symbols appear in T .

̸

If there is only one constant d in t ′ i , then we have a range [ l, r ] for t ′ i in both rdfcsa spo and rdfcsa ops . If x follows d in spo order, we use rdfcsa spo , otherwise we use rdfcsa ops . We first compute l ′ := findTarget Ψ ( l, r, l c , limitV ( x )) where l c = select 1 ( D,c ). Then, if l ′ = 0 we return c x := rank 1 ( D, Ψ[ l ′ ]), otherwise we return c x := ⊥ .

̸

Finally, if t ′ i contains two constants d and d ′ , they have a range [ l, r ] for dd ′ or d d ′ in either rdfcsa spo or rdfcsa ops , so we complete the search in the corresponding structure. In this case, we first compute l ′ := findTarget ΨΨ ( l, r, l c , limitV ( x )), where l c = select 1 ( D,c ). Then, if l ′ = 0 we return c x := rank 1 ( D, Ψ[Ψ[ l ′ ]]), and c x := ⊥ otherwise.

As an example, recall that if we have a triple pattern ( x, y, z ) with no constants, the initial range in rdfcsa is R := [1 , 3 n ]. If we bind y := win (i.e., the 3rd predicate, which is mapped to id 8 = 3+ gap p ), we update R := range ( 8 ) = [23 , 25] in rdfcsa spo (and also in rdfcsa ops ). Now, since Wheeler is the 4th object and maps into id 12 = gap o +4, if we call leap (( x, 8 , z ) , 12 ), since Wheeler follows win in spo order, we must use rdfcsa spo . We first compute l ′ := findTarget Ψ (23 26 , , select 1 ( D, 12 ) , 39) = 26, and then solve leap (( x, 8 , z ) , 12 ) = rank 1 ( D, Ψ[26]) = rank 1 ( D, 39) = 13 . Therefore, leap () returns object 5 = 13 -gap o which corresponds to Strutt , that is, the first object after Wheeler reached from the current range R .

## 5 URing: A unidirectional Ring

Bidirectionality is the key to using just one ring to index the 3! = 6 orders required by LTJ. The rdfcsa , instead, requires two copies of the index, thereby roughly doubling the space. We now explore the fact that the wavelet tree representation of the ring columns C ∗ supports an intersection algorithm ( range intersect , Section 3.1) that is likely faster than the one implemented in LTJ, which is based on the primitive leap ().

When we eliminate a new variable x , every triple pattern t i where it appears is represented by a range in some column, C ∗ [ l i . . r i ]. Assume x appears to the left of the positions already bound. The desired constants c x for x are the values that appear in all those ranges C ∗ [ l i , . . r i ]. We find them by running range intersect on all those ranges in order to obtain, one by one, the desired values c x (the algorithm runs even if the ranges are in different sequences C ∗ ). We then add each such binding ( x := c x ) to the mapping µ and recurse on that branch.

The problem with using that intersection algorithm is that it works only if the variable to eliminate is to the left of the current ranges, and therefore, analogously to the rdfcsa , we have a unidirectional index. Just as for rdfcsa , we must then have two indices, ring spo and ring ops to ensure that we always have a range that can be extended to the left. The algorithm proceeds exactly as the rdfcsa over those two copies, except that the intersection algorithm of LTJ is replaced by the custom algorithm range intersect . An additional benefit is that going rightwards in the binding is somewhat more expensive on the ring than going leftwards, and this new variant goes always leftwards.

## 6 Improved Variable Elimination Orders

Our second contribution is the study of improved VEOs in the context of compact indices for LTJ, which deviate from the VEO defined in Section 2.3. The first improvement is the use of adaptive VEOs; the second is on how to efficiently compute (or approximate) w ij in our compact index representations.

## 6.1 Adaptive VEOs

In previous work using the VEO described in Section 2.3, the VEO is fixed before running LTJ. The selectivity of each variable x j is estimated beforehand, by assuming it will be the first variable to eliminate. In this case, Eq. (1) takes the minimum of the number of children in all the trie nodes we must intersect, as an estimation of the size of the resulting intersection. The estimation is much looser on the variables that will be eliminated later, because the children to intersect can differ a lot for each value of x j .

We then consider an adaptive version of the heuristic: we use the described technique to determine only the first variable to eliminate. Say we choose x j . Then, for each distinct binding x j := c , the corresponding branch of LTJ will run the VEO algorithm again in order to determine the second variable to eliminate, now considering that x j has been replaced by c in all the triples t i where it appears. This should produce a much more accurate estimation of the intersection sizes.

In the adaptive setting, we do not check anymore that the new variable shares a triple with a previously eliminated one; this aimed to capture the fact that those triples would be more selective when some of their positions were bound, but now we know exactly the size of those progressively bound triples. The lonely variables are still processed at the end.

Observe that, in the adaptive case, there is not anymore a single VEO; each different branch can have one. While this technique does not require any extra space, it could incur in an extra cost to repeatedly recompute the VEO (in fact, only its first variable) for each binding. The cost to compute Eq. (1), on each of our compact index representations, becomes then of paramount importance for adaptive VEOs.

## 6.2 Computing the VEO predictors

The ring cannot efficiently compute w ij as described in Section 2.3, because it does not know the number of children of the node v : the ring only has the range C ∗ [ l . . r ] corresponding to v , which results from resolving the constants in t i ; recall Section 3.4. The size r -l +1 of the range was then used as a reasonable estimation of w ij [14, 15]. In the case t i has one constant and x j is to its right, we can also use r -l + 1 to estimate w ij , because the range size would be the same in both directions. We do the same when implementing the rdfcsa .

While the use of r -l +1 as a predictor of the true weight w ij can be seen as an approximation, it can be argued to be a better predictor of the difficulty of binding x j in t i . Note that r -l +1 is the number of leaf descendants of the current node v of the trie τ i , whose children are the bindings of x j in t i . The number of descendants may be a more accurate estimation of the total work that is ahead if we bind x j in t i , as opposed to the children, which yield the number of distinct values x j will take without looking further.

By using (additional) wavelet trees, we can also compute w ij as the number of children of v on the ring , in O (lg n ) time [30]. What we need is to count the number of different symbols in the range C ∗ [ l . . r ]. Let M be such that M i [ ] is the largest value i ′ &lt; i such that C ∗ [ i ] = C ∗ [ i ′ ], or 0 if there is no such i ′ . This implies that C ∗ [ q ] is

the first occurrence of a symbol in C ∗ [ l . . r ] iff l ≤ q ≤ r and M q [ ] &lt; l . We can then count the number of first occurrences of symbols in C ∗ [ l . . r ] by counting the number of values less than l in M l . . r [ ]. This is accomplished by the range count function (Section 3.1) if we have M represented as a wavelet tree.

Note that the use of M requires that the new variable x j is to the left of the constants in t i ; therefore we need one sequence M per column C ∗ in both the (actual) ring for the order spo and the (virtual) ring for the order ops . So, even if we use just one bidirectional ring , we must add two sequences M (thus tripling the space).

## 6.3 Refining VEO predictors

The value w j obtained by using the VEO predictor where the estimator is the size of the range C ∗ [ l . . r ] corresponds to the maximum number of triples that can participate in the intersection. Therefore, it is an upper bound to the size of the intersection of the set of triples.

We can obtain a better approximation of the intersection size by splitting the values of C ∗ [ l . . r ] into disjoint subsets of the alphabet and applying Eq. (1) to each. The sum of the weights of the subsets is a more refined approximation to the intersection. We can then refine the heursitic of Eq. (1) as

$$w _ { j } = \sum _ { \gamma \subset [ 1, \sigma ] } \min \{ w _ { i j } ^ { \gamma } \ | \ x _ { j } \text{ appears in triple } t _ { i } \},$$

where w γ ij is the weight of x j in t i for the partition γ of the alphabet. The partitions are disjoint and their union is [1 , σ ].

The ring can exploit the wavelet trees to easily compute w γ ij . Let us consider a variable x j that appears in a triple pattern t i , with the possible values of x j in the range C ∗ [ l . . r ]. Our estimation algorithm starts in the range B 1 ,σ [ l . . r ] of the root. By mapping [ l . . r ] to its left child ( B 1 ,m ), where m is ⌊ ( σ +1) ⌋ / 2, we retrieve the range B 1 ,m [ l ′ . . r ′ ] of the symbols from C ∗ [ l . . r ] that belong to the first half of the alphabet [1 , m ]. That range is computed in O (1) time as [ rank 0 ( B 1 ,σ , l -1)+1 . . rank 0 ( B 1 ,σ , r )]. The length of this range is equivalent to w [1 ,m ] ij . By using rank 1 instead of rank 0 we compute the range of [ l . . r ] in the right child ( B m +1 ,σ ), whose length is w [ m +1 ,σ ] ij . Since w [1 ,m ] ij + w [ m +1 ,σ ] ij = w ij for every i, j , (min i w [1 ,m ] ij ) + (min i w [ m +1 ,σ ] ij ) ≤ min i w ij is a tighter upper bound on the size of the intersection.

In that procedure we obtain two partitions, [1 , m ] and [ m + 1 , σ ]. If we continue mapping the current ranges in B 1 ,m and B m +1 ,σ to their children, each previous partition splits into two other halves. Therefore, by repeating those steps k levels, we get up to 2 k partitions. The length of each range in a node of the k -th level matches a weight w γ ij . As k increases, the approximation of the heuristic improves (indeed, if we reach k = lg σ we obtain the actual size of the intersection, at cost O σ ( )).

For example, consider two triples, t i and t i ′ , whose defined ranges are [1 . . 4] and [5 . . 8], respectively, in the sequence of Fig. 2. Note that their intersection is empty. Since both ranges have length 4, the weight w j per Eq. (1) is 4. In order to apply Eq. (5), the algorithm starts at the root B 1 6 , and maps each range to its children. For

Table 1 : The partitions γ and weights obtained in the sequence of Fig. 2 with the ranges [1 , 4] and [5 , 8] of two triple patterns t i and t i ′ , respectively. Column k indicates the number of levels to traverse in the wavelet tree.

|   k | γ                               | w γ ij   | w γ i ′ j   | min     |   w j |
|-----|---------------------------------|----------|-------------|---------|-------|
|   0 | [1 , 6]                         | 4        | 4           | 4       |     4 |
|   1 | [1 , 3] [4 , 6]                 | 2 2      | 0 4         | 0 2     |     2 |
|   2 | [1 , 2] [3 , 3] [4 , 5] [6 , 6] | 1 1 2 0  | 0 0 0 4     | 0 0 0 0 |     0 |

example, the range B 1 6 , [1 . . 4] maps to B 1 3 , [1 . . 2] and B 4 6 , [1 . . 2], thus w [1 3] , ij = 2 and w [4 6] , ij = 2. In the same way, from B 1 6 , [5 . . 8] we just reach B 4 6 , [3 . . 6], so w [1 3] , i j ′ = 0 and w [4 6] , i j ′ = 4. Consequently, w j = min( w [1 3] , ij , w [1 3] , i j ′ )+min( w [4 6] , ij , w [4 6] , i j ′ ) = 2, which is a closer bound to the actual intersection size. By descending one more level from the ranges in B 1 3 , and B 4 6 , , we will obtain four partitions and w j reaches 0. The partitions and weights obtained for each level are shown in Table 1.

Note that we are assuming that the range in the ring contains the values of the variable to bind x j . However, it is possible that in t i the defined range does not correspond to that variable. Those cases can occur when only one position of t i is bound. For instance, if the predicate of t i is bound to a constant c , the ring defines the range C l . . r s [ ] ( T pos ). When the variable x j is the object of t i , there is no direct access to the values of x j .

In that case, as in the main algorithm, we compute the size of each partition γ in C o [1 . . n ] ( T spo ), without any interval restriction. With this approach, w γ ij is equivalent to the number of triples whose object belongs to γ . From those, we just need to count the triples where its predicate has constant c . Since those partitions correspond to nonoverlapping consecutive intervals in T osp , the number of triples whose predicate is c in each alphabet partition γ is obtained as rank c ( C , e p ) -rank c ( C , s p ) + 1, where [ s, e ] is the range of γ in T osp . This range is computed as s = A c o [ s ] + 1 and e = A c o [ e +1], where c s and c e are the first and last symbol, respectively, of each alphabet partition γ .

## 7 Experimental results

We compare the compact indexing schemes described along the paper and various state-of-the-art alternatives, in terms of space usage and time for evaluating various types of BGPs.

Our experiments ran on an Intel(R) Xeon(R) CPU E5-2630 at 2.30GHz, with 6 cores, 15 MB cache, and 378 GB RAM.

## 7.1 Datasets and queries

We run two benchmarks over the Wikidata graph [31], which we choose for its scale, diversity, prominence, data model (i.e., labeled edges) and real-world query logs [32, 33]. The graph features n = 958 844 164 triples, which take 10.7 GB if stored in plain , , form using 32 bits for the identifiers.

We consider a real-world query log [32]. In search of challenging examples, we downloaded queries that gave timeouts, and selected queries with a single BGP, obtaining 1 295 unique queries. Those are classified into three categories: (I) 520 BGPs formed , by a single triple pattern, which mostly measure the retrieval performance of the index; (II) 580 BGPs with more than one triple but only one variable appearing in more than one triple, which measure the performance of joins but do not distinguish good from bad VEOs (as long as the join variable is eliminated first, of course); (III) 195 complex BGPs, where the performance of different VEOs can be compared.

All queries are run with a timeout of 10 minutes and a limit of 1000 results (as originally proposed for WGPB [9]). This measures the time the systems need to display a reasonable number of results. We also compare the systems without the limit of results, which measures throughput in cases where we need all the results. The space of the indices is measured in bytes per triple (bpt); a plain 32-bit storage requires 12 bpt.

## 7.2 Systems compared

Our experiments compare all indexing schemes described:

- · Two ring variants (Section 3), Ring -large and Ring -small, corresponding to using plain or compressed bitvectors in the wavelet trees, respectively (these are called Ring and C-Ring, respectively, in the original paper [14, 15]).
- · Their extension to compute the standard VEO based on number of children (Section 6.2): VRing -large, VRing -small, VURing -large and VURing -small.
- · Their corresponding unidirectional versions, which compute intersections using the wavelet tree (Section 5): URing -large and URing -small.
- · Their extension to compute the refined estimators for the VEO (Section 6.3), both in their bidirectional and unidirectional variantes: IRing -large, IRing -small, IURing -large, and IURing -small. The number of levels that descend those estimators is configured to 3.
- · All the versions above compute the VEO in traditional ('global VEO') and in adaptive form (Section 6.1).
- · Two rdfcsa variants (Section 4): RDFCSA -large represents Ψ in plain form; RDFCSA -small sets t Ψ = 16 and uses Huffman and run-length encoding to compress Ψ.

We also compare various prominent graph database systems:

- · MillenniumDB [13]: A recently developed open-source graph database. We use here a specialized version that stores six tries in the form of B+-trees and supports full LTJ, with a sophisticated (yet global) VEO. We run MillenniumDB over a RAM disk to avoid using external memory.

Fig. 5 : Index space and the averaged query times of the adaptive variants in msec, limiting outputs to 1000 results. Suffixes s and l mean small and large , respectively.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-87b9d9b8-1d52-4b06-a82a-95f2d65c2df5.jpg)

- · Jena LTJ [9]: An implementation of LTJ on top of Apache Jena TDB. All six different orders on triples are indexed in B+-trees, so the search algorithm is always wco.
- · Virtuoso [35]: The graph database hosting the public DBpedia endpoint, among others. It provides a column-wise index of quads with an additional graph ( g ) attribute, with two full orders ( psog , posg ) and three partial indices ( so , op , gs ) optimized for patterns with constant predicates. It supports nested loop joins and hash joins.
- · RDF-3X [34]: Indexes a single table of triples in a compressed clustered B+-tree. The triples are sorted and those in each tree leaf are differentially encoded. RDF-3X handles triple patterns by scanning ranges of triples and features a query optimizer using pair-wise joins.
- · Blazegraph [36]: The graph database system hosting the official Wikidata Query Service [32]. We run the system in triples mode, with B+-trees indexing orders spo , pos , and osp . It supports nested-loop joins and hash joins.

The code was compiled with g++ with flags -std=c++11 and -O3; some alternatives have extra flags to enable third party libraries. Systems are configured per vendor recommendations.

## 7.3 Results

Table 2 shows the index space in bytes-per-triple (bpt) and some general statistics on the query times obtained on our benchmark, when we limit the results to 1000. We list all the ring and rdfcsa variants first, and then other systems. Fig. 5 illustrates the tradeoff between index space and average query time for our adaptive variants.

Table 2 : Space and query times (in msec) of all the systems, limiting results to 1000, with Gl(obal) and Ad(aptive) VEOs. Timeouts count queries exceeding 10 min.

| System        | Space   | Average   | Average   | Median   | Median   | Timeouts   | Timeouts   |
|---------------|---------|-----------|-----------|----------|----------|------------|------------|
|               | (bpt)   | Gl        | Ad        | Gl       | Ad       | Gl         | Ad         |
| Ring -small   | 7.30    | 3056      | 1173      | 24       | 24       | 5          | 0          |
| IRing -small  | 7.30    | 2568      | 696       | 27       | 27       | 4          | 0          |
| Ring -large   | 12.15   | 2256      | 414       | 8        | 8        | 3          | 0          |
| IRing -large  | 12.15   | 2021      | 176       | 8        | 8        | 3          | 0          |
| URing -small  | 14.61   | 2779      | 872       | 20       | 20       | 4          | 1          |
| IURing -small | 14.61   | 2300      | 353       | 24       | 20       | 3          | 0          |
| URing -large  | 23.53   | 1481      | 373       | 8        | 8        | 0          | 0          |
| IURing -large | 23.53   | 1319      | 161       | 8        | 8        | 0          | 0          |
| VRing -small  | 35.42   | 4594      | 3198      | 24       | 24       | 4          | 3          |
| VRing -large  | 40.28   | 3067      | 1265      | 8        | 8        | 5          | 1          |
| VURing -small | 42.74   | 3467      | 1727      | 20       | 20       | 1          | 2          |
| VURing -large | 51.65   | 2124      | 1059      | 8        | 8        | 0          | 1          |
| RDFCSA -small | 15.85   | 2323      | 1248      | 8        | 8        | 1          | 1          |
| RDFCSA -large | 23.54   | 579       | 390       | 2        | 2        | 0          | 0          |
| MillenniumDB  | 156.78  | 96        | 96        | 27       | 27       | 0          | 0          |
| Jena LTJ      | 168.84  | 1930      | 1930      | 162      | 162      | 1          | 1          |
| Virtuoso      | 60.07   | 4880      | 4880      | 50       | 50       | 8          | 8          |
| RDF-3X        | 85.73   | 8230      | 8230      | 126      | 126      | 13         | 13         |
| Blazegraph    | 90.79   | 9220      | 9220      | 54       | 54       | 14         | 14         |

## 7.3.1 The general picture

It is immediately evident that adaptiveness and the use of the refined estimator is always a good strategy, especially in terms of robustness: average times and timeouts are considerably reduced in all cases. Adaptiveness speeds up all Ring variants by a factor of 2-11, whereas the refined estimation further speeds up the adaptive variants by a factor of 1.7-2.5. The dominating strategies, each with its own space-time niche and all using the adaptive variant, are:

- · The tiny variant: IRing -small uses just 7.30 bpt (nearly half of a plain storage of the triples), and solves queries with a median of 27 msec and an average of 0.70 sec.
- · The medium variant: RDFCSA -large roughly doubles that space (23.54 bpt) and reduces the median to nearly 2 msec. It also offers much better average times on simple queries and with unlimited number of results, as seen later. IURing -large, using the same space as RDFCSA -large, has a worse median but a better average time, 0.16 sec. It is not so interesting, however, in comparison with IRing -large, which uses half the space and is only marginally slower on average.
- · The small variant: IRing -large uses nearly the space of the triples in plain form (12.15 bpt) and solves queries with a median of 8 msec and an average of 0.18 sec.

| System        | Space (bpt)   | Type I   | Type I   | Type II   | Type II   | Type III   | Type III   |
|---------------|---------------|----------|----------|-----------|-----------|------------|------------|
|               |               | Avg      | Med      | Avg       | Med       | Avg        | Med        |
| IRing -small  | 7.30          | 12       | 8.0      | 380       | 36        | 3455       | 97         |
| IRing -large  | 12.15         | 3.9      | 2.9      | 93        | 11        | 881        | 32         |
| IURing -large | 23.53         | 4.6      | 4.0      | 75        | 12        | 832        | 36         |
| RDFCSA -large | 23.54         | 0.6      | 0.3      | 18        | 2.9       | 2611       | 14         |

Type I

Fig. 6 : Time distribution, in milliseconds, per query type, limiting outputs to 1000 results. The figures show boxplots for the smaller variants, marking the median inside. Horizontal positions are slightly shifted for visibility; see Table 2 for the exact space values. Hatched/empty boxes refer to global/adaptive VEOs. The numbers on top indicate where the capped whiskers reach.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-de0735e3-93a7-4282-b8b5-bd63ea31a7c9.jpg)

URing variants. The one-directional ring, URing , improves the times of Ring by 10%-50% depending on the variant, in exchange for doubling its space. The largest improvements turn out not to be so relevant, however, because they correspond to the small URing version, which loses by 20%-50% to the large corresponding Ring version, while using about the same space. The large URing versions, on the other hand, are only 10% faster than their corresponding Ring version, while doubling their space. Using similar space as URing , RDFCSA -large turns out to be more interesting in that it offers more stable times, with a median of 2 instead of 8. RDFCSA -small, instead, is not competitive.

VRing variants. It is also apparent that computing w ij as the number of leaf descendants for choosing VEOs using Eq. (1) performs much better than the original formula [9] that uses the number of children of the node: the VRing variants are much larger and slower than their corresponding Ring counterparts. In the case of adaptive VRing , where the VEO is recomputed for every binding, this is worsened by the fact that computing w ij on the VRing takes O (lg n ) time, as opposed to O (1) on the Ring .

Classical systems. The best performing classical systems are generally wco: MillenniumDB and (way behind) Jena LTJ, which use about 13 times more space than our 'small' variant ( IRing -large). MillenniumDB is almost twice as fast as IRing -large on the average, but has a higher median. This suggests it incurs a base cost of a few tens of milliseconds for every query, even the easy ones. No other classical index (including the non-wco ones) is competitive with our compressed variants.

## 7.3.2 Query types and space-time tradeoffs

Fig. 6 shows the time distributions on each query type. As expected, adaptive query plans and refined estimation of the intersections make no difference with respect to global ones in queries of type I and II, except for a few small gaps. Instead, they make a big difference in queries of type III, more in terms of robustness (lower average, less dispersion) than in the medians. The refined estimation of intersections has, as we have seen, a large impact on averages, but is not noticeable in terms of distribution. This shows that the refinement is mostly useful to avoid few, but very high, query times that are produced when using the coarser measure.

Using twice the space of IRing -large, RDFCSA -large performs better, most clearly on the simpler query types, where the time to extract the output tuples dominates. On those queries RDFCSA -large exploits its faster access to the data. Its smaller version, RDFCSA -small, instead, is dominated by IRing -large on queries of type II and III (but not on type I).

The table on top of the figure shows only the best performing variants, which are all adaptive. It clearly shows how times decrease steadily as we use more space. The exception is that, on type-III queries, IRing -large fares better than RDFCSA -large. In this type of queries the query resolution strategy is more important than the mere time to access the data.

Fig. 7 : Comparing the (global) VEOs of VRing , Ring , and IRing on queries of type III limited to 1000 results, with variants that choose the VEO at random or optimally.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-c95a8171-93ed-43cc-a1e4-f935df6bcb12.jpg)

## 7.3.3 Variable elimination orders

As already noted, the VRing variants increase the space while worsening query times. This shows up especially on the average times of Table 2, where the VRing adaptive variants are 2-3 times slower than their corresponding Ring variants. In part this is due to the O (lg n ) time invested in computing the number of children, what can be confirmed by the fact that, on global VEOs where this computation is done only a few times, the VRing variants are 'only' 20%-50% slower. But still, with global VEOs, where this O (lg n ) burden is insignificant, the results show that the Ring variants generate better VEOs than their VRing counterparts, apart from computing them faster. The fact that the medians and boxplot distributions are much closer than the averages show that, while most generated VEOs are similar, Ring avoids very bad VEOs that VRing sometimes generates.

This leads to the question of how good is the original strategy described in Section 2.3. To answer it, we created Ring variants that choose the VEO at random, in nonadaptive form for simplicity, and compare them in Fig. 7. The variant Ring R, which uses a completely random order, is not competitive at all. Ring RNL, which leaves the lonely variables to the end, does much better, showing the convenience of this strategy. The results improve even more on Ring RE, which in addition avoids eliminating variables that are disconnected from previously eliminated ones, if possible. Note that this is just like Ring , yet using random values to estimate the weights w ij . VRing distributes only slightly better than such a random estimation (and, actually, worsens a lot on the average), but Ring , which uses the number of leaf descendants to compute w ij , performs noticeably better. IRing , which refines the estimation of the intersections, performs similarly to Ring when using a global VEO. This changes on the adaptive versions: Ring A sharply outperforms Ring , and IRing A further outperforms Ring A.

An important question here is how much more margin for improvement do we have by choosing VEOs. To partially answer it, we executed Ring with all the possible global VEOs , and chose the best time for each query to create an ideal variant called Ring B. As the number of orders to try is the factorial of the number of variables, we reduced the search space by considering only the non-lonely variables and forcing the others

Fig. 8 : Index space and the averaged query times of the adaptive variants in seconds, not limiting outputs. Suffixes s and l mean small and large , respectively.

![image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00558v1-figure-13a2c196-d301-40a6-81d9-4e7e55c56692.jpg)

to be connected with some eliminated variable in some triple if possible, as Ring does; we believe the best time should always be within that search space. Further, we did not optimize those queries with 7 or more variables; we just used the time obtained by Ring on those. The times of Ring B are then an upper bound to the best times Ring could possibly obtain by choosing a good VEO (note that we also leave out adaptive orders). Even so, Fig. 7 shows that Ring B sharply outperforms IRing , our best global VEO, by a factor of about 4 on the average and 2 in the median. Ring B actually outperforms our best adaptive VEO, IRing A, by a factor of about 2 in the median, but interestingly, IRing A is almost 4 times faster on the average. This shows that, in many cases, the adaptive VEOs outperform the best possible global VEO. On the other hand, the experiment shows that it is still possible to improve a lot upon our current VEOs.

## 7.3.4 Not limiting the number of results

The case without limits in the number of answers is shown in Table 3, where for succinctness we left only the best performing of the classical indices. Fig. 8 shows the space-time tradeoffs with respect to the average adaptive times.

Although the times are much higher and thus the scale measures seconds, the dominant variants are the same as before. An important difference, however, is that adaptiveness and refined estimation of intersections now have little impact on the times. One reason for this is that now the cost to report so many results dominates the overall query time, thereby reducing the relative impact of using better or worse techniques to produce them. Indeed, our times limited to 1000 results suggest that adaptive VEOs produce results sooner along the query process than global VEOs.

The fact that the enumeration of results dominates makes RDFCSA -large the clear winner of 'medium' size, not only on the median but also on the average, where it outperforms IRing -large by a factor of two. MillenniumDB also benefits from reporting

Table 3 : Space and query times (in sec) of all the systems, with Gl(obal) and Ad(aptive) VEOs, not limiting the results. Timeouts count queries exceeding 10 min.

| System        | Space   | Average   | Average   | Median   | Median   | Timeouts   | Timeouts   |
|---------------|---------|-----------|-----------|----------|----------|------------|------------|
|               | (bpt)   | Gl        | Ad        | Gl       | Ad       | Gl         | Ad         |
| Ring -small   | 7.30    | 83.6      | 81.8      | 2.9      | 2.9      | 101        | 99         |
| IRing -small  | 7.30    | 82.3      | 80.1      | 2.7      | 2.7      | 99         | 94         |
| Ring -large   | 12.15   | 46.8      | 44.2      | 0.9      | 0.9      | 59         | 53         |
| IRing -large  | 12.15   | 45.4      | 42.9      | 0.8      | 0.8      | 58         | 54         |
| URing -small  | 14.61   | 75.1      | 71.9      | 2.2      | 2.0      | 94         | 86         |
| IURing -small | 14.61   | 72.7      | 73.9      | 2.0      | 2.0      | 89         | 90         |
| URing -large  | 23.53   | 47.4      | 46.3      | 1.0      | 1.0      | 59         | 58         |
| IURing -large | 23.53   | 45.2      | 43.1      | 0.8      | 0.8      | 58         | 55         |
| VRing -small  | 35.42   | 84.6      | 83.6      | 2.9      | 2.9      | 99         | 97         |
| VRing -large  | 40.28   | 45.2      | 44.5      | 0.9      | 0.9      | 55         | 53         |
| VURing -small | 42.74   | 75.1      | 72.5      | 2.2      | 2.1      | 89         | 85         |
| VURing -large | 51.65   | 46.7      | 46.3      | 1.0      | 1.0      | 55         | 56         |
| RDFCSA -small | 15.85   | 43.3      | 42.2      | 0.9      | 0.9      | 44         | 43         |
| RDFCSA -large | 23.54   | 22.5      | 21.3      | 0.2      | 0.2      | 31         | 26         |
| MillenniumDB  | 156.78  | 12.0      | 12.0      | 0.05     | 0.05     | 16         | 16         |

Table 4 : The best performing indices, separated by query type, without limiting the results. Times are given in seconds.

| System        | Space   | Type I   | Type I   | Type II   | Type II   | Type III   | Type III   |
|---------------|---------|----------|----------|-----------|-----------|------------|------------|
|               | (bpt)   | Avg      | Med      | Avg       | Med       | Avg        | Med        |
| IRing -small  | 7.30    | 25.5     | 0.100    | 105.4     | 7.80      | 150.4      | 21.89      |
| IRing -large  | 12.15   | 10.3     | 0.034    | 52.1      | 2.23      | 103.1      | 5.85       |
| IURing -large | 23.53   | 10.2     | 0.036    | 51.8      | 2.53      | 104.7      | 7.14       |
| RDFCSA -large | 23.54   | 3.1      | 0.004    | 24.5      | 0.74      | 60.6       | 1.84       |

many results, because of its locality-friendly data layout. It outperforms IRing -large by a factor of 3.5 and RDFCSA -large by a factor of 1.8 on the average. On the medians, MillenniumDB is 16 times faster than IRing -large and 4 times faster than RDFCSA -large.

Table 4 summarizes the main statistics on the best performing variants, separated by query type. It can be seen that RDFCSA -large now clearly outperforms all the IRing variants even on type-III queries.

## 8 Conclusions

We have introduced new compact indices, combined with novel query resolution strategies, to solve Basic Graph Patterns on graph databases using Leapfrog TrieJoin (LTJ), the leading worst-case-optimal (wco) multijoin algorithm. Concretely:

- · We uncover a space-time tradeoff formed by compact indices. The Pareto-optimal variants use from about 0.6 to 2.0 times the space needed to store the triples in raw form. These compressed indices are outperformed only by the classic LTJ implementation in MillenniumDB [13], which uses 14 times the space needed to store the triples.
- · We show that using the total number of leaves descending from an LTJ trie node yields much better variable elimination orders compared with the classic measure of the number of children of the node: while the latter approximates the cost of performing the next intersection, the former better estimates the whole future cost. Our better estimation speeds up query resolution by a factor over 2, and almost 8 when combined with adaptive plans.
- · We combine those new indices with adaptive variable elimination orders , in contrast with the global orders in use. We show that adaptively choosing the next variable to eliminate along the query process yields results much sooner: our adaptive query plans are up to 5 times faster to obtain the first 1000 results, and they even outperform in many cases the best possible non-adaptive plan. The time to obtain all the results, instead, is nearly the same.
- · We also show that the estimation of the intersection size can be refined by using features that are unique of our compact representation, which further speeds up the adaptive query times by a factor of up to 2.4. Further, we show that there is much space for improvement in terms of choosing a good variable ordering when generating query plans.

Overall, our new representations outperform the original ring by a factor up to 13 to produce the first 1000 results, while using the same space, and by 2 overall using about twice the space; this doubled space is still several times less than those of classical indices. Classical wco and non-wco indices are (often sharply) outperformed by our fastest variants. Only one of those, using 4 times the space of our largest relevant variant, outperforms it by a factor 2 on the average.

We remark that our compact indices run in main memory and would not be diskfriendly. While their compactness make them fit in memory for larger datasets, a relevant future work direction is to design compact representation formats for disk or distributed memory, where compactness translates into fewer I/Os or communication at query resolution time.

Another limitation of our compact indices is that they do not yet support updates. A way to support updates is to replace the wavelet tree bitvectors of all the ring structures by dynamic variants [37]. In this case, a node or triple can be inserted or deleted in the graph in O (lg n lg σ ) time. This, however, multiplies all the operation times by O (lg n ), which is a high price especially if we consider that updates are not only infrequent in many use cases, but also that queries require many more accesses than

updates. A recent development of dynamic bitvectors that are sensitive to the frequency of queries versus updates [38] yields a promising implementation of dynamism in our scenario: we anticipate almost no increase in query times by supporting efficient updates in the graph.

Data availability statement. The data and source code that support the findings of this study are openly available in zenodo at https://zenodo.org/records/13141588 and https://zenodo.org/records/13142779, respectively.

Acknowledgements. Supported by ANID - Millennium Science Initiative Program -Code ICN17 002, Chile. A.F. and A.G. are funded in part by MCIN/AEI/10.13039/501100011033: grant PID2020-114635RB-I00 (EXTRACompact); by MCIN/AEI/10.13039/ 501100011033 and EU/ERDF 'A way of making Europe': PID2021-122554OB-C33 (OASSIS) and PID2022-141027NB-C21 (EARTHDL); by MCIN/AEI/10.13039/501100011033 and 'NextGenerationEU'/ PRTR: grants TED2021-129245B-C21 (PLAGEMIS), PDC2021-120917-C21 (SIGTRANS) and by GAIN/Xunta de Galicia: GRC: grants ED431C 2021/53, and CIGUS 2023-2026. G.N. is funded in part by Fondecyt Grant 1-230755, Chile.

## References

- [1] Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Proc. ACM International Conference on Management of Data (SIGMOD), pp. 23-34 (1979)
- [2] Atserias, A., Grohe, M., Marx, D.: Size bounds and query plans for relational joins. SIAM Journal on Computing 42 (4), 1737-1767 (2013)
- [3] Ngo, H.Q., Porat, E., R´, C., Rudra, A.: Worst-case optimal join algorithms. In: e Proc. 31st Symposium on Principles of Database Systems (PODS), pp. 37-48 (2012)
- [4] Ngo, H.Q., R´ e, C., Rudra, A.: Skew strikes back: new developments in the theory of join algorithms. SIGMOD Record 42 (4), 5-16 (2013)
- [5] Veldhuizen, T.L.: Triejoin: A simple, worst-case optimal join algorithm. In: Proc. 17th International Conference on Database Theory (ICDT), pp. 96-106 (2014)
- [6] Khamis, M.A., Ngo, H.Q., R´ e, C., Rudra, A.: Joins via geometric resolutions: Worst case and beyond. ACM Transactions on Database Systems 41 (4), 22 (2016)
- [7] Nguyen, D., Aref, M., Bravenboer, M., Kollias, G., Ngo, H.Q., R´, C., Rudra, e A.: Join processing for graph patterns: An old dog with new tricks. In: Proc. 3rd International Workshop on Graph Data Management Experiences and Systems (GRADES), pp. 1-8 (2015)

| [8]   | Ngo, H.Q.: Worst-case optimal join algorithms: Techniques, results, and open problems. In: Proc. 37th Symposium on Principles of Database Systems (PODS), pp. 111-124 (2018)                                                                          |
|-------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [9]   | Hogan, A., Riveros, C., Rojas, C., Soto, A.: A worst-case optimal join algorithm for SPARQL. In: Proc. 18th International Semantic Web Conference (ISWC), pp. 258-275 (2019)                                                                          |
| [10]  | Harris, S., Seaborne, A., Prud'hommeaux, E.: SPARQL 1.1 Query Language. W3C Recommendation. https://www.w3.org/TR/sparql11-query/ (2013)                                                                                                              |
| [11]  | Aberger, C.R., Lamb, A., Tu, S., N¨tzli, o A., Olukotun, K., R´, e C.: Emptyheaded: A relational engine for graph processing. ACMTransactions on Database Systems 42 (4), 20 (2017)                                                                   |
| [12]  | Kalinsky, O., Etsion, Y., Kimelfeld, B.: Flexible caching in trie joins. In: Proc. 20th International Conference on Extending Database Technology (EDBT), pp. 282-293 (2017)                                                                          |
| [13]  | Vrgoc, D., Rojas, C., Angles, R., Arenas, M., Arroyuelo, D., Buil-Aranda, C., Hogan, A., Navarro, G., Riveros, C., Romero, J.: MillenniumDB: An open-source graph database system. Data Intelligence 5 (3), 560-610 (2023)                            |
| [14]  | Arroyuelo, D., Hogan, A., Navarro, G., Reutter, J., Rojas-Ledesma, J., Soto, A.: Worst-case optimal graph joins in almost no space. In: Proc. 47th ACM International Conference on Management of Data (SIGMOD), pp. 102-114 (2021)                    |
| [15]  | Arroyuelo, D., G´mez-Brand´n, o o A., Hogan, A., Navarro, G., Reutter, J.L., Rojas- Ledesma, J., Soto, A.: The Ring: Worst-case optimal joins in graph databases using (almost) no extra space. ACM Transactions on Database Systems 29 (2), 5 (2024) |
| [16]  | Brisaboa, N., Cerdeira-Pena, A., Bernardo, G., Fari˜a, n A., Navarro, G.: Space/time-efficient RDF stores based on circular suffix sorting. The Journal of Supercomputing 79 , 5643-5683 (2023)                                                       |
| [17]  | Manola, F., Miller, E.: RDF Primer. W3C Recommendation, (2004). http://www.w3.org/TR/rdf-primer/                                                                                                                                                      |
| [18]  | Wang, J., Trummer, I., Kara, A., Olteanu, D.: ADOPT: Adaptively optimizing attribute orders for worst-case optimal join algorithms via reinforcement learning. Proceedings of the VLDB Endowment 16 (11), 2805-2817 (2023)                            |
| [19]  | Clark, D.: Compact pat trees. PhD thesis, University of Waterloo (1996)                                                                                                                                                                               |
| [20]  | Munro, I.: Tables. In: Proc. 16th Conference on Foundations of Software                                                                                                                                                                               |

|      | Technology and Theoretical Computer Science (FSTTCS), pp. 37-42 (1996)                                                                                                                                                                                  |
|------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [21] | Raman, R., Raman, V., Rao, S.S.: Succinct indexable dictionaries with applica- tions to encoding k -ary trees, prefix sums and multisets. ACM Transactions on Algorithms 3 (4), 43 (2007)                                                               |
| [22] | Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 841-850 (2003)                                                                               |
| [23] | Navarro, G.: Wavelet trees for all. Journal of Discrete Algorithms 25 , 2-20 (2014)                                                                                                                                                                     |
| [24] | Claude, F., Navarro, G., Ord´˜ez, on A.: The wavelet matrix: An efficient wavelet tree for large alphabets. Information Systems 47 , 15-32 (2015)                                                                                                       |
| [25] | Gagie, T., Navarro, G., Puglisi, S.J.: New algorithms on wavelet trees and appli- cations to information retrieval. Theoretical Computer Science 426-427 , 25-41 (2012)                                                                                 |
| [26] | Barbay, J., Claude, F., Navarro, G.: Compact binary relation representations with rich functionality. Information and Computation 232 , 19-37 (2013)                                                                                                    |
| [27] | Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing 22 (5), 935-948 (1993)                                                                                                                        |
| [28] | Sadakane, K.: New text indexing functionalities of the compressed suffix arrays. Journal of Algorithms 48 (2), 294-313 (2003)                                                                                                                           |
| [29] | Navarro, G., M¨kinen, a V.: Compressed full-text indexes. ACM Computing Surveys 39 (1), 2 (2007)                                                                                                                                                        |
| [30] | Gagie, T., K¨rkk¨inen, a a J., Navarro, G., Puglisi, S.J.: Colored range queries and document retrieval. Theoretical Computer Science 483 , 36-50 (2013)                                                                                                |
| [31] | Vrandecic, D., Kr¨tzsch, o M.: Wikidata: A free collaborative knowledgebase. Communications of the ACM 57 (10), 78-85 (2014)                                                                                                                            |
| [32] | Malyshev, S., Kr¨tzsch, o M., Gonz´lez, a L., Gonsior, J., Bielefeldt, A.: Getting the most out of Wikidata: Semantic technology usage in Wikipedia's knowledge graph. In: Proc. 17th International Semantic Web Conference (ISWC), pp. 376- 394 (2018) |
| [33] | Bonifati, A., Martens, W., Timm, T.: Navigating the maze of Wikidata query logs. In: Proc. World Wide Web Conference (WWW), pp. 127-138 (2019)                                                                                                          |
| [34] | Neumann, T., Weikum, G.: The RDF-3X engine for scalable management of RDF data. VLDB Journal 19 , 91-113 (2010)                                                                                                                                         |

| [35]   | Erling, O.: Virtuoso, a hybrid RDBMS/graph column store. Data Engineering Bulletin 35 (1), 3-8 (2012)                                                                                             |
|--------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [36]   | Thompson, B.B., Personick, M., Cutcher, M.: The Bigdata ® RDF Graph Database. In: Linked Data Management, pp. 193-237 (2014)                                                                      |
| [37]   | M¨kinen, a V., Navarro, G.: Dynamic entropy-compressed sequences and full-text indexes. ACM Transactions on Algorithms 4 (3), 32 (2008)                                                           |
| [38]   | Navarro, G.: Adaptive dynamic bitvectors. In: Proc. 31st International Sympo- sium on String Processing and Information Retrieval (SPIRE) (2024). To appear, see https://arxiv.org/abs/2405.15088 |
Diego Arroyuelo Fabrizio Barisione Antonio Fariña Adrián Gómez-Brandón Gonzalo Navarro
New Compressed Indices for Multijoins on Graph Databases
A recent surprising result in the implementation of worst-case-optimal (wco)
multijoins in graph databases (specifically, basic graph patterns) is that they
can be supported on graph representations that take even less space than a
plain representation, and orders of magnitude less space than classical
indices, while offering comparable performance. In this paper we uncover a wide
set of new wco space-time tradeoffs: we (1) introduce new compact indices that
handle multijoins in wco time, and (2) combine them with new query resolution
strategies that offer better times in practice. As a result, we improve the
average query times of current compact representations by a factor of up to 13
to produce the first 1000 results, and using twice their space, reduce their
total average query time by a factor of 2. Our experiments suggest that there
is more room for improvement in terms of generating better query plans for
multijoins.