Time for learned data structures

Abstract

An emerging trend in data structure design shows that incorporating machine learning models into data structures enables them to adapt to the underlying data distribution and significantly surpass the space-time efficiency of traditional approaches. In this seminar, we provide an overview of several classic data-structuring problems—such as data indexing, compression, and hashing—where the learning-based approaches have proven effective, even breaking known lower bounds. We will emphasize key design considerations, including model selection and error handling. Additionally, we review some theoretical foundations and empirical results that demonstrate the performance gains of these techniques, and conclude by discussing some promising research opportunities they offer.