Docente: Paolo Ferragina
| Argomento | Riferimenti |
|---|---|
| Introduzione al corso: grandi collezioni di dati, motori di ricerca e il Web 2.0. Una nuova algoritmica? | Google, The Economist,Time (parte a), Time (parte b) |
| Modelli di calcolo: External-memory model, Data Streaming model, Cache-Oblivious model | slides in pdf e pps |
| Alcuni problemi interessanti: Max subarray, Elementi di max-frequenza, DB vs IR-approach al progetto di un motore di ricerca | Bentley |
| Il problema dell'ordinamento su grandi collezioni di dati: single vs multiple disks, disk striping, multi-way merge-sort, distribution sort, permuting vssorting, limiti inferiori | Greed Sort (saltare i dettagli del ColumnSort e le dimostrazioni), Libro Vitter (saltare il dettaglio delle formule 5.2 e 5.4),limiti inferiori |
| Nozione di Entropia: ordine zero e ordine k. Codici univocamente decodificabili e loro ottimalità (cenni ai Teoremi di Shannon) | |
| Huffman code: definizione, ottimalità, variante canonica | Sezioni 2.1-2.3 di Managing-Gigabytes tranne “Computing Huffman code lengths”, e slides in pdf e pps |
| CGrep: Byte-Aligned & Tagged Huffword, Ricerca sul compresso | CGrep |
| Alcuni algoritmi di pattern-matching: Karp & Rabin (ricerca esatta e fingerprinting), Agrep (ricerche regex e approssimate) | KR,AGrep |
| Un semplice compressore: ordina simboli per frequenza e codifica i loro ranghi (anche (s,c)-dense codes su slides) | codes |
| Compressione in streaming: Move-to-Front, Run-Length encoding (RLE) | MTF |
| Arithmetic coding: statico, dinamico e schema PPM | Sezione 2.4 e 2.5 (Prediction by Partial Matching) di Managing-Gigabytes, e slides in pdf e pps |
| Dictionary-based compression: LZ77, LZ78, LZW. | Sezione 2.6 di Managing-Gigabytes, e slides in pdf e pps |
| Burrows-Wheeler Transform: properietà, costruzione e inversione. Il compressore Bzip2. | Sezione 2.5 (Block-sorting compression) di Managing-Gigabytes, e articolo originale |
| Il grafo del Web: proprietà e compressione. | slides |
| Compressione e Sincronizzazione di (collezioni di) file | slides, rsync |
| Data Sketching e Data Streaming: Bloom Filter, Spectral Bloom Filter, Count Min Sketch, e loro applicazioni | slides, Bloom Filter, Count Min Sketch |
| Full-indexing: definizione, suffix tree, suffix array, lcp array. Text mining. | slides, Text Indexing |
| Motori di Ricerca: introduzione, struttura, e crawling. | slides, Struttura, Crawling |
| Motori di Ricerca: parsing, modelli statistici dei testi (Zipf Law, Heaps Law, Luhn). | slides |
| Motori di Ricerca: Inverted Lists = Dizionario + Postings. Indicizzazione del dizionario. | slides, Locality Preserving FC solo sez 3.2 e no teo 7 |
| Motori di Ricerca: Memorizzazione dei Postings e risoluzione di Query. | slides,articolo |
| Motori di Ricerca: Text-based ranking, Link-based ranking. Qualità dei risultati: Precision, Recall, F-measure. Visualizzazione snippets e loro clustering. | slides, articolo |
| Miscellanea: Latent Semantic Indexing e Random Projections. | slides, articolo senza (SVD updating) |
| Miscellanea: Web SPAM, Web Advertising. | slides |
| Ricapitolazione argomenti | Parte 1: slides con animazioni, Parte 2:slides con animazioni |