Upper Bounds for Complexity of Asymptotically Optimal Learned Indexes

• DOI: 10.48550/arxiv.2405.03851
• Publication Date: 2024-05-06
• Authors: Luis Alberto Croq...; Guang Yang; Liang Lian; Ali Hadian; Thomas Heinis
• Keywords: Asymptotically optimal algorithm

Learned indexes leverage machine learning models to accelerate query answering in databases, showing impressive practical performance. However, theoretical understanding of these methods remains incomplete. Existing research suggests that learned have superior asymptotic complexity compared their non-learned counterparts, but findings been established under restrictive probabilistic assumptions. Specifically, for a sorted array with $n$ elements, it has shown can find key $O(\log(\log n))$ expected time using at most linear space, $O(\log n)$ methods. In this work, we prove $O(1)$ be achieved thereby establishing the tightest upper bound so far an asymptotically optimal index. Notably, use weaker assumptions than prior meaning our results generalize previous efforts. Furthermore, introduce new measure statistical data. This metric exhibits information-theoretical interpretation and estimated practice. characterization provides further indexes, by helping explain why some datasets seem particularly challenging