Algorithms for massive data
a.a. 2021/22
Responsabile didattico: Nicola Prezza
Durata: 28 ore
Programma: Basics: Probability theory recap (random variables; concentration inequalities); Hashing (universal and k-independent hashing). Similarity-preserving sketching: Karp-Rabin hashing; Jaccard similarity via minhash, Locality-sensitive hashing. Mining data streams: Pattern matching (Karp-Rabin's and Porat-Porat's algorithms); Counting with small registers: Morris' algorithm; Counting distinct elements (Flajolet-Martin's and bottom-k algorithms); Counting ones in a window: Datar-Gionis-Indyk-Motwani's algorithm. Compressed data structures: Data compression (entropy, codes, dictionary compressors); Dictionary data structures (Elias-Fano, succinct bitvectors); Compressed suffix arrays; FM index; Beyond statistical compression (LZ-indexes, run-length BWT).