• compressed
• data
• learned
• rank
• select
• structure
• succinct

Abstract
In this thesis, I address the well-known problem of designing, implementing and experimenting compressed data structures. Following a recent line of research on the so-called learned data structures, I apply machine learning concepts to data compression and so I introduce the first learned and compressed data structure.
Furthermore, I studied the theoretical background behind the effectiveness of this new kind of data structures.
In the end, I corroborate these theoretical results with a large set of experiments over datasets originating from a variety of sources, and I show that a carefully engineered version of this solution provides new interesting space-time trade-offs with respect to well-established implementations of Elias-Fano, RRR-vector, and random-access vectors of Elias -gamma and -delta coded gaps.

Riassunto
In questa tesi affronto il ben noto problema di progettare, implementare e sperimentare strutture date compresse. Seguendo un recente filone di ricerca chiamato "learned data structures", applico tecniche di apprendimento automatico alla compressione dati introducento quindi la prima struttura dati "learned" e compressa.
Inoltre studio i retroscena dell'efficacia di questo nuovo tipo di strutture dati.
In conclusione, avvaloro questi risultati teorici con un grande numero di esperimenti su insiemi di dati provenienti da fonti variegate e mostro come versioni della soluzione proposta attentamente ingegnerizzate forniscono nuovi compromessi interessanti rispetto a solide implementazioni di Elias-Fano, RRR-vector e vettori compressi con Elias -gamma e -delta code.