Thomas Heinis

Beyond Logarithmic Bounds: Querying in Constant Expected Time with Learned Indexes

2024 · arXiv (Cornell University)

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 indexes have superior asymptotic complexity compared …