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 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)
- fondamenti di programmazione C oppure C++
- Matematica discreta (aritmetica modulare, combinatoria)

(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, zero-order compressed bitvectors, wavelet trees)
- Compressed suffix array
- FM-index

(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
- Estensioni ad approximate pattern matching (Hamming distance)

2.5 Sketching su streams
- Algoritmo di Morris
- Algoritmo di Flajolet-Martin
- Frequent itemsets. Algoritmo di Misra-Gries
- Algoritmo Tug-of-war e dimensionality reduction
- Algoritmo di Datar-Gionis-Indyk-Motwani e estensioni

- Dispense del docente: https://arxiv.org/abs/2301.00754
- Articoli originali di ricerca forniti durante il corso

L'esame è composto da due parti:

1. Una prova orale individuale obbligatoria che mira ad accertare la conoscenza degli argomenti del corso. La valutazione massima ottenibile con la prova orale è 30. Obiettivo della prova orale è verificare la conoscenza degli strumenti teorici illustrati durante il corso, nonché la capacità di applicarli in contesti applicativi collegati agli algoritmi per dati massivi. La valutazione di questa parte dell'esame è formulata secondo questo schema: (1) conoscenze (enunciati e dimostrazioni dei risultati teorici) e capacità di applicare le conoscenze nella soluzione di esercizi (range 40%), (2) dettaglio e completezza delle risposte (range 40%), (3) capacità di comunicazione, compreso l'uso di terminologia specifica relativa ad algoritmi e strutture di dati per dati massivi (range 20%).

2. Progetto individuale facoltativo. Il progetto consente allo studente di ottenere un punteggio di (al massimo) 5 punti aggiuntivi rispetto al voto della prova orale. Il progetto consiste in un problema (challenge) relativo all'elaborazione di dati massivi e richiede l'implementazione di software (nei linguaggi C o C++) per essere risolto, oltre ad una breve descrizione della soluzione proposta. Le soluzioni degli studenti verranno confrontate in una gara (competizione), valutando la qualità (accuratezza) della soluzione calcolata dal software, nonché il suo utilizzo di risorse computazionali (memoria e la velocità). La valutazione di questa parte dell'esame è formulata secondo questo schema: (1) posizionamento della soluzione nella classifica della competizione (range 80%), (2) originalità della soluzione (range 20%).

La lode (30 e lode) verrà assegnata agli studenti che hanno ottenuto una valutazione di 30 nella prova orale e che hanno risolto il progetto con un'ottima soluzione (ottenendo 5 punti extra).

I contenuti del corso vengono presentati tramite l'uso della lavagna e del proiettore.

Inglese

orale