Algoritmi per i Big Data

PROPEDEUDICITA'

MATEMATICA DISCRETA, CALCOLO DELLE PROBABILITA' ET STATISTICA, ALGORITMI E STRUTTURE DI DATI.

CAMBIAMENTO AULA

- LA LEZIONE del 10 ottobre 2023 dalle ore 9:30 alle ore 11:00 in aula 5 PP2 è stata spostata in aula 1 PP1.

- La LEZIONE del 17 ottobre 2023 dalle ore 9:30 alle ore 11:00 in aula 5 PP2 è stata  spostata in 6 PP2

INIZIO CORSO ABD

Cari Studenti, il corso avrà inizio, come da orario, martedì 3 ottobre in aula 5 PP2. La lezione avrà inizio alle 9.30 e sarà una panoramica introduttiva agli argomenti che tratteremo durante tutto il corso. Vi aspetto!

Vi ricordo che tutte le informazioni sono disponibili sul canale Team associato a questo corso

ARGOMENTI ED OBIETTIVI DEL CORSO

Il corso si propone di descrivere tecniche algoritmiche e statistiche per la gestione di grandi quantità di dati (Big Data). In particolare, si descriveranno le soluzioni più efficienti per effettuare operazioni fondamentali di Data Mining ed Information Retrieval su insiemi di Dati. Per esempio, si mostreranno tecniche probabilistiche per trovare velocemente tutte le coppie pagine web che risultano simili. Si considereranno scenari applicativi in cui gli  insiemi di dati non possono essere mantenuti nella memoria di un computer: o sono troppo grandi, oppure variano con il tempo, per esempio sono l'output di un canale di comunicazione (Data Stream). In questo contesto, le soluzioni algoritmiche classiche viste nel corso di Algoritmi e Strutture Dati del II anno non sono spesso implementabili.

ACCESSO ALLE INFORMAZIONI PER IL CORSO

Il canale ufficiale del corso è già disponibile sulla piattaforma Teams ed e' sul link:

https://teams.microsoft.com/l/team/19%3a52fClnCQSlHBUeredBDlYa9xp7OBDBwSXiRyUzpDtB81%40thread.tacv2/conversations?groupId=922821d9-4e4d-4c8c-9586-db661a41c0d0&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Tutte le informazioni sono disponibili e saranno aggiornate sul suddetto canale.

LE LEZIONI SVOLTE SONO PUBBLICATE SUL CANALE TEAMS DEL CORSO

ALGORITHMS FOR BIG DATA 

Programma Provvisorio 

PART A: Probability and Computing: Randomized Algorithms for Big Data 

oBasic Notions of Probability (Chapt 1 of [2]) 

oVerifying Polynomial Identities (Chapt 1.1 of [2],  

oVerifying Matrix Multiplications (Chapt. 1.3 of [2],  

oContention Resolutions (Chapt 13 of [3]) 

oRandomized Quick-Sort (Chapt. 2.5 of [2]) 

oRandomized Algorithms for Computing the Median ( Chapt 3.4 of [2]) 

oRandomized Hash Functions, and Hash Tables*, (Chapt 13.6 of [3]   vedi anche Ssection 2.3 in [4]*)   

PART B: Data Mining   

•Data Mining: A Short Overview  (Chapt 1 of [1]): 

oModeling from a Data Set 

oStatistical Modeling 

oMachine Learning 

oComputational Approach  

oTypical  Problems in Data Mining: Examples 

oBasic Data Structures: Hash Functions and Indexes (see Part A)* 

•Finding Similar Items (Chapt 3 of [1] + ) 

oApplications of Set Similarity 

oShingling of Documents 

oSimilarity-preserving Summaries of Sets 

oLocality Sensing Hashing for Documents 

•Mining Data Streams (Chapt 4 of [1]) 

oThe Stream Data Model 

oPattern Matching: Karp-Rabin’s Algorithm (Ssection 4.1 in [4]) 

oSampling Data in a Stream 

oFiltering Stream 

oCounting Distinct Elements in a Stream 

oEstimating Moments of a Stream 

•Random Walks & Page Rank (forse...) 

oRandom Walks  (Section 4 of [5]) 

oPage Rank Algorithms for the WEB (Sec  5 of [1]] 

Books: 

[1] Leskovec, Rajaraman, and Ullamann: Mining of Massive Data Sets (+ slides in preparazione) 

[2] Mitzenmacher and Upfal: Probability and Computing (Cambridge) 

[3] Kleinberg and Tardos: Algorithm Design 

[4] Nicola Prezza: Algorithms for Massive Data (Notes) 

[5] Foundations of Data Science, Avrim Blum, John Hopcroft, Ravindran Kannan 

Su appuntamento con il docente, inviando una richiesta per email a:

clementi@mat.uniroma2.it

con SUBJECT:  ricevimento ABD

Prova Orale + Progetto (Facoltativo)