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

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.