ADVANCED COMPUTER SCIENCE - MOD. 2

Il corso si propone di introdurre algoritmi e strutture dati efficienti per la rappresentazione e analisi di dati massivi. Mentre tecniche algoritmiche tradizionali richiedono la disponibilità dei dati completi in un formato immediatamente accessibile per l'algoritmo, gli algoritmi presentati in questo corso ricorrono a tecniche di compressione lossy e lossless per rendere possibile l'analisi di dati la cui dimensione eccede la capacità di calcolatori tradizionali. Verranno discusse tecniche di sketching per ridurre (spesso esponenzialmente) la dimensione dei dati analizzati, algoritmi per analizzare stream di dati e strutture dati compresse per rappresentare e manipolare dati in formato compresso.

Lo studente alla fine del corso sarà in grado di applicare tecniche algoritmiche avanzate per analizzare dati di dimensione molto elevata e avrà le basi teoriche necessarie per comprendere in modo indipendente articoli scientifici relativi all'area di ricerca nella quale il corso si inquadra. In particolare, i risultati attesi si dividono in:

1. Conoscenza e comprensione:
Al termine del corso lo studente conoscerà le principali tecniche di sketching, streaming e strutture dati compresse.

2. Capacità di applicare conoscenza e comprensione:
Al termine del corso lo studente sarà in grado di applicare le tecniche algoritmiche apprese (sketching, streaming, strutture compresse) per risolvere problemi tipici di analisi e manipolazione di dati massivi.

3. Capacità di giudizio:
Al termine del corso lo studente sarà in grado di utilizzare le conoscenze acquisite per:
- Identificare l'algoritmo e la struttura dati più adatta a risolvere una determinata problematica nell'ambito dei massive data.
- Analizzare in modo rigoroso le performance di algoritmi randomizzati (runtime, approssimazione, probabilità di successo).
- Leggere e comprendere in modo indipendente articoli di ricerca nel settore.
- Implementare algoritmi esistenti e progettarne di nuovi.

- Teoria delle probabilità (valore atteso, varianza, variabili casuali, eventi)
- Algoritmi e strutture dati (complessità asintotica, strutture dati di base)
- Matematica discreta (aritmetica modulare)

(1) strutture dati lossless

- Introduzione. Basi di teoria dell'informazione (Worst-case Entropy, statistical entropy, compressione dati)
- strutture compresse per insiemi e stringhe (sorted integers, Elias-Fano, succinct bitvectors, wavelet trees)
- Compressed suffix array
- FM-index / r-index
- Indici per grafi e linguaggi regolari

(2) algoritmi e strutture dati lossy

2.1 Ripasso di teoria delle probabilità
- definizioni di base, concentration bounds
- Hashing

2.2 Filtri
- Bloom, counting bloom
- Quotient filters

2.3 Similarity-preserving sketching
- Rabin hashing, Shingling
- MinHash (Jaccard distance), permutazioni Min-wise.
- locality-sensitive hashing
- nearest neighbor search

2.4 Pattern matching su streams
- Pattern matching & streaming, algoritmo di Karp-Rabin
- Algoritmo di Porat-Porat's
- Estensioni ad approximate pattern matching (Hamming distance)

2.5 Sketching su streams
- Algoritmo di Morris
- Algoritmo di Flajolet-Martin, Algoritmo Bottom-k
- Algoritmi Tidemark, BJKST
- Frequent itemsets. Algoritmo di Misra-Gries
- Algoritmo Tug-of-war algorithm e dimensionality reduction
- Higher moments - Algoritmo AMS
- Algoritmo di Datar-Gionis-Indyk-Motwani e estensioni

- Rajaraman, A. and Ullman, J.D., 2011. Mining of massive datasets. Cambridge University Press. http://www.mmds.org/
- Dispense del docente: https://arxiv.org/abs/2301.00754
- Chakrabarti, Amit, 2020. Data stream algorithms - lecture notes: https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf
- Navarro, Gonzalo, 2016. Compact data structures: a practical approach. Cambridge University Press.
- slides del docente e articoli originali di ricerca

L'esame consiste in una prova orale individuale in cui verrà testata la conoscenza dei contenuti del corso.

orale

Slide del docente e lavagna.