Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations
Paolo Ferragina, Filippo Lari · 2025
Read Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations by Paolo Ferragina, Filippo Lari (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-07827.txt.
Introduction
Paolo Ferragina and 1 co-author ask how small a piecewise linear approximation can possibly be, in a 2025 computer science paper. Such approximations summarise rising two-dimensional data with a chain of straight segments that stay within a set error. Learned data structures use them to store and search large datasets quickly.
The authors derive the first lower bounds on storage cost for these approximations, covering both compression and indexing settings. They then compare the bounds against known data structures to see which designs already sit near the limit. Knowing the floor matters: it tells engineers when a cleverer encoding can still save space and when the remaining cost is forced by the data itself.
Catalog record
| CREATOR | Paolo Ferragina, Filippo Lari |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-07827
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Compressibility Measures and Succinct Data Structures for Piecewise Linear Approximations Paolo Ferragina, Filippo Lari Abstract We study the problem of deriving compressibility measures for Piecewise Linear Approximations (PLAs), i.e., error-bounded approximations of a set of two-dimensional increasing data points using a sequence of segments. Such approximations are widely used tools in implementing many learned data structures , which mix learning models with traditional algorithmic design blocks to exploit regularities in the underlying data distribution, providing novel and effective space-time trade-offs. We introduce the first lower bounds to the cost of storing PLAs in two settings, namely compression and indexing . We then compare these compressibility measures to known data structures, and show that they are asymptotically optimal up to a constant factor from the space lower bounds. Finally, we design the first data structures for the aforementioned settings that achieve the space lower bounds plus small additive terms, which turn out to be succinct in most practical cases. Our data structures support the efficient retrieval and evaluation of a segment in the (compressed) PLA for a given x x -value, which is a core operation in any learned data structure relying on PLAs. As a result, our paper offers the first theoretical analysis of the maximum compressibility achievable by PLA-based learned data structures, and provides novel storage schemes for PLAs offering strong theoretical guarantees while also suggesting simple and efficient practical implementations. Department L’EMbeDS, Sant’Anna School of Advanced Studies, Pisa, Italy Department of Computer Science, University of Pisa, [email protected]://orcid.org/0000-0003-1353-360X Department of Computer Science, University of Pisa, [email protected]://orcid.org/0009-0000-6817-6561 ccs Theory of computation Design and analysis of algorithms ccs Theory of computation Data compression ccs Information systems Information retrieval keywords Piecewise Linear Approximations, Succinct Data Structures, Lower Bounds † † runningauthor: P. Ferragina and F. Lari † † copyright: Paolo Ferragina and Filippo Lari † † funding: The work of P.F. was partially supported by the Alfred P. Sloan Foundation with the grant #G-2025-25193 ( sloan.org ). The work of both authors has been supported by the NextGenerationEU – National Recovery and Resilience Plan (Piano Nazionale di Ripresa e Resilienza, PNRR) – Project: “SoBigData.it - Strengthening the Italian RI for Social Mining and Big Data Analytics” – Prot. IR0000013 – Avviso n. 3264 del 28/12/2021; and by the European Union – Horizon 2020 Program under the scheme “INFRAIA-01-2018-2019 – Integrating Activities for Advanced Communities”, Grant Agreement n. 871042, “SoBigData++: European Integrated Infrastructure for Social Mining and Big Data Analytics” (http://www.sobigdata.eu). † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction 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 [ 14 ] , 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 [ 19 ] . 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 [ 13 ] , string indexing [ 23 ] , one-dimensional indexing [ 14 , 12 ] , multi-dimensional indexing [ 16 , 4 ] , range minimum queries [ 8 ] , monotone minimal perfect hashing [ 9 ] , and range filtering [ 22 ] , 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 \ell as a function of the sequence length n and the maximum allowed error \varepsilon , 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. [ 10 ] 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 \ell is \Theta(n/\varepsilon^{2}) with high probability. Later works [ 24 , 3 ] provided better upper bounds, however, their PLAs were restricted to be formed by horizontal segments . As far as lower bounds are concerned, we mention the work of Zeighami and Shahabi [ 25 ] which was the first to limit from below the model size (e.g., the number of segments \ell in a PLA or the number of neurons in a neural network) of any learned data structure achieving a given desired accuracy \varepsilon 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 \ell forming an optimal PLA is known (e.g., computed by [ 19 ] ), 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 [ 12 ] (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. 2 Background 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 S=1\leq x_{1}<x_{2}<\dots<x_{n}\leq u of n elements drawn from a finite integer universe U of size u