Compressing Highly Repetitive Binary Trees with an Application to Range Minimum Queries

To construct such mapping functions, we begin by augmenting the representation of Section 3 with a bit vector $S[\mathrm{1..2}n]$, which marks with $1$s the positions corresponding to the beginning (the first opening parenthesis) and the end (the last closing parenthesis) of each copied subtree in $B$; see the example in Figure 1. Moreover, we augment the bit vector $R$ from Section 3 with support for ${\text{rank}}_1$ and ${\text{select}}_1$ operations. Converting a position in $B$ to a position in $B_c$, and vice versa, can then be performed using the following auxiliary functions:

• $\mathrm{■}$

  $\varphi (i)$: Given a position $i$ in $B$, return a position in $B_c$. If $i$ is contained inside a copied subtree, return the position of the closing parenthesis of the corresponding pointer in $B_c$; Otherwise, return the properly scaled position of the same parenthesis in $B_c$. Let $r={\text{rank}}_1(S,i)$. Then:

  (1)

• $\mathrm{■}$

  ${\varphi }^{-1}(j)$: Given a position $j$ in $B_c$, return a position in $B$. If $i$ corresponds to a pointer, return the starting position of the copied subtree in $B$; Otherwise, return the properly scaled position of the same parenthesis in $B$. Let $r^{\prime }={\text{rank}}_1(R,j)$. Then:

  (2)

We give the intuition behind our formulation using the example in Figure 1. Consider the computation of $\varphi$ for $i=20$. First, we compute $r={\text{rank}}_1(S,i)$, which is equal to $2$, indicating that position $i$ lies outside a copied subtree in $B$. Next, we compute the position in $B_c$ corresponding to the copy immediately preceding $i$, namely ${\text{select}}_1(R,r/2)=12$. Finally, to obtain the result, we compute the distance between $i$ and the end of the copy immediately preceding it as $(i-{\text{select}}_1(S,r))=4$. Adding this distance to the previous quantity yields $\varphi (20)=12+4=16$. A similar idea is used to compute ${\varphi }^{-1}$.

The efficiency of $\varphi$ and ${\varphi }^{-1}$ depends on the implementation of $S$ and $R$. In theory, both can be supported in $O(1)$ time, e.g., by resorting to [41, 40]. However, since we strive for a practical implementation, we refrain from doing so and instead adopt the Elias-Fano encoding described in Section 2. As a consequence, since $S$ and $R$ contain $p$ ones (i.e., the number of copies found by the procedure of Section 3) and have lengths $n$ and $n_d\ll n$, respectively, implementing both mappings requires $O(p\log (n/p))$ bits of space and $O(\log n)$ time.

In the balanced parentheses representation of Definition 2, each node of the underlying tree is identified by the position of its closing parenthesis. An LCA query, therefore, takes as input two such positions $u$ and $v$ and returns the position of the closing parenthesis corresponding to their lowest common ancestor. As discussed in Section 1, this operation can be reduced to a $\pm 1\text{RMQ}$ on the balanced parentheses sequence, which asks for the position of the minimum excess in the range $B[u,v]$. For example, in Figure 1, the LCA of $u=24$ and $v=27$ is given by $\pm 1{\text{RMQ}}_B(24,27)=25$, since the minimum excess in that range occurs at position $25$.

This restricted version of RMQs can be solved in $O(1)$ time using $o(n)$ bits of space by resorting to standard precomputed tables [3, 42, 17]. However, this requires accessing the balanced parentheses representation $B$, which is not available in our setting.

In this section, we show how to overcome this issue, answering an LCA query between two nodes $u$ and $v$ directly on our compressed format. To this end, we begin by distinguishing the following three cases. Examples are shown in parentheses and refer to Figure 1. Recall that nodes are represented by the position of their closing parenthesis in $B$.

1. 1.

   Neither $u$ nor $v$ belongs to a copied subtree ($u=5$ and $v=20$).

2. 2.

   Exactly one of $u$ and $v$ belongs to a copied subtree ($u=6$ and $v=14$).

3. 3.

   Both $u$ and $v$ belong to different copied subtrees ($u=14$ and $v=28$).

Intuitively, since in all of the above cases the ancestor-descendant relationships in $B$ are preserved in $B_c$, the LCA of $u$ and $v$ can be obtained by computing the LCA of $\varphi (u)$ and $\varphi (v)$ in $B_c$, i.e. $\pm 1{\text{RMQ}}_{B_c}(\varphi (u),\varphi (v))$, and mapping the result back to $B$ using ${\varphi }^{-1}$.

This property no longer holds when $u$ and $v$ belong to the same copied subtree. Consider nodes $u=24$ and $v=30$ in Figure 1. In this case, the key idea is to recursively follow the pointer to the common source of both nodes until one of the three base cases is reached.

To formalize this idea, we describe a single step of this recursive approach. Please refer to Figure 1 for a running example. We first compute the starting position $m$ of the copied subtree containing both $u$ and $v$ in $B$, that is, $m={\text{select}}_1(S,{\text{rank}}_1(S,u))$ (note that $u$ and $v$ are interchangeable here). Next, we determine the starting position $s$ of the corresponding source subtree in $B$ by accessing the pointer array $P$. We then map $u$ and $v$ to positions within the source by setting $u^{\prime }=s+(u-m)$ and $v^{\prime }=s+(v-m)$. The LCA query is then solved recursively for $u^{\prime }$ and $v^{\prime }$, and the recursion ends after reaching one of the base cases.

Notice that each recursive calls return the position of the LCA within the source subtree. To translate this position back to the copied subtree, we compute its offset with respect to the start of the source $s$ and add this offset to $m$. The complete procedure for computing the LCA of two nodes in our compressed representation is presented in Algorithm 1.

Considering the cost of our algorithm, the $\pm 1\text{RMQ}$s on $B_c$ can be solved in $O(1)$ time using one of the approaches in [3, 42, 17] (we comment in Section 5 about their practicality). Overall, this only adds $o(n_d)$ bits of space to our representation.

Moreover, each recursive call requires $O(\log n)$ time, due to the ${\text{rank}}_1$ and ${\text{select}}_1$ operations on $S$, as well as the calls to $\varphi$ and ${\varphi }^{-1}$ (see Section 4.1). The total number of recursive calls is proportional to the length of the longest chain of copies $L$ in the minimal DAG representation of the underlying tree. Considering the example in Figure 1, we have $L=2$. Consequently, the overall running time of Algorithm 1 is $O(L\log n)$.

Given an array $A$, supporting LCA queries on its Cartesian tree $𝒞(A)$ allows us to answer RMQs on $A$. Since LCA queries are in turn reduced to $\pm 1\text{RMQ}$s on the balanced parentheses sequence $B$ of $𝒞(A)$, it is necessary to map indices of $A$ into positions of $B$, and vice versa.

By Definition 2, the value at position $i$ in $A$ corresponds to the node visited at step $i$ during an inorder traversal of $𝒞(A)$ (i.e., the node with inorder number $i$). The closing parenthesis of this node is therefore located at position ${\text{select}}_0(B,i)$ in $B$. Conversely, a closing parenthesis at position $i$ in $B$ corresponds to the value at position ${\text{rank}}_0(B,i)$ in $A$. As a consequence, RMQs can be formulated as follows [36]:

Notice that the inner part of Equation 3 corresponds to the LCA between the nodes ${\text{select}}_0(i)$ and ${\text{select}}_0(j)$, and is computed as described in Section 4. What remains is to show how to answer ${\text{rank}}_0$ and ${\text{select}}_0$ queries on $B$ using our compressed representation.

To this end, for each copy we store the ${\text{rank}}_0$ value (i.e., the inorder number) of its rightmost child in a separate array using $O(p\log n)$ bits overall. For example, in Figure 1 we store the values $7$ and $15$ for the first and second copy, respectively. Using this array, we can support both ${\text{rank}}_0$ and ${\text{select}}_0$ queries on $B$ by following a recursive strategy similar to the one used for LCA queries in Section 4. We defer a complete description to Appendix B; here we only mention that both operations can be done in $O(L\log n)$ time, where $L$ is again the longest chain of copies in the minimal DAG of $𝒞(A)$.

We conclude by summarizing our main result. Given an array $A[1..n]$, let $n_d$ be the number of nodes in the minimal DAG of its Cartesian tree $𝒞(A)$, of which $p=o(n_d)$ are copies. The overall space usage of our data structure is $2n_d+O(p\log n)+o(n_d)$ bits, and within such space it supports RMQs in $O(L\log n)$ time. This proves Theorem 1.

Our representation is theoretically more compact than existing ones [6, 5] that use $O(n_d)$ words of space (i.e., $O(n_d\log n)$ bits) at the cost of a possibly slower query time. Indeed, $L$ can be as large as $O(\sqrt{n})$ in the worst case (see Appendix A). However, our experimental results show that $L$ never exceeds $\log n$, and is significantly smaller on average (see Table 1).

In the next section, we present an extensive experimental evaluation on real-world datasets, showing that query times in practice are often faster than those of state-of-the-art implementations [22, 13, 2], while achieving the smallest space usage on $9$ out of $11$ datasets.

To obtain a practical implementation of RMQs, we introduce the following optimizations. We use a sparse table [3], that is, a table storing all answers to RMQs for dyadic intervals ⁷⁷7Intervals whose length is a power of $2$., built over samples of the input array. After an initial experimental evaluation, we set the sampling frequency to $2^{12}$ to achieve the best space-time trade-off.

The rationale behind this engineering trick is that for large ranges, the position returned by the sparse table is often correct and can be reported directly as the answer. This intuition is confirmed by the results in Figure 2, which show the percentage of queries solved directly using the sparse table for different query sizes. In particular, approximately $70\%$, $80\%$, and nearly $100\%$ of queries of length ${10}^4$, ${10}^5$, and ${10}^6$, respectively, are solved immediately using this technique. As we show in Section 5.3, this optimization adds only a moderate space overhead while significantly accelerating such queries.

Since most long queries are answered using the aforementioned sparse table, we are left only with short queries of length ${10}^1$–${10}^3$. These queries are very likely to map to short ranges in the balanced parentheses sequence of the Cartesian tree. Moreover, we expect the compressed balanced parentheses to be much shorter than the uncompressed ones. Therefore, to solve the $\pm 1\text{RMQ}$ queries in Algorithm 1, we avoid complex solutions designed to handle arbitrary ranges and to scale to large instances [3, 42, 17, 13, 15], and instead use linear scans accelerated by precomputed tables storing the answers for blocks of $16$ bits each. These tables fit within the cache of most architectures and introduce only a negligible space overhead.

Considering the longest chain of copies $L$, which controls the time complexity of our queries (see Theorem 1), Table 1 shows that this parameter never exceeds $\log n$ on any of the tested datasets. Moreover, the average chain length is much smaller than the maximum.

Lastly, some components of our compressed representation rely on existing libraries. The SA and LCP arrays of Section 3 are implemented using the highly optimized libsais library [21]. For the Elias-Fano representation of the sparse bit vectors in Sections 3 and 4, we use the broadword implementation provided by the SUX library [44]. For the plain bit vector of the compressed balanced parentheses, which requires support for rank and select operations, we use the most efficient implementation to date from the pasta library [31].

To assess the performance of our implementation, we consider real-world datasets. In particular, we use the LCP array of texts coming from the repetitive and non-repetitive collections of the Pizza & Chili corpus [16]. Among many others, this can be seen as a practical application, since RMQs on the LCP array of a text, in combination with its suffix array, can be used to speed up pattern matching queries [14]. In all the following experiments, to measure the space-time performance, we generate ${10}^2$ random queries for each range of size $\{{10}^1,{10}^2,\mathrm{\dots },{10}^5,{10}^6\}$. We measure the average query time in nanoseconds and the space usage in bits per element (bpe), comparing the following implementations:

• $\mathrm{■}$

  CRMQ<$t$>: Our implementation of the data structure of Theorem 1, where only maximal identical subtrees of size at least $t$ are compressed.

• $\mathrm{■}$

  Succinct: A practical version of the optimal solution by Fischer and Heun, due to Grossi and Ottaviano [22], implemented in the succinct library.

• $\mathrm{■}$

  RMM: The implementation of Ferrada and Navarro [13], which uses a range min–max tree to solve $\pm 1\text{RMQ}$s on the balanced parentheses.

• $\mathrm{■}$

  RecRMQ<$s,\mathrm{\Lambda },d$>: The recursive approach by Baumstark et al. [2], which partitions the excess array of the Cartesian tree into blocks of size $s$ across $\mathrm{\Lambda }$ levels of recursion. At each level, it stores the minimum excess value of each block. After $\mathrm{\Lambda }$ levels, the recursion terminates, and a sparse table is used to answer queries. Additionally, a top-level sparse table built over blocks of size $d$ can be used to further accelerate queries as we do.

• $\mathrm{■}$

  HyperRMQ<$b$>: A practical implementation of the hypersuccinct trees by Munro et al. [36], due to Hamada et al. [23]. Each micro-tree contains fewer than $2b$ nodes and is encoded using an entropy coder that the authors named depth-first arithmetic coding.

For the sake of presentation, only the most representative subset of the experimental results is shown in Figure 3; the complete results are reported in Appendix C.

We begin by observing that both Succinct (olive squares) and RMM (orange bullets) consistently yield the worst space-time trade-offs across all tested datasets. Consequently, we exclude them from our comparison, focusing on solutions that offer a better trade-off.

We next consider the only available implementation based on a compressed encoding, namely HyperRMQ (blue right-oriented triangles). Although it goes slightly below the lower bound of $2$ bpe on a few datasets ($3$ out of $11$, see Appendix C), it is always the slowest among all competitors, with query times on the order of ${10}^3$ nanoseconds. We therefore proceed by comparing RecRMQ with our implementation.

Starting with RecRMQ (purple stars), we observe that it offers the best space-time trade-offs among the previously discussed solutions (i.e., Succinct, RMM, and HyperRMQ) across all datasets and query ranges. In particular, query times are often in the range of hundreds of nanoseconds for small ranges ${10}^1$–${10}^4$, and drop to tens of nanoseconds for larger ones, that is, ${10}^5$–${10}^6$. This highlights the benefit of using the top-level sparse table, as discussed in Section 5.1. In terms of space usage, as expected, RecRMQ always uses more than $2$ bpe.

Finally, turning to our CRMQ (red crosses), we first note that for small query ranges, that is, ${10}^1$–${10}^3$, our solution is not particularly efficient and is only slightly better than HyperRMQ. We believe this is because, for such queries, the probability that the two nodes of the Cartesian tree lie in the same copy is high. This triggers recursive calls in Algorithm 1, which, although few in number (see Table 1), introduce a non-negligible overhead. This behavior changes significantly when considering larger query ranges, namely ${10}^4$–${10}^6$. In this regime, queries are more likely to be solved by the top-level sparse table, or after only a few recursive calls. As a result, on most datasets, our solution is on par with RecRMQ.

Moving to the space usage, our CRMQ is almost always the most space-efficient, going below the lower bound of $2$ bpe on $9$ out of $11$ datasets (see Appendix C). In particular, on the repetitive portion of the Pizza & Chili dataset (first two rows of Figure 3), the smallest space usage is an impressive $0.11$ bpe, corresponding to a reduction of $95\%$ with respect to the second most space-efficient solution. On non-repetitive texts (last two rows of Figure 3), the improvement is less pronounced but still substantial: the minimum space usage is around $0.81$ bpe, i.e., $61\%$ smaller than the second best solution.

Overall, the experimental evaluation shows that, when space efficiency is a primary concern or when queries are of medium to large size, our approach should be the solution of choice, as it achieves a significant space reduction while still delivering fast query times.