Title: Algorithms for big data

Lecturers:  Paolo Ferragina and Andrea Marino

Period: First 5 lectures: 18, 19, 20, 25, 26 november, 9-11, sala seminari EST
Last 4 lectures: 18 March, 15 - 17 Sala Gerace;  20 March, 11-13, sala seminari EST;
25 March, 15 - 17,  Sala Seminari OVEST; 27 March, 11 - 13, Sala Seminari EST.


Lecture 1. Data streams and sketching: Distinct counting, Frequent Items, Probabilistic Estimators, Similarity and Min-hash sketches.

Lecture 2. Sampling: sampling in networks, markov chain sampling. Applications to estimating properties of large networks.

Lecture 3. Mining in large graphs: social network analysis, clustering, community detection, spectral techniques.

Lecture 4. Dimensionality reduction: Projections, Locality sensitive hashing, Johnson Lindenstrauss.

Lecture 5. Large-scale distributed programming frameworks: Map-reduce, Pregel and examples of computation on large graphs.

Lecture 6. Diameter computation in real-world huge graphs.

Lecture 7. Distance distribution approximation and introduction to probabilistic counting.

Lecture 8: Probabilistic counting with applications

Lecture 9. Centrality measures in complex networks.