提出更优的分段线性逼近理论下界，指导学习型索引设计。
Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis
- 建立现有分段线性逼近算法的期望段覆盖理论下界
- 实测显示模型精度、大小与查询性能存在关键权衡
- 为未来学习型索引设计提供可落地的优化指南
数据库领域正越来越多地用机器学习模型增强传统索引结构（如B+-树）。其中，误差有界的分段线性逼近（ε-PLA）因其简单有效而广受青睐。尽管ε-PLA在诸多学习型索引中扮演核心角色，其拟合算法的设计与分析仍缺乏深入研究。本文从理论和实证两方面重新审视ε-PLA在学习型索引中的应用。首先，我们建立了现有ε-PLA拟合算法期望段覆盖的改进下界Ω(κ·ε²)，其中κ为依赖数据的常数。随后，我们对主流ε-PLA算法在不同学习型数据结构中的表现进行了全面基准测试。结果揭示了模型精度、模型规模与查询性能之间的关键权衡，为未来学习型数据结构的合理设计提供了实用指导。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。