AUTONOMOUS, DISTRIBUTED AND PERVASIVE SYSTEMS-1

Anno accademico
2023/2024 Programmi anni precedenti
Titolo corso in inglese
AUTONOMOUS, DISTRIBUTED AND PERVASIVE SYSTEMS-1
Codice insegnamento
PHD156-1 (AF:471254 AR:258248)
Modalità
In presenza
Crediti formativi universitari
2
Livello laurea
Corso di Dottorato (D.M.45)
Settore scientifico disciplinare
INF/01
Periodo
Annuale
Anno corso
1
Sede
VENEZIA
Spazio Moodle
Link allo spazio del corso
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)
Didattica frontale, slides, lavagna.
Inglese
Il programma è ancora provvisorio e potrà subire modifiche.
orale
Programma definitivo.
Data ultima modifica programma: 25/02/2023