FL-RMQ: A Learned Approach to Range Minimum Queries

In today’s digital world, an enormous amount of data is generated on a daily basis. This introduces new challenges in designing several advanced software systems. Among others, much attention is devoted to computational problems involving variable-length keys (aka, strings), which undoubtedly constitute a core component of a plethora of big-data applications such as search engines [40, 35, 42], RDF and key-value stores [54, 51], scalable distributed storage systems [13], computational biology tools [3, 52], Large Language Models [7], and $n$-gram language models [41, 65, 50], just to mention a few.

Recently, motivated by such rapid growth of data, researchers have started to investigate novel methods for designing algorithms and data structures that leverage how those data are distributed to deliver faster or more succinct solutions. The seminal work of Kraska et. al [45] has shaken the foundations of the decades-old field of indexing data structures, showing how replacing well-established design elements, such as B-Tree nodes, with Machine Learning (ML) models leads to significant improvements in time efficiency and memory usage. Following this line of work, numerous solutions have been proposed in the indexing scenario, respectively in the one-dimensional case [28, 20, 72, 77, 15, 48] and the multi-dimensional one [21, 64, 58, 63], and their effectiveness have also been evaluated in theory [25, 78]. However, the benefits of such a novel combination are not only limited to the problem of indexing, but several other classical problems have been revisited under this paradigm such as approximate membership queries [66, 19, 73, 68], range filtering [17, 74], frequency estimation [16], compressed $rank$ and $select$ dictionaries [10, 24], and sorting [46, 47, 12, 69].

Considering such premises, here we focus on the Range Minimum Query (RMQ) problem, which finds applications in many string-related tasks such as pattern matching [2, 18], text indexing [31, 67], text compression [61, 14, 49], and string mining [30, 39]. Formally, given an array $A[1..n]$ of $n$ items drawn from a totally ordered universe, the RMQ problem is to design a data structure that returns for any given range $A[i,j]$ the position of the leftmost minimum, indicated hereafter with $RM{Q}_A(i,j)$. Such a problem is generally framed in two settings: the indexing setting, where the data structure can access the underlying array $A$, and the encoding setting, where the array $A$ cannot be accessed.

In the indexing setting, solutions are pretty simple and based on a block decomposition of the input array $A$ or a sparse version of the naive lookup table [5]. It turns out that any indexing solutions using $O(n/C)$ bits must have $\mathrm{\Omega }(C)$ query time [11]. An optimal solution matching this lower bound, although not practical, is the one by Fischer & Heun [29].

In the encoding setting, most solutions rely on a sequence of reductions from RMQs on $A$ to Lowest Common Ancestor (LCA) queries on a tree representation of $A$, called Cartesian tree. In this setting, the information-theoretic lower bound constraints any encoding solution to use at least $2n-\mathrm{\Theta }(\log n)$ bits. Much work has been devoted to efficiently solving LCAs on succinct representations of the Cartesian tree, and the first solution matching such lower bound (up to lower order term) is again due to Fischer & Heun [29]. Recently, more practical encoding approaches have been proposed [36, 23, 4], and also compressed RMQ data structures have been investigated [34, 56, 38].

In this article, we focus for the first time in the literature on designing an indexing data structure for the RMQ problem via a learned-based approach. Indeed, we show a surprising connection between RMQs on $A$ and the geometry of a properly defined set of 2D-points in the Cartesian plane. We then hinge on a classical result in computational geometry to design a novel data-aware indexing scheme for RMQs that deploys piecewise-linear approximations of the distribution of these points to learn the mapping between properly encoded ranges of $A$ and the positions of their leftmost minimum (i.e., their RMQs). As a result, the performance of our data structure depends on the number $\mathrm{\ell }$ of such linear functions (aka, models), which is strongly related to the underlying data distribution, and can be several orders of magnitudes smaller than the input size (see Section 4). Because of its algorithmic features, we name our data structure Fully-Learned RMQ, hence shortly FL-RMQ. We establish theoretical bounds for its space usage and query time, covering both worst-case scenarios and average-case performance for uniformly distributed inputs, which compare favorably with the best-known indexing solutions (see Table 1 and Section 3). Finally, we corroborate our theoretical findings with a wide set of experiments showing that our FL-RMQ offers more robust space-time trade-offs than the other known practical indexing solutions on both artificial and real-world datasets (see Section 4).

We believe that our approach is noteworthy not only for the novel space-time trade-offs it introduces for the RMQ problem, but also because it extends the learned-based design paradigm to a new problem (indeed RMQ), it is flexible enough to be applied easily to its encoding variant (as we comment in Section 5), and it paves the way to further research opportunities on possibly other problems too.

A straightforward solution in the indexing setting (i.e., the one that allows access to the indexed array) is to store the answer for all the $\left(\genfrac{}{}{0pt}{}{n}{2}\right)$ valid queries in a table, and then look up the answer in (optimal) constant time. Another technique is to perform a so-called block decomposition, where the input array is divided into blocks of size $b$, and only the answers for those subarrays are stored. Each query is divided into at most three subqueries: one out-of-block query that spans several blocks, and two in-block queries (completely contained inside a block). In-block queries require at most two linear scans of $b$ elements, while out-of-block queries are answered by comparing $O(n/b)$ block minima. The final answer is obtained by comparing at most three values and overall requires $O(b+n/b)$ time while using $\mathrm{\Theta }(n/b\log b)$ bits of space. A value for $b$ that minimizes the query time is $\sqrt{n}$.

Bender & Farach-Colton [5] presented an elegant solution taking $\mathrm{\Theta }(n\log n)$ memory words, which uses a sparse version of the naive lookup table, called sparse table. The main idea is to compute the answers for all queries whose range size is a power of two, i.e. a table $T[1..n][1..\lceil \log n\rceil ]$ with $T[i,j]=RM{Q}_A(i,i+2^j-1)$. An arbitrary query $RM{Q}_A(i,j)$ is eventually answered by determining first the maximal $k$ such that $2^k\le j-i+1$, and then comparing $A[T[i,k]]$ and $A[T[j-2^k+1,k]]$ to return their minimum.

In the indexing setting, any data structure using $O(n/C)$ bits in addition to $A$ must have $\mathrm{\Omega }(C)$ query time [11]. A solution matching this lower bound is the one introduced by Fischer & Heun [29] using $\frac{2n}{c(n)}-\mathrm{\Theta }(\frac{n\log \log n}{c(n)\log n})$ bits on top of $A$ and solving queries in $O(c(n))$ time, where $c(n)=O(n^{\delta })$ for an arbitrary constant . Such a solution is based on a novel variant of the Four-Russians-Trick that only allows storing the answers for blocks with the same Cartesian tree [75] topology. Most notably, an instantiation of their solution with $c(n)=O(1)$ was the first indexing solution to have an optimal query time while only requiring a linear number of bits of space [29]. Interestingly, they also show how to adapt the string compression scheme of Ferragina and Venturini [27] to obtain the first entropy-bounded solution using $n{H}_k+O(\frac{n}{\log n}\left(k\log \sigma +\log \log n\right))$ bits and $O(1)$ query time.

Most encoding approaches (i.e., the ones that are not allowed to access the indexed array) heavily rely on the Cartesian tree, and in particular, on the well-known sequence of reductions from RMQs on $A$ to LCA queries on its corresponding Cartesian tree and back to $\pm 1$RMQs [32, 6] (i.e., an RMQ problem on arrays whose adjacent values change just by $\pm 1$). The information-theoretic lower bound for encoding data structures is $2n-\mathrm{\Theta }(\log n)$ bits, and again the first result matching such lower bound (up to lower order terms) while delivering $O(1)$ query time is due to Fischer & Heun [29]. It is based on a novel succinct encoding of the Cartesian tree of $A$ and a sublinear size data structure for $\pm 1$RMQs.

Based on such an approach, some practical optimizations were introduced [36]. Most notably, Ferrada & Navarro [23] provided a simpler formulation of RMQs based on balanced parenthesis [57] and used a Range-Min-Max tree [60] to solve the $\pm 1$RMQs, hence obtaining a practical solution that matched the space lower bound and fast query times (although not optimal). This paved the way for practical improvements to that solution. In particular, Baumstark et al. [4] provided the most competitive implementation to date.

Another research direction aimed to reduce the space of encoding solutions even further by leveraging data compression techniques. In particular, Gawrychowski et al. [34] proposed two approaches. The first one combines a grammar-compressed representation of $A$ with a modification of the direct access scheme of Bille et al. [9], thus solving RMQs in $O(\log n)$ time while using a number of memory words proportional to the grammar size. The second one augments a top-tree compressed [8] Cartesian tree $𝒯$ of $A$ with support for $O(\log n)$ time LCA queries (and thus RMQs) using $O(|𝒯|)$ words of space. Recently, Munro et al. [56] introduced hypersuccinct trees, a compression method for ordinal trees achieving optimal space usage for many tree sources. They apply this novel technique to Cartesian trees achieving constant time RMQs while using $1.736n+o(n)$ bits on average. Lastly, Hamada et al. [38] proposed a practical tree compression technique based on tree covering [22] and applied it to Cartesian trees. Their implementation is the only available (encoding) solution having constant query time and using less than $2n$ bits on average.

In our paper, we focus on indexing approaches whose key theoretical bounds are summarized in Table 1 alongside our results. For the experimental analysis, we compare our FL-RMQ with variants of the block decomposition and with the sparse table approach. A discussion on how to extend FL-RMQ to the encoding setting is deferred to conclusions.

We start by framing the RMQ problem as a supervised learning task in which the training dataset $D_A$ is formed by taking as input data the range-pairs $(i,j)$, where , and the target data are the positions $RM{Q}_A(i,j)$ of their leftmost minima ²²2Notice that our concept of a training dataset slightly differs from traditional machine learning scenarios, as our model is not required to generalize to unseen data; instead, it is designed to handle the same data points present in the training set during queries.. Hence we aim at learning a model $f:{\mathbb{N}}^2\to \mathbb{N}$ that maps valid ranges of $A$ to positions of their leftmost minima. We note that the size of the training dataset $|D_A|$ poses a computational challenge, as the number of valid ranges scales quadratically with the input size. To overcome this issue, we exploit the same idea of the sparse table solution [5], and hence we consider a subset of the original training set whose range-pairs are only the ones whose size is a power of two, and thus ${\tilde{D}}_A=\{((i,j),m)\in D_A|\exists k:j-i+1=2^k\}$. This way, we exponentially reduce the size of the training set from $\mathrm{\Theta }(n^2)$ to $\mathrm{\Theta }(n\log n)$.

Choosing the model $f$ is a fundamental task in designing learned data structures. Indeed, one must balance the ability of the model to mimic the desired mapping (i.e., its accuracy) with the corresponding inference time and storage requirement (i.e., efficiency in time versus efficiency in space). Experimental results on the performance of learned data structures (see e.g. [45, 76, 53, 44, 71, 28]) suggest that linear models are typically preferable over more complex ones, such as quadratic, cubic, or neural networks, and single-dimensional models should be preferred over multi-dimensional ones.

Following these guidelines, since we are dealing with ranges, we first need a method for converting ranges of the form $[i,j]$ with $i\le j$ into integers. Ideally, we would like an encoding $e()$ that preserves their natural ordering: namely, given the two ranges $[i,j]$ and $[x,y]$, such that $i\le x$ and $j\le y$, we want $e(i,j)\le e(x,y)$.

We notice that if we plot the points corresponding to valid ranges into the Cartesian plane, as shown in Figure 1a, they form an upper triangular grid. Now, to enumerate ranges and get the encoding function $e()$, we decide to take into account their appearance (from left to right) on the diagonals of such a grid in a bottom-up manner. So, given a range $[i,j]$, we are interested in how to compute $e(i,j)$ efficiently. As already mentioned, since we are using the sparse table approach, the length of $[i,j]$ is always a power of two, i.e. $j-i+1=2^k$ for some positive integer $k$. Therefore, the point in the Cartesian plane corresponding to $[i,j]$ lies on the $k$-th diagonal (counting from the bottom), and the number of points on such diagonal is equal to $n-2^k+1$. Following this observation, $e(i,j)$ can be calculated by first computing the number of points under the $k$-th diagonal, which is given by ${\sum }_{d=0}^{k-1}\left(n-2^d+1\right)=k(n+1)-2^k+1$, and then adding the relative position of the point corresponding to $[i,j]$ on the $k$-th diagonal, which is given by the value of $i$. Combining these quantities, we get the closed formula for our range encoding:

As for the efficiency of this computation, we remark that $j-i+1=2^k$, hence we do not need to compute powers of two explicitly. However, extracting the exponent $k$ requires computing the most significant bit of a word that can be done in constant time using a precomputed table ³³3Storing the answers for blocks of size $\log n/2$ requires at most two table look-ups and $O(\sqrt{n}\log \log n)$ bits of space., or when available, through specialized hardware instructions. In both cases, we emphasize that this computation is fast in practice, and thus it can be neglected.

The second ingredient of our proposal is an implementation of $f$ based on a Piecewise-Linear Approximation (PLA), with maximum error $\epsilon$, of the sequence of all the encoded ranges and the positions of their minimum value, i.e. $\{(e(i,j),m)|((i,j),m)\in {\tilde{D}}_A\}$. A PLA consists of a sequence of segments each of them represented as a triple $s_z=(r_z,{\alpha }_z,{\beta }_z)$, where ${\alpha }_z$ is the slope, ${\beta }_z$ is the intercept, and $r_z$ is the abscissa of the point that started such segment. The segments computed by a PLA are such that every point in the sequence has a vertical distance of at most $\epsilon$ from one of these segments. We highlight that such an $\epsilon$-approximation of an increasing sequence of 2D-points can always be computed in linear time and optimally, hence using the minimum number of segments [62], as done in several learning-based data structures to date (see e.g. [45, 33, 28] and many others nowadays).

However, deploying the Piecewise-Linear Approximation (PLA) in our setting is not immediate. In fact, in general, our sequence of 2D-points is not monotone, see the example of Figure 1b. Although this property is not mandatory for computing a PLA, it is preferable because it makes the data more easily approximated by a smaller number of segments. Moreover, having an increasing sequence allows us to quickly determine which segment is responsible for a given encoded range (see Section 3.2). Therefore, we make our sequence monotone by following the ordering given by the encoding of Equation 1: this way, ranges corresponding to points lying on the same diagonal have the positions of their minima sorted in increasing order. However, this ordering can be broken when considering the first point lying on the next diagonal, see Figure 1b as an example. To avoid this issue, we add a correction term $\mathrm{\Delta }$ whenever this ordering is not followed, having care of adding such a correction to all the subsequent positions, as shown in Figure 1c.

In summary, our implementation of $f$ consists of only two components: the optimal number of segments that $\epsilon$-approximate the position of the minimum of ranges of $A$ whose length is a power of two, properly shifted by corrections that ensure their (increasing) monotonicity; the sequence of those (integer) corrections that allow to scale back a prediction into its original valid position in $A$. In the subsequent sections, we explore the novel space-time trade-offs given by this representation and evaluate its practical performance. Due to its algorithmic features, we call our solution Fully-Learned RMQ, hence shortly FL-RMQ.

We run our experiments on an Ubuntu machine with $3024$ GiB of internal memory and an Intel Xeon Platinum 8260M CPU. Our FL-RMQ is implemented in C++, and RMQs are answered as in Corollary 4 on top of the uncompressed data structure of Theorem 1.

To assess the performance of FL-RMQ, we experiment on both artificial and real-world datasets. Following the methodology of Ferrada & Navarro [23], we generate three artificial datasets of $n={10}^9$ integers. (1) RAND: a sequence of uniformly distributed integers in the range $[1,n]$. (2) INC-$\delta$: a pseudo-increasing sequence whose $i$-th element is chosen uniformly at random in the range $[i-\delta ,i+\delta ]$. (3) DEC-$\delta$: analogous to INC-$\delta$, but the $i$-th element is uniformly chosen in the range $[n-i-\delta ,n-i+\delta ]$. For the latter two datasets, Ferrada & Navarro use $\delta \in \{0,{10}^2,{10}^4\}$. However, small values of $\delta$ make the resulting sequences nearly sorted, giving an undue advantage to our FL-RMQ. Therefore we fairly consider the harder instances, namely that with $\delta ={10}^4$. For what concerns real-world datasets, we use the Longest Common Prefix (LCP) array of texts coming from the Pizza & Chili corpus [26].

We start by assessing the effectiveness of our approach by measuring the average number of elements covered by a segment. Using real-world datasets, we compute the ratio between the number of segments $\mathrm{\ell }$ and the size $n$ of the LCP arrays. Figure 2 shows that, even for small values of $\epsilon$, the number of segments is from $2$ to $4$ orders of magnitude less than $n$, proving once again the compression capability of the PLA also in this novel setting of RMQs.

We then focus on evaluating the query time and space usage of our FL-RMQ data structure, comparing it with the following baselines: a block decomposition with blocks of progressively larger sizes, specifically $b\in \{\log n,\sqrt[4]{n},\sqrt[3]{n},\sqrt{n}\}$, and the classical sparse table approach. We avoided both the entropy compressed and the optimal solution of Fischer & Heun surveyed in Section 2 because there are no available implementations to the best of our knowledge. In this experimental evaluation, we include all artificial datasets but limit the real-world datasets to only the largest one, since Figure 2 shows that their distributions are very similar. Lastly, over all experiments, for each range of size $\{{10}^1,{10}^2,\mathrm{\dots },{10}^7,{10}^8\}$, we generate ${10}^4$ queries by randomly choosing the starting point for each of them. In the following, we measure the average query time in nanoseconds and the additional space (i.e. the extra space on top of the input array) in bits per element (bpe). Because of the page limit, we only report the most significant sample of each experiment in Figure 3, please refer to Appendix 6 for the complete results.

We start by commenting on the performances of the sparse table (orange bullet) and the block decomposition approaches (blue squares), as they do not depend on the underlying data distribution. As expected, the sparse table approach is the fastest on all datasets, as it only requires four memory accesses and a few arithmetic operations independently of the query size. However, we can notice that it is also the most space-consuming, requiring between $960$ (RAND, INC-$\delta$, and DEC-$\delta$) and $1024$ (ENGLISH) bpe. Moving to the block decompositions, we observe that for the smallest range size (${10}^1$) they have the same query time, as they all resort to a simple linear scan when solving queries. The decomposition with block size $\sqrt{n}$, as expected, guarantees the smallest space occupancy but has the slowest query times for mid-sized ranges (${10}^3$ and ${10}^4$). However, for larger ranges (${10}^6-{10}^8$), it becomes more efficient among the block decompositions and eventually ranks as the second fastest and even the fastest among them. Switching to blocks of size $\log n$ (lightest blue squares), we observe an almost symmetrical behavior. This configuration is the most space-consuming but delivers the fastest query times for small ranges. However, its performance progressively degrades as the range size increases. Lastly, we observe that blocks of size $\sqrt[4]{n}$ and $\sqrt[3]{n}$ give a trade-off between the previously discussed behaviors. Specifically, $\sqrt[4]{n}$ performs well on mid-size ranges (${10}^2-{10}^4$), while $\sqrt[3]{n}$ offers better performance on larger ones (${10}^5-{10}^8$).

Turning to our solution, we observe that it behaves similarly on both ENGLISH and RAND. Hence we only comment on the latter dataset as the same considerations apply to the other. The results are shown in Figure 3 and detailed in Figure 4 and 5 of Appendix 6. For small ranges (${10}^1$ and ${10}^2$), FL-RMQ performs comparably to other approaches across all values of $\epsilon$, with the sparse table being only slightly faster but much more space consuming. For mid-size ranges (i.e., ${10}^3-{10}^5$), FL-RMQ delivers a smooth space-time trade-off that is competitive with the block decompositions. Notably, the one using $\epsilon =512$ is very close to the best performances of the $\sqrt[3]{n}$-decomposition. Lastly, for large ranges (${10}^6-{10}^8$), our FL-RMQ excels by providing the best performance along the Pareto frontier. In particular, the query time is very competitive, varying from hundreds ($\epsilon =64$) to thousands ($\epsilon =2048$) of nanoseconds, while requiring between $2.06$ and $0.06$ bpe.

Switching to the results obtained on INC-$\delta$ shown in Figure 3, and detailed in Figure 6 of Appendix 6, we first observe that for small ranges (${10}^1-{10}^4$), our FL-RMQ performs similarly to the various block decompositions in terms of query time, across all values of $\epsilon$. However, for larger ranges (${10}^5-{10}^8$), FL-RMQ significantly improves on the block decomposition, with the implementation using $\epsilon =512$ providing the fastest query time. Considering the space usage, we observe an interesting pattern: for values of $\epsilon$ between $64$ and $256$, FL-RMQ uses more space than any of the block decompositions. This suddenly changes for larger values of $\epsilon$ (between $512$ and $2048$), where FL-RMQ uses $2$ orders of magnitude less space than any block decomposition. On DEC-$\delta$, we observe a very similar behavior, and the same comments apply (see Figure 7 of Appendix 6). The latter results are particularly interesting, as they emphasize the main strength of FL-RMQ: its ability to leverage regularities in the underlying data distribution to achieve novel and competitive space-time trade-offs.

As a final experiment, motivated by the lack of an absolute winner among all the implementations considered, we designed and implemented a hybrid approach that combines FL-RMQ with a block decomposition. For each dataset, we observe a threshold in the query size where FL-RMQ begins to outperform the block decompositions. Based on this, we select the two best-performing configurations and build our FL-RMQ only for ranges larger than this threshold, while resorting to the block decomposition for smaller ones. This hybrid solution is represented with purple stars in Figure 3, and in the detailed experiments reported in Figures 4 – 7 of Appendix 6. Starting from RAND and ENGLISH, based on the previous experiments, we set the threshold to ${10}^4$ and choose blocks of size $\sqrt[3]{n}$ varying $\epsilon$ between $32$ and $64$. Figure 3 shows that this combination has good performances on small ranges (${10}^1-{10}^3$) while outperforming all the other implementations on larger ones (from ${10}^4$ on). However, for INC-$\delta$ and DEC-$\delta$ (Figure 3 and Figures 6 – 7 of Appendix 6), the best implementations of FL-RMQ (i.e. the ones using $\epsilon \in \{512,1024\}$) are already orders of magnitudes smaller than any block decomposition, with a better or very similar query time, therefore the hybrid approach is not convenient in these cases.

We introduced a novel approach to the RMQ problem by establishing a connection between the input data and the geometry of a properly defined set of points in the Cartesian plane. Building on this insight, we designed a data structure whose performance adapts to the underlying data distribution, provided theoretical guarantees for its efficiency, and experimentally demonstrated its practicality against existing approaches.

While our proposal still requires further development, we suggest several future directions: first, our FL-RMQ can be extended to solve the $\pm 1$RMQs arising in the encoding setting [29, 36, 23, 4], thus obtaining an encoding data structure with possibly lower order space usage terms and more practical query times (further details in the journal version of this paper); second, extend the use of linear functions for the PLA to non-linear functions [37], which possibly reduce the value of $\mathrm{\ell }$; third, extend the theoretical bound on the number of segments $\mathrm{\ell }$ produced by the PLA to other input distributions, which could provide deeper insights into the performance of our data structure across various scenarios. Finally, significant opportunities remain for algorithmic engineering, such as utilizing specialized data layouts to enhance cache efficiency in binary searches [43], more space/time efficient solutions for predecessor searches, or applying vectorized instructions to streamline minimum computation over the short ranges $[p-\epsilon ,p+\epsilon ]$ on which the minimum search is restricted [70].