# Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis

arXiv: https://arxiv.org/abs/2506.20139 · HTML: https://mlsanity.com/paper/2506.20139/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 60 references that are in the map.
- First posted on arXiv 25 Jun 2025.

## Builds on (most cited first, 15 of 15)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [ALEX: An Updatable Adaptive Learned Index](https://mlsanity.com/paper/1905.08898/) (2019)
- [FITing-Tree: A Data-aware Index Structure](https://mlsanity.com/paper/1801.10207/) (2018)
- [Benchmarking Learned Indexes](https://mlsanity.com/paper/2006.12804/) (2020)
- [The PGM-index: a multicriteria, compressed and learned approach to data indexing](https://mlsanity.com/paper/1910.06169/) (2019)
- [Time series compression: a survey](https://mlsanity.com/paper/2101.08784/) (2021)
- [Meta-Learning Neural Bloom Filters](https://mlsanity.com/paper/1906.04304/) (2019)
- [CARMI: A Cache-Aware Learned Index with a Cost-based Construction Algorithm](https://mlsanity.com/paper/2103.00858/) (2021)
- [Are Updatable Learned Indexes Ready?](https://mlsanity.com/paper/2207.02900/) (2022)
- [Why Are Learned Indexes So Effective but Sometimes Ineffective?](https://mlsanity.com/paper/2410.00846/) (2024)
- [Techniques for Inverted Index Compression](https://mlsanity.com/paper/1908.10598/) (2019)
- [Optimal Segmented Linear Regression for Financial Time Series Segmentation](https://mlsanity.com/paper/2101.00370/) (2021)
- [Fast Parallel Operations on Search Trees](https://mlsanity.com/paper/1510.05433/) (2015)
- [Learned Data Compression: Challenges and Opportunities for the Future](https://mlsanity.com/paper/2412.10770/) (2024)

## Abstract (arXiv)

A growing trend in the database and system communities is to augment conventional index structures, such as B+-trees, with machine learning (ML) models. Among these, error-bounded Piecewise Linear Approximation (ε-PLA) has emerged as a popular choice due to its simplicity and effectiveness. Despite its central role in many learned indexes, the design and analysis of ε-PLA fitting algorithms remain underexplored. In this paper, we revisit ε-PLA from both theoretical and empirical perspectives, with a focus on its application in learned index structures. We first establish a fundamentally improved lower bound of Omega(kappa · ε2) on the expected segment coverage for existing ε-PLA fitting algorithms, where kappa is a data-dependent constant. We then present a comprehensive benchmark of state-of-the-art ε-PLA algorithms when used in different learned data structures. Our results highlight key trade-offs among model accuracy, model size, and query performance, providing actionable guidelines for the principled design of future learned data structures.