ALGORITHMS FOR MASSIVE DATA

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 infine 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)

Parte I: ripasso

- Teoria delle probabilità (Valore atteso, varianza, variabili casuali, disuguaglianze di Markov, Chebyshev, Chernoff)
- Hashing (universal, tabelle hash)

Parte II: Sketching

- Shingling
- Rabin hashing (identità)
- MinHash (distanza di Jaccard), permutazioni Min-wise
- SimHash (distanza Coseno)
- sketching per distanze di Hamming / Euclidea
- Locality-sensitive hashing (LSH), nearest neighbor search, altre applicazioni
- Bloom filters, Count-min sketch

Parte III: algoritmi su streams

- Il modello stream
- Pattern matching (Algoritmi di Karp-Rabin e Porat-Porat)
- Algoritmo di Morris (conteggio con piccoli registri)
- Algoritmo idealizzato di Flajolet-Martin
- Algoritmo Bottom-k
- La famiglia di algoritmi LogLog
- lower bounds
- Stima di momenti (AMS, tug-of-war, heavy hitters)
- Algoritmo di Datar-Gionis-Indyk-Motwani algorithm (conteggio di eventi in una finestra)


Parte IV: Strutture dati compresse

- Entropia, compressione dati
- bitvector
- wavelet trees
- Suffix array compresso
- FM-index
- Compressione di dati strutturati (grafi)

- 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.

Slide del docente e lavagna.

Inglese

orale