A Survey of Learned Indexes for the Multi-dimensional Space
Abdullah Al-Mamun Hao Wu Qiyang He Jianguo Wang Walid G. Aref
A recent research trend involves treating database index structures as
Machine Learning (ML) models. In this domain, single or multiple ML models are
trained to learn the mapping from keys to positions inside a data set. This
class of indexes is known as "Learned Indexes." Learned indexes have
demonstrated improved search performance and reduced space requirements for
one-dimensional data. The concept of one-dimensional learned indexes has
naturally been extended to multi-dimensional (e.g., spatial) data, leading to
the development of "Learned Multi-dimensional Indexes". This survey focuses on
learned multi-dimensional index structures. Specifically, it reviews the
current state of this research area, explains the core concepts behind each
proposed method, and classifies these methods based on several well-defined
criteria. We present a taxonomy that classifies and categorizes each learned
multi-dimensional index, and survey the existing literature on learned
multi-dimensional indexes according to this taxonomy. Additionally, we present
a timeline to illustrate the evolution of research on learned indexes. Finally,
we highlight several open challenges and future research directions in this
emerging and highly active field.