Learned Indexes From the One-dimensional to the Multi-dimensional Spaces: Challenges, Techniques, and Opportunities

Recently, the class of learned index structures has emerged as one form of database indexes that make use of Machine Learning (ML) techniques. The learned indexes designed for the one-dimensional space have demonstrated improvements in both the query processing time and the index size. Observing the advantages of one-dimensional learned indexes, various learned indexes have been proposed for the multi-dimensional space. This class of learned indexes is termed ''Learned Multi-dimensional Indexes.'' This tutorial on learned indexes is designed based on our long survey article on the subject [4]. In this tutorial, we use a taxonomy to categorize over 100 learned one- and multi-dimensional indexes with more focus on the class of learned multi-dimensional indexes. The goal of this tutorial is to explain the fundamental techniques behind state-of-the-art learned one- and multi-dimensional indexes with emphasis on the latter, and identify the ongoing challenges and future opportunities for research in this domain.