Algoritmi per i Big Data

INIZIO CORSO ABD

Il corso ABD dell'anno accademico 2023-34 avrà inizio martedì 8 ottobre alle ore 9.30. A partire dalla lezione successiva, l'orario di inizio delle lezioni e' fissato per le ore 9.00. L' aula  e' la 5 in PP2 salvo comunicazioni diverse che verranno inserite  sul canale teams.

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. 

Tutti gli studenti  che decidono di seguire e fare l'esame di ABD devono  iscriversi al suddetto canale teams ed e' richiesto di consultarlo  assiduamente durante lo svolgimento delle lezioni.

ABD: 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.

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 

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 

per appuntamento , tramite email : clementiATmat.uniroma2.it

orale con possibilità di svolgere progetti (facoltativo)