Lower Bounds for the Algorithmic Complexity of Learned Indexes

Luis Alberto Croquevielle, Roman Sokolovskii, Thomas Heinis

Learned index structures aim to accelerate queries by training machine learning models to approximate the rank function associated with a database attribute. While effective in pra…