Diario delle lezioni

Totale: 21 lezioni da 2 ore e 2 lezioni da 3 ore (2*21 + 3*2 = 48 ore), corrispondenti a 6 CFU.

22 settembre 2025 (Lezione n° 1 da 2 ore)

• Presentazione del corso
• Introduzione al Data Mining
• Introduzione ai Big Data
• Principio di Bonferroni
• Introduzione agli algoritmi

23 settembre 2025 (Lezione n° 2 da 2 ore)

• Introduzione alla computazione distribuita e concorrente
• MapReduce e sua implementazione Hadoop: introduzione
• File system distribuito HDFS: files e chunck
• Architettura distribuita multirack
• Gestione dei fallimenti
• MapReduce: progettazione di algoritmi distribuiti
• Map task
• Reduce task
• Backup Tasks
• Combiners
• Funzione di partizione

29 settembre 2025 (Lezione n° 3 da 2 ore)

• Rappresentazione di matrici sparse
• MapReduce: prodotto matrice vettore
• Introduzione ai grafi
• Rappresentazione di grafi tramite matrici di adiacenza
• MapReduce: cammini di lunghezza 2 in grafi

30 settembre 2025 (Lezione n° 4 da 2 ore)

• MapReduce: prodotto di matrici in 2 step
• MapReduce: prodotto di matrici in un unico step
• Estensioni di MapReduce: i Workflow
• Spark: RDD, trasformazioni, azioni, Lazy evaluation, Lineage
• MapReduce: cammini di lunghezza 3 in grafi

7 ottobre 2025 (Lezione n° 5 da 2 ore)

• Modello di “costo di comunicazione” in MapReduce
• Reducer Size e Replication Rate
• Mapping schema: grafo bipartito input/output
• Similarity join con MapReduce

9 ottobre 2025 (Lezione n° 6 da 2 ore)

• Lower bound al replication rate
• Esercizi su MapReduce
• Introduzione a Similar items
• Jaccard similarity
• Shingling di documenti di testo

13 ottobre 2025 (Lezione n° 7 da 2 ore)

• Introduzione a funzioni Hash
• Compressione di shingles con funzioni Hash
• Vettore caratteristico e matrice caratteristica
• Minhashing e Jaccard similarity
• Minhash signature e matrice delle firme

14 ottobre 2025 (Lezione n° 8 da 2 ore)

• Calcolo della matrice delle firme
• Locality-Sensitive Hashing: dividere la matrice in bande
• Il procedimento completo per la similarità di documenti di testo

20 ottobre 2025 (Lezione n° 9 da 2 ore)

• Misure di distanza: distanze euclidee, distanza di Jaccard, distanza coseno, Edit distance, distanza di Hamming
• Teoria Locality-Sensitive Hashing
• AND-construction, OR-constriction, S-curve
• LSH per distanza di Hamming

21 ottobre 2025 (Lezione n° 10 da 2 ore)

• LSH per distanze euclidee
• Matching di impronte digitali
• Tecniche per rilevare item identici
• Tecniche per item con alto grado di similarità: filtro per lunghezza

3 novembre 2025 (Lezione n° 11 da 2 ore)

• Tecniche per item con alto grado di similarità: indicizzazione del prefisso
• Frequent itemset: introduzione e applicazioni
• Supporto, frequenza
• Regole di associazione: confidenza, interesse
• Introduzione all’algoritmo A-Priori

4 novembre 2025 (Lezione n° 12 da 2 ore)

• Algoritmo A-Priori
• Esempio esecuzione Algoritmo A-Priori
• Introduzione all’Algoritmo di Park-Chen-Yu (PCY)

10 novembre 2025 (Lezione n° 13 da 2 ore)

• Algoritmo di Park-Chen-Yu (PCY)
• Varianti multi-stage e multi-hash dell’algoritmo PCY
• Esempio di prestazioni migliorate con la variante multi-hash PCY

11 novembre 2025 (Lezione n° 14 da 2 ore)

• Algoritmo randomizzato “semplice”
• Algoritmo distribuito di Savarese-Savasere-Omiecinski-Navathe (SON)
• Algoritmo di Tovoinen
• Esercizio su item con alto grado di similarità

17 novembre 2025 (Lezione n° 15 da 2 ore)

• Esercizi su MapReduce in preparazione all’esonero

18 novembre 2025 (Lezione n° 16 da 2 ore)

• Esercizio su MapReduce in preparazione all’esonero
• Introduzione al problema del Clustering
• Clustering gerarchico e valutazione della sua efficienza

24 novembre 2025 (Lezione n° 17 da 2 ore)

• Algoritmo K-means di assegnamento di punti
• Scelta del parametro k per il clustering
• Algoritmo di Bradley, Fayyad e Reina
• Algoritmo CURE

25 novembre 2025 (Lezione n° 18 da 2 ore)

• Algoritmo GRGPF
• Esercizi su Map-Reduce

2 dicembre 2025 (Lezione n° 19 da 2 ore, ore 9:00-11:00)

• Introduzione all’analisi dei link nel Web
• PageRank
• Teleporting
• Calcolo del PageRank (prima parte)

2 dicembre 2025 (Lezione n° 20 da 2 ore, ore 16:00-18:00)

• Calcolo del PageRank (seconda parte)
• Topic-specific PageRank
• TrustRank e Spam mass
• Cenni a HITS
• Esercizi su PageRank

15 dicembre 2025 (Lezione n° 21 da 3 ore)

• Reti sociali: problema dell’individuazione di comunità
• Edge-betweeness per clustering: Algoritmo di Girvan-Newman
• Modularità come misura della qualità di un clustering
• Lista tool per Big Data
• SimRank
• Ricerca di comunità in grafi sociali: grafi bipartiti completi
• Correlazione con il problema degli itemset frequenti

16 dicembre 2025 (Lezione n° 22 da 3 ore)

• Modelli generativi per la determinazione di comunità: AGM e BigCLAM
• Esercizi su reti sociali
• Esercizi in preparazione all’esame

8 gennaio 2026 (Lezione n° 23 da 2 ore)

• Correzione dell’esonero
• Relazioni su tool per big data
• Esercizi in preparazione all’esame