Pith. sign in

REVIEW 61 references

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

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2506.20139 v1 pith:THM4IIEA submitted 2025-06-25 cs.DB cs.LG

Jiayong Qin , Xianyu Zhu , Qiyu Liu , Guangyi Zhang , Zhigang Cai , Jianwei Liao , Sha Hu , Jingshu Peng
show 2 more authors
Yingxia Shao Lei Chen
This is my paper · ORCID
classification cs.DBcs.LG
keywords epsilonlearnedstructuresalgorithmsindexanalysisapproximationdata
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

61 extracted references · 57 canonical work pages

  1. [1]

    The case for learned index structures,

    T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis, “The case for learned index structures,” inProceedings of the 2018 international conference on management of data, 2018, pp. 489–504

    work page 2018

  2. [2]

    A model for learned bloom filters and optimizing by sandwiching,

    M. Mitzenmacher, “A model for learned bloom filters and optimizing by sandwiching,”Advances in Neural Information Processing Systems, vol. 31, 2018

    work page 2018

  3. [3]

    Effectively learning spatial indices,

    J. Qi, G. Liu, C. S. Jensen, and L. Kulik, “Effectively learning spatial indices,”Proceedings of the VLDB Endowment, vol. 13, no. 12, pp. 2341–2354, 2020

    work page 2020

  4. [4]

    Benchmarking learned indexes,

    R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska, “Benchmarking learned indexes,”Proceed- ings of the VLDB Endowment, vol. 14, no. 1, pp. 1–13, 2020

    work page 2020

  5. [5]

    Are up- datable learned indexes ready?

    C. Wongkham, B. Lu, C. Liu, Z. Zhong, E. Lo, and T. Wang, “Are up- datable learned indexes ready?”Proceedings of the VLDB Endowment, vol. 15, no. 11, pp. 3004–3017, 2022

    work page 2022

  6. [6]

    The pgm-index: a fully-dynamic com- pressed learned index with provable worst-case bounds,

    P. Ferragina and G. Vinciguerra, “The pgm-index: a fully-dynamic com- pressed learned index with provable worst-case bounds,”Proceedings of the VLDB Endowment, vol. 13, no. 8, pp. 1162–1175, 2020

    work page 2020

  7. [7]

    Deep learning,

    Y . LeCun, Y . Bengio, and G. Hinton, “Deep learning,”nature, vol. 521, no. 7553, pp. 436–444, 2015

    2015

  8. [8]

    Why are learned indexes so effective?

    P. Ferragina, F. Lillo, and G. Vinciguerra, “Why are learned indexes so effective?” inInternational Conference on Machine Learning. PMLR, 2020, pp. 3123–3132

    work page 2020

Show all 61 references
  1. [9]

    Fiting-tree: A data-aware index structure,

    A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska, “Fiting-tree: A data-aware index structure,” inProceedings of the 2019 international conference on management of data, 2019, pp. 1189–1206

    2019

  2. [10]

    Learned index with dynamicϵ,

    D. Chen, W. Li, Y . Li, B. Ding, K. Zeng, D. Lian, and J. Zhou, “Learned index with dynamicϵ,” inICLR. OpenReview.net, 2023

    2023

  3. [11]

    From{WiscKey}to bourbon: A learned index for{Log-Structured}merge trees,

    Y . Dai, Y . Xu, A. Ganesan, R. Alagappan, B. Kroth, A. Arpaci-Dusseau, and R. Arpaci-Dusseau, “From{WiscKey}to bourbon: A learned index for{Log-Structured}merge trees,” in14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), 2020, pp. 155–171

    2020

  4. [12]

    Lhist: towards learning multi-dimensional histogram for massive spatial data,

    Q. Liu, Y . Shen, and L. Chen, “Lhist: towards learning multi-dimensional histogram for massive spatial data,” in2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 2021, pp. 1188–1199

    2021

  5. [13]

    HAP: an efficient hamming space index based on augmented pigeonhole principle,

    ——, “HAP: an efficient hamming space index based on augmented pigeonhole principle,” inProceedings of the 2022 International Confer- ence on Management of Data, 2022, pp. 917–930

    2022

  6. [14]

    Bittuner: A toolbox for automatically configuring learned data compressors,

    Q. Liu, Y . Luo, M. Cui, S. Han, J. Peng, J. Li, and L. Chen, “Bittuner: A toolbox for automatically configuring learned data compressors,” in 2025 IEEE 41st International Conference on Data Engineering (ICDE). IEEE Computer Society, 2025, pp. 4548–4551

    2025

  7. [15]

    Learned data compression: Challenges and opportunities for the future,

    Q. Liu, S. Han, J. Liao, J. Li, J. Peng, J. Du, and L. Chen, “Learned data compression: Challenges and opportunities for the future,”arXiv preprint arXiv:2412.10770, 2024

    2024 arXiv

  8. [16]

    Organization and maintenance of large ordered indices,

    R. Bayer and E. McCreight, “Organization and maintenance of large ordered indices,” inProceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, 1970, pp. 107–141

    1970

  9. [17]

    An on-line algorithm for fitting straight lines between data ranges,

    J. O’Rourke, “An on-line algorithm for fitting straight lines between data ranges,”Commun. ACM, vol. 24, no. 9, pp. 574–578, 1981

    1981

  10. [18]

    Maximum error- bounded piecewise linear representation for online stream approxima- tion,

    Q. Xie, C. Pang, X. Zhou, X. Zhang, and K. Deng, “Maximum error- bounded piecewise linear representation for online stream approxima- tion,”VLDB J., vol. 23, no. 6, pp. 915–937, 2014

    2014

  11. [19]

    Piece-wise linear approximations,

    S. H. Cameron, “Piece-wise linear approximations,”Technical note CSTN-106, Computer Sciences Division, IIT Research Institute, Chicago, IL, 1966

    1966

  12. [20]

    Time series compression survey,

    G. Chiarot and C. Silvestri, “Time series compression survey,”ACM Computing Surveys, vol. 55, no. 10, pp. 1–32, 2023

    2023

  13. [21]

    Online piece-wise linear approximation of numerical streams with precision guarantees,

    H. Elmeleegy, A. K. Elmagarmid, E. Cecchet, W. G. Aref, and W. Zwaenepoel, “Online piece-wise linear approximation of numerical streams with precision guarantees,”Proceedings of the VLDB Endow- ment, vol. 2, no. 1, pp. 145–156, 2009

    2009

  14. [22]

    A learned approach to design compressed rank/select data structures,

    A. Boffa, P. Ferragina, and G. Vinciguerra, “A learned approach to design compressed rank/select data structures,”ACM Transactions on Algorithms (TALG), vol. 18, no. 3, pp. 1–28, 2022

    2022

  15. [23]

    Techniques for inverted index compres- sion,

    G. E. Pibiri and R. Venturini, “Techniques for inverted index compres- sion,”ACM Computing Surveys (CSUR), vol. 53, no. 6, pp. 1–36, 2020

    2020

  16. [24]

    Handbook of stochastic methods for physics, chemistry and the natural sciences,

    C. W. Gardiner, “Handbook of stochastic methods for physics, chemistry and the natural sciences,”Springer series in synergetics, 1985

    1985

  17. [25]

    Redner,A guide to first-passage processes

    S. Redner,A guide to first-passage processes. Cambridge university press, 2001

    2001

  18. [26]

    J. E. Gentle,Computational statistics. Springer, 2009, vol. 308

    2009

  19. [27]

    Entropic central limit theorem for order statistics,

    M. Cardone, A. Dytso, and C. Rush, “Entropic central limit theorem for order statistics,”IEEE Transactions on Information Theory, vol. 69, no. 4, pp. 2193–2205, 2022

    2022

  20. [28]

    Fast parallel operations on search trees,

    Y . Akhremtsev and P. Sanders, “Fast parallel operations on search trees,” in2016 IEEE 23rd International Conference on High Performance Computing (HiPC). IEEE, 2016, pp. 291–300

    2016

  21. [29]

    PGM-Index,

    “PGM-Index,” https://github.com/gvinciguerra/PGM-index, accessed: 2025-06-10

    2025

  22. [30]

    STX B+ Tree C++ template classes,

    “STX B+ Tree C++ template classes,” https://panthema.net/2007/ stx-btree/, accessed: 2025-06-10

    2007

  23. [31]

    Benchmarking learned indexes,

    R. Marcus, A. Kipf, A. van Renen, M. Stoian, S. Misra, A. Kemper, T. Neumann, and T. Kraska, “Benchmarking learned indexes,”Proc. VLDB Endow., vol. 14, no. 1, p. 1–13, Sep. 2020

    2020

  24. [32]

    Efficiently searching in-memory sorted arrays: Revenge of the interpolation search?

    P. Van Sandt, Y . Chronis, and J. M. Patel, “Efficiently searching in-memory sorted arrays: Revenge of the interpolation search?” in Proceedings of the 2019 International Conference on Management of Data, ser. SIGMOD ’19, New York, NY , USA, 2019, p. 36–53. [Online]. Available...

    2019

  25. [33]

    Openstreetmap,

    openstreetmap, “Openstreetmap,” [n.d.]. [Online]. Available: https: //www.openstreetmap.org/

  26. [34]

    Why are learned indexes so effective but sometimes ineffective?

    Q. Liu, S. Han, Y . Qi, J. Peng, J. Li, L. Lin, and L. Chen, “Why are learned indexes so effective but sometimes ineffective?”arXiv preprint arXiv:2410.00846, 2024

    2024 arXiv

  27. [35]

    Adaptive sequential segmentation of piecewise stationary time series,

    U. Appel and A. V . Brandt, “Adaptive sequential segmentation of piecewise stationary time series,”Information sciences, vol. 29, no. 1, pp. 27–56, 1983

    1983

  28. [36]

    On the approximation of curves by line segments using dynamic programming,

    R. Bellman, “On the approximation of curves by line segments using dynamic programming,”Communications of the ACM, vol. 4, no. 6, p. 284, 1961

    1961

  29. [37]

    Computing unrestricted synopses under maximum error bound,

    C. Pang, Q. Zhang, X. Zhou, D. Hansen, S. Wang, and A. Maeder, “Computing unrestricted synopses under maximum error bound,”Algo- rithmica, vol. 65, pp. 1–42, 2013

    2013

  30. [38]

    Wavelet synopses for general error metrics,

    M. Garofalakis and A. Kumar, “Wavelet synopses for general error metrics,”ACM Transactions on Database Systems (TODS), vol. 30, no. 4, pp. 888–928, 2005

    2005

  31. [39]

    An online pla algorithm with maximum error bound for generating optimal mixed- segments,

    H. Zhao, T. Li, G. Chen, Z. Dong, M. Bo, and C. Pang, “An online pla algorithm with maximum error bound for generating optimal mixed- segments,”International Journal of Machine Learning and Cybernetics, vol. 11, pp. 1483–1499, 2020

    2020

  32. [40]

    Efficient algorithms for sequence segmen- tation,

    E. Terzi and P. Tsaparas, “Efficient algorithms for sequence segmen- tation,” inProceedings of the 2006 SIAM International Conference on Data Mining. SIAM, 2006, pp. 316–327

    2006

  33. [41]

    Optimal segmented linear re- gression for financial time series segmentation,

    C.-J. Wu, W.-S. Zeng, and J.-M. Ho, “Optimal segmented linear re- gression for financial time series segmentation,” in2021 International Conference on Data Mining Workshops (ICDMW), 2021, pp. 623–630

    2021

  34. [42]

    Segmenting time series: A survey and novel approach,

    E. Keogh, S. Chu, D. Hart, and M. Pazzani, “Segmenting time series: A survey and novel approach,”Data Mining in Time Series Databases, vol. 57, 03 2003

    2003

  35. [43]

    Novel online methods for time series segmentation,

    X. Liu, Z. Lin, and H. Wang, “Novel online methods for time series segmentation,”IEEE Transactions on Knowledge and Data Engineering, vol. 20, no. 12, pp. 1616–1626, 2008

    2008

  36. [44]

    A novel segmentation and representation approach for streaming time series,

    Y . Hu, P. Guan, P. Zhan, Y . Ding, and X. Li, “A novel segmentation and representation approach for streaming time series,”IEEE Access, vol. 7, pp. 184 423–184 437, 2019

    2019

  37. [45]

    A novel bounded-error piece- wise linear approximation algorithm for streaming sensor data in edge computing,

    J.-W. Lin, S.-w. Liao, and F.-Y . Leu, “A novel bounded-error piece- wise linear approximation algorithm for streaming sensor data in edge computing,” inAdvances in Intelligent Networking and Collaborative Systems, L. Barolli, H. Nishino, and H. Miwa, Eds. Cham: Springer Inter...

    2020

  38. [46]

    Ubiquitous b-tree,

    D. Comer, “Ubiquitous b-tree,”ACM Comput. Surv., vol. 11, no. 2, p. 121–137, Jun. 1979

    1979

  39. [47]

    Fast: fast architecture sensitive tree search on modern cpus and gpus,

    C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V . W. Lee, S. A. Brandt, and P. Dubey, “Fast: fast architecture sensitive tree search on modern cpus and gpus,” inProceedings of the 2010 ACM SIGMOD International Conference on Management of Data, ser. SIGM...

    2010

  40. [48]

    Wormhole: A fast ordered index for in- memory data management,

    X. Wu, F. Ni, and S. Jiang, “Wormhole: A fast ordered index for in- memory data management,” ser. EuroSys ’19. New York, NY , USA: Association for Computing Machinery, 2019

    2019

  41. [49]

    Alex: an updatable adaptive learned index,

    J. Ding, U. F. Minhas, J. Yu, C. Wang, J. Do, Y . Li, H. Zhang, B. Chandramouli, J. Gehrke, D. Kossmannet al., “Alex: an updatable adaptive learned index,” inProceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020, pp. 969–984

    2020

  42. [50]

    Xindex: a scalable learned index for multicore data storage,

    C. Tang, Y . Wang, Z. Dong, G. Hu, Z. Wang, M. Wang, and H. Chen, “Xindex: a scalable learned index for multicore data storage,” in Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’20. New York, NY , USA: Association...

    2020

  43. [51]

    Finedex: a fine-grained learned index scheme for scalable and concurrent memory systems,

    P. Li, Y . Hua, J. Jia, and P. Zuo, “Finedex: a fine-grained learned index scheme for scalable and concurrent memory systems,”Proc. VLDB Endow., vol. 15, no. 2, p. 321–334, Oct. 2021

    2021

  44. [52]

    G-learned index: Enabling efficient learned index on gpu,

    J. Liu, F. Zhang, L. Lu, C. Qi, X. Guo, D. Deng, G. Li, H. Zhang, J. Zhai, H. Zhang, Y . Chen, A. Pan, and X. Du, “G-learned index: Enabling efficient learned index on gpu,”IEEE Transactions on Parallel and Distributed Systems, vol. 35, no. 6, pp. 950–967, 2024

    2024

  45. [53]

    Carmi: a cache-aware learned index with a cost- based construction algorithm,

    J. Zhang and Y . Gao, “Carmi: a cache-aware learned index with a cost- based construction algorithm,”Proc. VLDB Endow., vol. 15, no. 11, p. 2679–2691, Jul. 2022

    2022

  46. [54]

    Making in-memory learned indexes efficient on disk,

    J. Zhang, K. Su, and H. Zhang, “Making in-memory learned indexes efficient on disk,”Proc. ACM Manag. Data, vol. 2, no. 3, May 2024

    2024

  47. [55]

    Ferragina, Paoloand Vinciguerra,Learned Data Structures

    G. Ferragina, Paoloand Vinciguerra,Learned Data Structures. Cham: Springer International Publishing, 2020, pp. 5–41

    2020

  48. [56]

    Semantic hashing,

    R. Salakhutdinov and G. Hinton, “Semantic hashing,”International Journal of Approximate Reasoning, vol. 50, no. 7, pp. 969–978, 2009, special Section on Graphical Models and Information Retrieval

    2009

  49. [57]

    Spectral hashing,

    Y . Weiss, A. Torralba, and R. Fergus, “Spectral hashing,” inProceedings of the 22nd International Conference on Neural Information Processing Systems, ser. NIPS’08. Red Hook, NY , USA: Curran Associates Inc., 2008, p. 1753–1760

    2008

  50. [58]

    A model for learned bloom filters, and optimizing by sandwiching,

    M. Mitzenmacher, “A model for learned bloom filters, and optimizing by sandwiching,” inProceedings of the 32nd International Conference on Neural Information Processing Systems, ser. NIPS’18. Red Hook, NY , USA: Curran Associates Inc., 2018, p. 462–471

    2018

  51. [59]

    Meta-learning neural bloom filters,

    J. Rae, S. Bartunov, and T. Lillicrap, “Meta-learning neural bloom filters,” inInternational Conference on Machine Learning. PMLR, 2019, pp. 5271–5280

    2019

  52. [60]

    Stable learned bloom filters for data streams,

    Q. Liu, L. Zheng, Y . Shen, and L. Chen, “Stable learned bloom filters for data streams,”Proceedings of the VLDB Endowment, vol. 13, no. 12, pp. 2355–2367, 2020

    2020

  53. [61]

    Learning-based fre- quency estimation algorithms

    C.-Y . Hsu, P. Indyk, D. Katabi, and A. Vakilian, “Learning-based fre- quency estimation algorithms.” inInternational Conference on Learning Representations, 2019

    2019

Pith tools