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.

Conoscenza e comprensione
Il laureato/la laureata magistrale:

- conosce le metodologie di progettazione e sviluppo di sistemi informatici relativi a Data Engineering;
- conosce le tecniche per la valutazione delle prestazioni, della scalabilità, e dell'affidabilità di software e algoritmi per analizzare dati massivi;

- sviluppa le proprie competenze nell'ambito della programmazione acquisendo padronanza delle tecniche di calcolo e la conoscenza di algoritmi, allo stato dell'arte;
- conosce ambienti di programmazione e algoritmi per l’analisi di dati massivi;

Capacità di applicare conoscenza e comprensione
Il laureato/la laureata magistrale:
- è in grado di progettare e sviluppare sistemi per la memorizzazione, gestione e analisi di dati su larga scala;
- è in grado di progettare e valutare sistemi altamente scalabili;
- è in grado di usare tecniche di programmazione avanzata negli ambiti del calcolo ad alte prestazioni e algoritmi per l'analisi di elevate moli di dati;

- è in grado di verificare i requisiti funzionali e non funzionali (prestazioni) di un algoritmo;
- è in grado di accedere alla letteratura scientifica per individuare potenziali soluzioni a problemi con metodi innovativi allo stato dell'arte.

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