logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-09112020-150355


Tipo di tesi
Tesi di laurea magistrale
Autore
BOFFA, ANTONIO
URN
etd-09112020-150355
Titolo
Spreading the learned approach to succint data structures
Dipartimento
INFORMATICA
Corso di studi
INFORMATICA
Relatori
relatore Prof. Ferragina, Paolo
relatore Dott. Vinciguerra, Giorgio
Parole chiave
  • compressed
  • data
  • learned
  • rank
  • select
  • structure
  • succinct
Data inizio appello
09/10/2020
Consultabilità
Completa
Riassunto
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.
File