DA LOZZO GIORDANO
FRATI FABRIZIO
Obiettivi
In molti contesti applicativi sono in gioco enormi volumi di dati chevengono utilizzati in ambito economico-finanziario, politico, sociale ed
anche istituzionale. Spesso i dati sono memorizzati in enormi cloud
distribuite e talvolta sono generati secondo un flusso continuo, così
consistente da renderne impossibile una memorizzazione completa. In
moltissimi casi i dati sono inerenti ad entità in fitta relazione tra
loro e danno luogo a immense reti di collegamenti. Esempi comuni di tali
reti sono le reti sociali e biologiche, le reti di distribuzione e il
grafo del Web. Inoltre il fatto che i dati siano memorizzati in sistemi
gestiti da terze parti pone problemi di integrità che non trovano
riscontro nella letteratura informatica classica sia per la tipologia
sia per la scala.
Questo scenario pone sfide algoritmiche inedite sulle quali è al lavoro
una vasta platea di ricercatori. Tale sforzo ha prodotto, nell’ultimo
decennio, molte novità sia sul piano metodologico sia sul piano
tecnologico. L’insegnamento ha lo scopo di trasferire agli studenti
alcuni tra i più importanti strumenti metodologici nati nell’ambito
della ricerca sugli algoritmi per Big Data. Tali strumenti metodologici
sono proposti assieme a contesti applicativi sfidanti.
Programma
1) Algorithms for data streams- Approximate counting
- Majority problems
- Sampling and reservoir sampling
- Bloom filters
- Frequent itemsets
- Number of distinct elements
2) Algorithms and data structures for quantitative features analysis
- orthogonal range searching (kd-trees, range trees, and layered range trees)
- median finding
- multidimensional divide and conquer, closest pair
- fractional cascading
3) Locality sensitive hashing for finding similar items
- Min-Hashing
- Nearest neighbour search, k-nearest neighbour search
4) NoSQL internals & Distributed Hash Tables
- Chord
- consistent hashing
- Kademlia
5) Scalable security:
- integrity of big data sets in the cloud,
- consistency and scalability issues with authenticated data structures
Prerequisiti
DA LOZZO GIORDANO
Il corso non richiede alcun prerequisito.FRATI FABRIZIO
NessunoTesti Adottati
Mining of Massive DatasetsJure Leskovec, Anand Rajaraman, Jeff Ullman
Cambridge University Press
http://www.mmds.org/
Bibliografia Di Riferimento
Mining of Massive Datasets Jure Leskovec, Anand Rajaraman, Jeff Ullman Cambridge University Press http://www.mmds.org/Modalità Erogazione
TradizionaleModalità Frequenza
FacoltativaModalità Valutazione
DA LOZZO GIORDANO
Prova scritta, valutazione progetto. La prova scritta puo' essere sostituita da prove in itinere parziali.FRATI FABRIZIO
Prova scritta, valutazione progetto. La prova scritta può essere sostituita da prove in itinere parziali.Esempi Domande
Domanda 1:Descrivi i Bloom filter. Mostra perché i Bloom filter possono avere falsi positivi. Qual è la probabilità che un Bloom filter abbia falsi positivi? Mostra l’analisi che porta a calcolare tale probabilità e mostra quando tale probabilità è minima.
Domanda 2:
Si consideri un KD-tree T definito su un pointset P⊆R^2. Si descriva l’algoritmo SearchKDTree che consente di effettuare su T una query di tipo Orthogonal Range Search definita da un rettangolo R. Se ne descrivano inoltre le performance in termini di tempo di interrogazione, argomentando le ragioni che lo determinano.
