AUTONOMOUS, DISTRIBUTED AND PERVASIVE SYSTEMS-1

Il termine "big data" indica dati di dimensioni così elevate da non poter essere immagazzinati e processati con tecniche algoritmiche tradizionali. Spesso, però, la dimensione di questi dati non riflette il loro effettivo contenuto informativo. Si pensi al sequenziamento di DNA: un genoma umano richiede circa 1GB di spazio per essere memorizzato, e tecniche moderne permettono di sequenziare decine di genomi in pochi giorni. Chiaramente, tecniche algoritmiche tradizionali non scalano: tutti i genomi italiani, per esempio, richiederebbero circa 60 Petabyte solo per essere immagazzinati. Due genomi umani qualsiasi sono però simili al 99.99%: la chiave è la compressione. Il problema è: possiamo sviluppare algoritmi che operano direttamente su dati compressi (senza passare per la fase di decompressione)?

Il corso affronta la tematica della rappresentazione e manipolazione di grosse quantità di dati tramite l'utilizzo di strutture dati compresse. Questo settore di ricerca unisce tecniche provenienti da algoritmi e strutture dati e da teoria dell'informazione per ottenere strutture dati in grado, simultaneamente, di accelerare operazioni tipiche dell'information retrieval e occupare uno spazio proporzionale ai dati compressi (fino a migliaia di volte inferiore ai dataset originali).

Alla fine del corso, lo studente sarà in grado di:
1) comprendere le principali tecniche di compressione lossless tipicamente utilizzate per rappresentare dati non strutturati (stringhe) e strutturati (e.g. alberi, grafi).
2) comprendere la relazione esistente tra compressione e computazione, e come questa possa essere utilizzata per accelerare operazioni su dati compressi.
3) implementare semplici strutture dati compresse

conoscenze base di:
- algoritmi e strutture dati (e.g. sorting, hashing, binary search, big-O notation)
- teoria delle probabilità

1) Entropia, teorema di Shannon, codici prefix-free, compressione
2) Bitvector con rank/select/access, wavelet trees, strutture dati geometriche
3) Compressed suffix arrays, FM-index, Burrows-Wheeler transform
4) Indici basati sui compressori Lempel-Ziv

- Navarro, Gonzalo. Compact data structures: A practical approach. Cambridge University Press, 2016.
- original research articles

Una delle seguenti:
- lettura e discussione di un articolo del settore
- implementazione di una struttura dati compressa in C++
- ricerca (sviluppo/implementazione di una nuova tecnica che può portare a una pubblicazione)

orale

Didattica frontale, slides, lavagna.

Il programma è ancora provvisorio e potrà subire modifiche.