Totale: 24 lezioni da 2 ore (2*24 = 48 ore), corrispondenti a 6 CFU.

25 settembre 2023 (Lezione n° 1 da 2 ore)

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

26 settembre 2023 (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

2 ottobre 2023 (Lezione n° 3 da 2 ore)

• Backup Tasks
• Combiners
• Funzione di partizione
• Rappresentazione di matrici sparse
• MapReduce: prodotto matrice vettore
• Introduzione ai grafi
• Rappresentazione di grafi tramite matrici di adiacenza

3 ottobre 2023 (Lezione n° 4 da 2 ore)

• MapReduce: cammini di lunghezza 2 in grafi
• MapReduce: prodotto di matrici in 2 step
• MapReduce: prodotto di matrici in un unico step

9 ottobre 2023 (Lezione n° 5 da 2 ore)

• Estensioni di MapReduce: i Workflow
• Spark: RDD, trasformazioni, azioni, Lazy evaluation, Lineage
• Modello di costo di comunicazione in MapReduce
• Reducer Size e Replication Rate
• Mapping schema: grafo bipartito input/output
• Similarity join con MapReduce

16 ottobre 2023 (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
• Introduzione a funzioni Hash
• Compressione di shingles con funzioni Hash

17 ottobre 2023 (Lezione n° 7 da 2 ore)

• Minhashing e Jaccard similarity
• Minhash signature
• Locality-Sensitive Hashing: introduzione

23 ottobre 2023 (Lezione n° 8 da 2 ore)

• Locality-Sensitive Hashing: dividere la matrice in bande
• Il procedimento completo per la similarità di documenti di testo
• Misure di distanza: distanze euclidee, distanza di Jaccard, distanza coseno, Edit distance.

24 ottobre 2023 (Lezione n° 9 da 2 ore)

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

30 ottobre 2023 (Lezione n° 10 da 2 ore)

• Matching di impronte digitali
• Tecniche per rilevare item identici
• Tecniche per item con alto grado di similarità: filtro per lunghezza
• Tecniche per item con alto grado di similarità: indicizzazione del prefisso (prima parte)

31 ottobre 2023 (Lezione n° 11 da 2 ore)

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

6 novembre 2023 (Lezione n° 12 da 2 ore)

• Algoritmo A-Priori
• Esempio esecuzione Algoritmo A-Priori

7 novembre 2023 (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

13 novembre 2023 (Lezione n° 14 da 2 ore)

• Algoritmo randomizzato “semplice”
• Algoritmo distribuito di Savarese-Savasere-Omiecinski-Navathe (SON)
• Algoritmo di Tovoinen

14 novembre 2023 (Lezione n° 15 da 2 ore)

• Introduzione al problema del Clustering
• Clustering gerarchico e valutazione della sua efficienza
• Algoritmo K-means di assegnamento di punti (I parte)

20 novembre 2023 (Lezione n° 16 da 2 ore)

link alla lezione

• Algoritmo K-means di assegnamento di punti (II parte)
• Scelta del parametro k per il clustering
• Algoritmo di Bradley, Fayyad e Reina (I parte)

21 novembre 2023 (Lezione n° 17 da 2 ore)

• Algoritmo di Bradley, Fayyad e Reina (II parte)
• Algoritmo CURE
• Algoritmo GRGPF (I parte)

28 novembre 2023 (Lezione n° 18 da 2 ore)

• Algoritmo GRGPF (II parte)
• Introduzione all’analisi dei link nel Web

29 novembre 2023 (Lezione n° 19 da 2 ore)

• PageRank
• Teleporting
• Calcolo del PageRank (I parte)

4 dicembre 2023 (Lezione n° 20 da 2 ore)

• Esercizi in preparazione all’esonero

5 dicembre 2023 (Lezione n° 21 da 2 ore)

• Esercizi in preparazione all’esonero
• Calcolo del PageRank (II parte)

11 dicembre 2023 (Lezione n° 22 da 2 ore)

• Topic-specific PageRank
• TrustRank e Spam mass
• Cenni a HITS Reti sociali: edge-betweeness per clustering
• Algoritmo di Girvan-Newman

12 dicembre 2023 (Lezione n° 23 da 2 ore)

• Algoritmo di Girvan-Newman: complessità
• Modularità come misura della qualità di un clustering
• SimRank
• Ricerca di comunità in grafi sociali: grafi bipartiti completi
• Correlazione con il problema degli itemset frequenti
• Modelli generativi per la determinazione di comunità: AGM e BigCLAM (I parte)

18 dicembre 2023 (Lezione n° 24 da 2 ore)

• Modelli generativi per la determinazione di comunità: AGM e BigCLAM (II parte)
• Correzione esonero
• Esercizi in preparazione all’esame

9 gennaio 2024 (Lezione aggiuntiva da 2 ore)

• Relazioni su tool per big data: import.io, Scraper API, RawGraphs, Gephi, Carto, Tableau
• Esercizi in preparazione all’esame