Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations

The rapid growth of data has led to the development of novel techniques for designing data structures that leverage regularities in the underlying data distribution to deliver faster or more succinct solutions to proper query operations. This novel line of research, known as learned data structures [15], integrates machine learning models with traditional algorithmic techniques to achieve improved space occupancy and query time performance.

A widely used tool in the field of learned data structures is the so-called Piecewise Linear Approximation (PLA), an error-bounded approximation of a two-dimensional set of points using a sequence of segments [20]. The common use of PLAs is due to their ability to capture linear trends in the input data, which frequently occur in many practical applications, while using little space and providing fast inference time. In this work, we focus on PLAs arising in two settings: (1) the compression setting, where the input sequence of points is increasing in both coordinates but the $x$-values are also consecutive; and (2) the indexing setting, where instead the $y$-values of the input sequence are consecutive. These two settings are general enough to cover a broad range of applications, including $rank$ and $select$ dictionaries [7, 2], time series compression [14], string indexing [24], one-dimensional indexing [15, 13], multi-dimensional indexing [17, 4], range minimum queries [9], monotone minimal perfect hashing [10], and range filtering [23], to mention a few.

Prior work concerning the study of theoretical properties of PLAs has primarily focused on providing upper bounds on the optimal number of segments $\mathrm{\ell }$ as a function of the sequence length $n$ and the maximum allowed error $\epsilon$, that is the maximum vertical distance between the $y$-coordinate of any input point and its covering segment. Such a relationship is fundamental from a theoretical perspective since it can explain the surprising performance of learned data structures and also allow a theoretical comparison with their classical counterparts. In this context, it is worth mentioning the pioneering study of Ferragina et al. [11] showing that in the indexing case under the assumption that the gaps between consecutive keys are independently and identically distributed random variables, with constant mean and variance, the optimal number of segments $\mathrm{\ell }$ is $\mathrm{\Theta }(n/{\epsilon }^2)$ with high probability. Later works [25, 3] provided better upper bounds, but they only considered PLAs formed by horizontal segments.

As far as lower bounds are concerned, we mention the work of Zeighami and Shahabi [26] which was the first to limit from below the model size (e.g., the number of segments $\mathrm{\ell }$ in a PLA or the number of neurons in a neural network) of any learned data structure achieving a given desired accuracy $\epsilon$ for a wide range of problems arising in database systems such as one- and multi-dimensional indexing, cardinality estimation, and range-sum estimation.

In our work, we assume that the segments have arbitrary slopes and the number of segments $\mathrm{\ell }$ forming an optimal PLA is known (e.g., computed by [20]), and thus provide the first information-theoretic lower bound to the storage complexity of that PLA in both the compression and the indexing settings (see Theorems 6 and 8). We then compare two representative data structures against these lower bounds, namely the LA-vector by Boffa et al. [2] (for the compression setting) and the PGM-index by Ferragina & Vinciguerra [13] (for the indexing setting), showing that both are optimal up to a constant factor. Finally, we conclude our work by designing two novel data structures for the aforementioned compression and indexing settings, that provide the same asymptotic query time as the LA-vector and the PGM-index, but with small additive terms to the introduced lower bounds.

We assume the transdichotomous word RAM model where the word size $w$ matches the logarithm of the problem size and arithmetic, logic, and bitwise operations, as well as access to $w$-bit memory cells, take $O(1)$ time. To simplify, we denote with $\log x$ the logarithm in base $2$ of $x$, and we assume that logarithms hide their ceiling and thus return integers.

Given a static sorted sequence of $n$ elements drawn from a finite integer universe $U$ of size $u$, we consider the following fundamental operations:

• $\mathrm{■}$

  $rank(S,x)$, which for $x\in U$ returns the number of $S$’s elements that are smaller or equal to $x$, i.e. $|\{x_i\in S|x_i\le x\}|$.

• $\mathrm{■}$

  $select(S,i)$, which for $i\in \{1,2,\mathrm{\dots },n\}$, returns the element in $S$ of position $i$, i.e. $rank(S,x)=i$. We assume $select(S,0)=0$.

If $S$ is represented with its characteristic bit vector $B_S$, namely, a bit vector of length $u$ such that $B_S[i]=1$ if $i\in S$, and $B_S[i]=0$ otherwise, then supporting such operations is equivalent to support the $ran{k}_1(B_S,x)$, which yields the number of $1$s before position $x$, and $selec{t}_1(B_S,i)$, which gives the position of the $i$-th $1$ in $B_S$. These operations have been studied extensively with many practical and theoretical results, and are at the core of any succinct or compressed data structure (see [18] for a comprehensive treatment). For our purposes, we briefly mention that they can be supported in $O(1)$ time while using only $o(u)$ additional bits on top of the underlying bit vector.

The information-theoretic lower bound to store $S$ is $ℬ(u,n)=\log \left(\genfrac{}{}{0pt}{}{u}{n}\right)$. Such value is related to the zero-order empirical entropy of its characteristic bit vector $B_S$, defined as $u{\mathscr{H}}_0(B_S)=n\log \frac{u}{n}+(u-n)\log \frac{u}{u-n}$. In fact, with simple arithmetic manipulations one obtains $ℬ(u,n)=u{\mathscr{H}}_0(B_S)-O(\log u)$. The best upper bound to represent $S$ with the minimum redundancy with respect to $ℬ(u,n)$, and while still being able to perform $rank$ and $select$ in optimal constant time, is given by the following data structure due to Pătraşcu [21]:

Theorem 1 implies constant time $rank$ and $select$ operations in $ℬ(u,n)+O(u/{\log }^{c}u)$ space, which essentially matches the lower bound of Pătraşcu & Viola [22]. To further reduce the space redundancy on top of $ℬ(u,n)$, one must allow for slower $rank$ or $select$ operations. A prominent example is given by the Elias-Fano encoding scheme [6, 5], which attains the following space-time trade-off for the aforementioned operations [18]:

Indeed, the space usage of Theorem 2 can be expressed in terms of $ℬ(u,n)$ as follows:

Thus obtaining a lower redundancy term with respect to Theorem 1 whenever $S$ is very sparse, which, however, requires giving up the constant time $rank$ operation. The literature offers other trade-offs (e.g., [18, 19]) that could be adopted in our solution, leading to corresponding time-space bounds. However, for the sake of presentation, in the remainder of the paper we focus on the results provided in Theorems 1 and 2.

A new line of research has recently started to investigate novel methods for designing algorithms and data structures that leverage regularities in the underlying data to deliver faster or more succinct solutions to a wide variety of problems. Most of these methods rely on a technique known as Piecewise Linear Approximation (PLA), which involves approximating a sequence of two-dimensional points using a set of segments.

A PLA can always be computed optimally, hence producing the minimum number of segments $\mathrm{\ell }$ in time proportional to the sequence length using an algorithm by O’Rourke [20].

Here, we focus on PLAs computed from monotone sequences of two-dimensional data points, in which a point $(x_i,y_i)$ is smaller than $(x_{i+1},y_{i+1})$ because it has a strictly smaller abscissa and a smaller ordinate $y_i\le y_{i+1}$. In particular, we consider two specific scenarios: (1) the compression setting, where PLAs are computed on sequences having consecutive $x$-values (i.e., $x_{i+1}=x_i+1$, with $x_1=1$), and (2) the indexing setting, in which PLAs are computed on sequences having consecutive $y$-values (i.e. $y_{i+1}=y_i+1$, with $y_1=1$). As already mentioned, despite the names, such scenarios are quite general and encompass a wide range of applications. To get a practical sense of the usage of PLAs in the design of learned data structures, we briefly outline two prominent examples.

In the design of learned and compressed $rank$ and $select$ dictionaries [2], the input sequence , is first mapped to a Cartesian plane representation where the $x$-axis corresponds to the sequence of positions $1,2,\mathrm{\dots },n$, while the $y$-axis represents the sequence values, namely $x_i$s. This transformation converts $S$ into a set of monotonically increasing two-dimensional points: $\{(i,x_i)|x_i\in S\}$. The key innovation of this approach is that the Cartesian plane representation reveals inherent regularities in the underlying sequence $S$. A PLA is then computed from such a sequence of points, and compression is achieved by storing for each point $(i,x_i)$ the absolute difference between $x_i$ and the approximation of the segment for position $i$ using just $\log (2\epsilon +1)$ bits. Performing a $select(S,i)$ operation then reduces to first finding the segment covering the abscissa value $i$, computing the approximate sequence value from such segment in $i$, and finally adding the correction term stored in position $i$ to retrieve the exact value. A $rank(S,x)$ operation can be naively solved by binary searching on the $select$ values, even if faster alternatives do exist [2].

In the design of learned one-dimensional indexes [13], given the input sequence , one performs the same mapping above onto a Cartesian plane representation. In this case, the $x$-axis contains the sequence values, while the $y$-axis corresponds to their respective positions $1,2,\mathrm{\dots },n$. Again, this transformation converts $S$ into a set of monotonically increasing two-dimensional data points: $\{(x_i,i)|x_i\in S\}$. The data structure then consists of a PLA computed from such a set of points and a search for a given key $x$ proceeds in three steps. First, the segment covering $x$ is identified through a binary search on the first keys covered by each segment. Second, the approximate position $i$ of $x$ is obtained from such a segment. Third, since the underlying sequence is monotonically increasing and the approximate position $i$ of $x$ is precise up to an error $\epsilon$, it is corrected via a (binary) search in the interval $[i-\epsilon ,i+\epsilon ]$. Such queries can be sped up by applying the same construction recursively to the sequence of first keys covered by each segment until a single one remains (see e.g. [13, 15]). This approach implements the index as a hierarchical structure, forming a tree of linear models. Consequently, searches involve a top-down traversal of the tree, trading faster queries for an increased space usage.

In the following, we review existing methods for the lossless compression of PLAs, focusing on the $predict(x)$ operation, which, given a value lying on the $x$-axis, identifies the segment covering $x$ and computes the corresponding $y$-value predicted by that segment.

Ferragina & Vinciguerra introduced the PGM-index [13], the first solution in the indexing case based on the optimal PLA computed by the O’Rourke algorithm [20], i.e., the one consisting of the minimum number of segments $\mathrm{\ell }$ providing an $\epsilon$-approximation of the input points. In particular, they designed two compression methods for the segments. The first one hinges on the observation that, in the indexing setting, the intercepts are monotonically increasing. Denoting with ${\beta }_i$ the intercept of the $i$-th segment and with $y_i$ its first covered $y$-value, this easily follows since ${\beta }_i\in [y_i-\epsilon ,y_i+\epsilon ]$ and ${\beta }_{i+1}\in [y_{i+1}-\epsilon ,y_{i+1}+\epsilon ]$, but $y_i+\epsilon \le y_{i+1}-\epsilon$ as in this particular case a segment covers at least $2\epsilon$ keys [13, Lemma 2]. Exploiting this, they convert the monotone sequence of floating-point intercepts into integers and store them with the data structure of Okanohara & Sadakane [19]. But, they stored uncompressed the first covered keys and slopes of each segment. For the sake of comparison, we provide the space usage for the PLA composing just the first layer of the PGM index. Since the universe of the underlying sequence is $u$, and each slope can be expressed as a rational number with a numerator and denominator respectively of $\log n$ and $\log u$ bits, they obtained the following result which we specialize via two approaches, one based on binary search (as proposed in [13]), and one using the data structure of Pătraşcu (see Theorem 1):

The second compression method targets the segment’s slopes, and is based on the observation that the O’Rourke algorithm does not compute a single segment but a whole family of segments whose slopes identify an interval of reals. The compressor then works greedily (and optimally) by trying to assign the same slope to most segments of the PLA, thus reducing the number of slopes to be fully represented. This is very effective on some real-world datasets, however, the authors did not provide an analysis of its space occupancy.

Moving to the compression setting, Boffa et al. introduced the LA-vector [2], the first learned and compressed $rank$ and $select$ dictionary based on the optimal PLA. Their compression scheme for segments hinges on the assumption that the sequence of intercepts is monotonically increasing, which is not necessarily the case in general. This is because, in the compression setting, segments may cover fewer than $2\epsilon$ points, as the $y$-value can increase by more than one between consecutive $x$-values. Ferragina & Lari [9] recently showed how to waive that assumption with a negligible impact on space occupancy, obtaining the following bound (we drop the cost of $cn$ bits for storing the correction vector $C$ in Theorem 3.2 of [2], and we add the solution based on the data structure of Pătraşcu):

Lastly, Abrav and Medvedev proposed the PLA-index [1] in a Bioinformatics application where the $x$- and $y$-values of the underlying sequence are increasing but not necessarily contiguous. They took an orthogonal approach to PLA compression by modifying the O’Rourke algorithm, enforcing each segment to start from the ending point of the previous one. This allows them to derive a more compact encoding, which may produce a suboptimal number of segments ${\mathrm{\ell }}^{\prime }\ge \mathrm{\ell }$. As their approach does not guarantee optimality and targets different sequence types, we defer comparison to the journal version.

We conclude by noticing that none of these results focused on studying lower bounds to the cost of storing PLAs (possibly in compressed form). Therefore, the first novel contribution of our work lies in deriving the first compressibility measures for PLAs in the two aforementioned settings. It will turn out that the storage schemes for PLAs of the LA-vector and the PGM-index are asymptotically optimal up to a constant factor. Hence, our second contribution is to design the first data structures for the compression and indexing settings that achieve the space lower bounds plus small additive terms, which are succinct in most practical cases.

We begin by observing that, in general, the segments of a PLA, whether in the compression or indexing setting, have floating-point components. As discussed in Section 3, some existing compression schemes assume that segments either start or end at an integer $y$-coordinate to exploit integer compression techniques. In our context, we work under the same assumption for two reasons: first, when establishing a lower bound on the space required to represent a PLA, it is important to note that the class of PLAs with floating-point components is larger than that of PLAs with integer components. Consequently, any lower bound proven for the latter also applies to the former. Second, as proved by Ferragina & Lari [9] this reduction has a negligible impact on the approximation error of the resulting PLA, and in fact, it only increases that error by a constant $3$. Therefore, without loss of generality, we can safely restrict our analysis to PLAs having segments with integer starting and ending ordinates.

Under this assumption, given the optimal number of segments $\mathrm{\ell }$, the approximation error $\epsilon$, the universe size $u$, and the length of the sequence $n$, we consider the problem of counting the number of possible PLAs that can be constructed using these parameters, in both the compression and indexing cases. Then, by a simple information-theoretic argument, taking the logarithm of such quantities gives a lower bound on the number of bits required to represent any PLA in the considered settings, and this provides a compressibility measure that any compression scheme should strive to achieve. Starting from PLAs arising in the compression setting, we prove the following theorem:

We begin by establishing constraints on the parameters of a PLA that are commonly observed in many practical applications. Specifically, we assume that $ϵ=O(1)$, $\mathrm{\ell }=o(n)$ and $n=o(u)$. Next, we proceed by formalizing the core operation performed on any PLA in both the compression and indexing settings. In particular, we define the $predict(x)$ operation, which, given a value lying on the $x$-axis, identifies the segment covering $x$ and computes the corresponding $y$-value predicted by that segment. Designing data structures that efficiently support this operation while achieving space usage close to the lower bounds of Section 4 is of both practical and theoretical interest since it can help to understand what the limits of PLA-based learned data structures are in terms of the redundancy needed to store and query the PLA itself, and possibly improve the performances of such data structures.

At the end of Section 2, we commented on the relation between the current literature and our lower bounds, highlighting that the storage schemes for PLAs of the LA-vector and the PGM-index are compact [18]. Due to space constraints, we sketch the main result here; please refer to the full version of this paper for the complete proofs [8]. Starting with the LA-vector (see Section 5.1), it turns out that the storage space of Lemma 5 can be expressed as ${ℬ}_{𝒞}(\mathrm{\ell },\epsilon ,u,n,𝐲)$ with an additive term that is either $O(\mathrm{\ell }\log \frac{u}{\mathrm{\ell }})$ or $O(\mathrm{\ell }\log \frac{u}{\mathrm{\ell }}+\frac{n}{{\log }^{c}n})$ depending if queries are answered with a binary search or with the data structure of Pătraşcu [21]. In the first case, the overhead is always $O({ℬ}_{𝒞}(\mathrm{\ell },\epsilon ,u,n,𝐲))$, while in the second case, that bound holds only when $\mathrm{\ell }=\omega (n/(\log u{\log }^{c}n))$. As a result, the storage space of the LA-vector is asymptotically optimal up to a constant factor, and thus is compact. Moving to the PGM-index (see the full version of this paper [8]), the additive term on top of the lower bound ${ℬ}_{ℐ}(\mathrm{\ell },\epsilon ,u,n,𝐱)$ is either $\mathrm{\Theta }(\mathrm{\ell }\log u)$ or $O(\mathrm{\ell }\log u+\frac{u}{{\log }^{c}u})$, depending on how queries are answered. In the first case, the overhead is always $\mathrm{\Theta }({ℬ}_{ℐ}(\mathrm{\ell },\epsilon ,u,n,𝐱))$, while in the second case that bound holds only when $\mathrm{\ell }=\mathrm{\Omega }(u/{\log }^{c+1}u)$. Therefore, the storage space of the PGM-index is also compact.

Motivated by this, the following sections will describe the design of the first data structures for the compression and indexing settings, achieving small additive terms to the lower bounds of Section 4, which turn out to be succinct in most practical cases, and most importantly provide the same asymptotic query time as the LA-vector and the PGM-index.

In this work, we addressed the problem of deriving the first compressibility measures for PLAs of monotone sequences in two distinct settings: compression and indexing, which are general enough to cover a broad range of applications. The measures we obtained provide a theoretical foundation for understanding the space requirements of any learned data structure relying on PLAs in any of its components.

Based on our compressibility measures, we analyzed two representative data structures for storing PLAs, namely the one of the LA-vector (compression setting) and the one of the PGM-index (indexing setting), showing that they are both optimal up to a constant factor.

Motivated by this study, we proposed two novel data structures for the above settings, which turn out to be succinct (thus optimal up to lower-order terms) in most practical cases while retaining the same asymptotic query time of the LA-vector and PGM-index. Overall, they offer strong theoretical guarantees and suggest efficient practical implementations, providing valuable tools for practitioners and researchers in learned data structures.

Future works could investigate an extension of our analysis to Piecewise Non-Linear Approximations, for which successful applications already exist [14]. Another interesting direction, complementary to our work, is the implementation of the proposed data structures with a thorough experimental evaluation of their space-time trade-offs.