Learning-based approaches to compressed data structures design

Abstract

An emerging trend in data structures design consists in introducing learned components so to uncover some new regularities in the input data, and thus enable faster queries and more succinct space usage (sometimes of orders of magnitude) compared to traditional approaches. While the resulting learned data structures are typically difficult to analyse under the classical models of computations, some initial results bound their worst-case performance and build a theoretical foundation for their excellent practical performance. We provide a walkthrough of new theoretical and experimental achievements in this area, and conclude by discussing the plethora of research opportunities that these new learning-based approaches to data structures design open up.