ALGORITHMS FOR MASSIVE DATA

Il corso introduce 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.

La padronanza di questi prerequisiti è condizione necessaria per una proficua frequenza del corso. Gli studenti che presentassero lacune in merito sono caldamente invitati a colmarle preventivamente, così da garantire la piena comprensione delle lezioni.

- Teoria della probabilità (argomenti trattati in CT0675)
- Algoritmi e strutture dati (argomenti trattati in CT0667)
- Programmazione, preferibilmente in C/C++ (argomenti trattati in CT0665 e CT0664)
- Matematica discreta (argomenti trattati in CT0434)

(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 filters, counting Bloom filters
- 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
- Stima delle frequenze su uno stream: sampling, count-min sketch, Misra-Gries sketch
- Stima degli elementi distinti (momento di frequenza zero): Flajolet-Martin sketch
- Stima del numero di eventi (primo momento di frequenza): Morris sketch
- Stima del secondo momento di frequenza: Tug-of-war sketch
- Applicazioni: dimensionality reduction, sketches for relational algebra

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

L'esame è composto da due parti, entrambe obbligatorie:

1. Progetto individuale. Il punteggio massimo ottenibile con il progetto è 15. Lo studente dovrà individuare un problema interessante nell'ambito dell'elaborazione di dati massivi (idealmente utilizzando dati reali) e risolverlo implementando le tecniche discusse a lezione o descritte in articoli di ricerca originali. Il progetto va consegnato nella forma di una relazione pdf. Gli argomenti devono essere in linea con il focus del corso: strutture dati compresse, filtri o algoritmi di sketching/streaming. È possibile utilizzare qualsiasi linguaggio di programmazione, sebbene siano raccomandati C/C++, Rust (e simili) per ragioni di efficienza.

2. Prova orale individuale. La prova va sostenuta obbligatoriamente dopo la consegna del progetto individuale. Il punteggio massimo ottenibile con la prova orale è 15. La prova inizia con un semplice test a risposta multipla volto a verificare conoscenze di base collegate al materiale del corso. Se il test viene passato, la prova orale prosegue con la verifica dei dettagli del progetto consegnato. Nel qual caso lo studente non sappia dimostrare conoscenza approfondita di tutti i dettagli del progetto, la prova orale coprirà anche elementi teorici presentati durante il corso.

orale

Progetto individuale (massimo 15 punti, sufficienza: 9/15):
- accuratezza della soluzione, uso di risorse computazionali, qualità della relazione (range 80%),
- originalità della soluzione (range 20%).

Prova orale (massimo 15 punti):
- conoscenze: enunciati e dimostrazioni dei risultati teorici (range 40%),
- dettaglio e completezza delle risposte (range 40%),
- capacità di comunicazione, compreso l'uso di terminologia specifica relativa ad algoritmi e strutture di dati per dati massivi (range 20%).

La valutazione finale è data dalla somma delle valutazioni del progetto e della prova orale. Le valutazioni massime (30 e 30L) richiedono di rispondere ad una domanda aggiuntiva facoltativa sulla teoria presentata durante il corso. Senza questa domanda facoltativa, la valutazione massima ottenibile è 29.

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