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

• URL: http://arxiv.org/abs/2506.20139v1
• Date: Wed, 25 Jun 2025 05:20:54 GMT
• Title: Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis
• Authors: Jiayong Qin, Xianyu Zhu, Qiyu Liu, Guangyi Zhang, Zhigang Cai, Jianwei Liao, Sha Hu, Jingshu Peng, Yingxia Shao, Lei Chen,
• Abstract summary: Piecewise Linear Approximation ($epsilon$-PLA) has emerged as a popular choice due to its simplicity and effectiveness.<n>Despite its central role in many learned indexes, the design and analysis of $epsilon$-PLA fitting algorithms remain underexplored.
• Score: 16.350750984598797
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 ($\epsilon$-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 $\epsilon$-PLA fitting algorithms remain underexplored. In this paper, we revisit $\epsilon$-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 \cdot \epsilon^2)$ on the expected segment coverage for existing $\epsilon$-PLA fitting algorithms, where $\kappa$ is a data-dependent constant. We then present a comprehensive benchmark of state-of-the-art $\epsilon$-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.

Related papers

• Learning Identifiable Structures Helps Avoid Bias in DNN-based Supervised Causal Learning [56.22841701016295]
  Supervised Causal Learning (SCL) is an emerging paradigm in this field.<n>Existing Deep Neural Network (DNN)-based methods commonly adopt the "Node-Edge approach"
  arXiv  Detail & Related papers  (2025-02-15T19:10:35Z)
• How to Leverage Demonstration Data in Alignment for Large Language Model? A Self-Imitation Learning Perspective [17.956310574300765]
  This paper introduces a novel generalized self-imitation learning ($textbfGSIL$) framework. It effectively and efficiently aligns large language models with offline demonstration data. $textbfGSIL$ consistently and significantly outperforms baselines in many challenging benchmarks.
  arXiv  Detail & Related papers  (2024-10-14T02:21:29Z)
• Revisiting Nearest Neighbor for Tabular Data: A Deep Tabular Baseline Two Decades Later [76.66498833720411]
  We introduce a differentiable version of $K$-nearest neighbors (KNN) originally designed to learn a linear projection to capture semantic similarities between instances.<n>Surprisingly, our implementation of NCA using SGD and without dimensionality reduction already achieves decent performance on tabular data.<n>We conclude our paper by analyzing the factors behind these improvements, including loss functions, prediction strategies, and deep architectures.
  arXiv  Detail & Related papers  (2024-07-03T16:38:57Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Surprisal Driven $k$-NN for Robust and Interpretable Nonparametric Learning [1.4293924404819704]
  We shed new light on the traditional nearest neighbors algorithm from the perspective of information theory. We propose a robust and interpretable framework for tasks such as classification, regression, density estimation, and anomaly detection using a single model. Our work showcases the architecture's versatility by achieving state-of-the-art results in classification and anomaly detection.
  arXiv  Detail & Related papers  (2023-11-17T00:35:38Z)
• Principled and Efficient Motif Finding for Structure Learning of Lifted Graphical Models [5.317624228510748]
  Structure learning is a core problem in AI central to the fields of neuro-symbolic AI and statistical relational learning. We present the first principled approach for mining structural motifs in lifted graphical models. We show that we outperform state-of-the-art structure learning approaches by up to 6% in terms of accuracy and up to 80% in terms of runtime.
  arXiv  Detail & Related papers  (2023-02-09T12:21:55Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• Learning to Learn Graph Topologies [27.782971146122218]
  We learn a mapping from node data to the graph structure based on the idea of learning to optimise (L2O) The model is trained in an end-to-end fashion with pairs of node data and graph samples. Experiments on both synthetic and real-world data demonstrate that our model is more efficient than classic iterative algorithms in learning a graph with specific topological properties.
  arXiv  Detail & Related papers  (2021-10-19T08:42:38Z)
• DAGs with No Curl: An Efficient DAG Structure Learning Approach [62.885572432958504]
  Recently directed acyclic graph (DAG) structure learning is formulated as a constrained continuous optimization problem with continuous acyclicity constraints. We propose a novel learning framework to model and learn the weighted adjacency matrices in the DAG space directly. We show that our method provides comparable accuracy but better efficiency than baseline DAG structure learning methods on both linear and generalized structural equation models.
  arXiv  Detail & Related papers  (2021-06-14T07:11:36Z)
• The Price of Tailoring the Index to Your Data: Poisoning Attacks on Learned Index Structures [9.567119607658299]
  We present the first study of poisoning attacks on learned index structures. We formulate the first poisoning attacks on linear regression models trained on a cumulative distribution function. We generalize our poisoning techniques to attack a more advanced two-stage design of learned index structures.
  arXiv  Detail & Related papers  (2020-08-01T17:12:04Z)
• Learning Reasoning Strategies in End-to-End Differentiable Proving [50.9791149533921]
  Conditional Theorem Provers learn optimal rule selection strategy via gradient-based optimisation. We show that Conditional Theorem Provers are scalable and yield state-of-the-art results on the CLUTRR dataset.
  arXiv  Detail & Related papers  (2020-07-13T16:22:14Z)
• Stochastic Flows and Geometric Optimization on the Orthogonal Group [52.50121190744979]
  We present a new class of geometrically-driven optimization algorithms on the orthogonal group $O(d)$. We show that our methods can be applied in various fields of machine learning including deep, convolutional and recurrent neural networks, reinforcement learning, flows and metric learning.
  arXiv  Detail & Related papers  (2020-03-30T15:37:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.