A Tour of Learned Static Sorted Sets Dictionaries: From Specific to Generic with an Experimental Performance Analysis

In recent years, in the era of Big Data, studying new methods to improve the performance of well-known procedures, such as searching in a Sorted Set, has become crucial in many fields. A new trend emerging in this scenario combines Machine Learning models with Data Structures, generating the so-called Learned Data Structures. In this thesis, we provide an in-depth experimental study of the use of these models, starting from some evidence known to experts in the field but not experimentally investigated concerning the use of very complex models such as Neural Networks. Then, we document a time/space trade-off scenario that is very important for practitioners and designers users. Furthermore, we investigate a comparison well known in the Literature, i.e., Branchy procedures versus Branch-free ones, and we place it in the context of Learned Data Structures. Finally, considering that the Learned Data Structures currently defined in the Literature only fit with specific Dictionaries and procedures, e.g., Binary Search, we have defined a new type of generic Learned Data Structure that can use a wide range of Dictionaries.