Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913911838605312 |
|---|---|
| author | Qin, Jiayong Zhu, Xianyu Liu, Qiyu Zhang, Guangyi Cai, Zhigang Liao, Jianwei Hu, Sha Peng, Jingshu Shao, Yingxia Chen, Lei |
| author_facet | Qin, Jiayong Zhu, Xianyu Liu, Qiyu Zhang, Guangyi Cai, Zhigang Liao, Jianwei Hu, Sha Peng, Jingshu Shao, Yingxia Chen, Lei |
| contents | 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 $Ω(κ\cdot ε^2)$ on the expected segment coverage for existing $ε$-PLA fitting algorithms, where $κ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_20139 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis Qin, Jiayong Zhu, Xianyu Liu, Qiyu Zhang, Guangyi Cai, Zhigang Liao, Jianwei Hu, Sha Peng, Jingshu Shao, Yingxia Chen, Lei Databases Machine Learning 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 $Ω(κ\cdot ε^2)$ on the expected segment coverage for existing $ε$-PLA fitting algorithms, where $κ$ 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. |
| title | Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis |
| topic | Databases Machine Learning |
| url | https://arxiv.org/abs/2506.20139 |