Learning Data Structures

by Francisco Guilherme Ramilo Caetano Pesquita

MSc thesis presentation and discussion.

Date: 2021-Nov-22   Time: 14:00
Room: Zoom

Abstract: We studied learned data structures, a state-of-the-art development
in searching and data structuring that uses machine learning methods for
pattern recognition in data in an attempt to improve search performance. A
Python implementation of the Recursive Model Index, a key example of such
structures, was completed, with its obstacles catalogued. We overview the
parametrization requirements of Recursive Model Indexes and their performance
relative to the same, regarding staging, stage size, and internal model
choice, and compare the best performing set-ups to traditional search methods,
namely B-trees and binary search. We confirm that the recursive nature of the
RMI offers advantages over single-model options, and that the RMI has
heightened performance over the traditional options considered, both in
standard searching and as a hash function in a hash table.