Algoritmi per Information Retrieval 2008/2009

Informazioni Generali

Impegno: 6 CFU tra teoria ed esercitazioni.
Orario delle lezioni: Lunedì ore 16-18 (aula C1), Mercoledì ore 16-18 (aula C1).
Ricevimento studenti: Lunedì 9-12 e dopo ogni lezione.

Libri di testo

I.H. Witten, A. Moffat, T.C. Bell. Managing Gigabytes. Morgan Kaufmann, 1999 (second edition).
S. Chakrabarti. Mining the Web: discovering knowledge from hypertext data. Morgan Kaufmann, 2003.
Articoli forniti dal docente (in attach a ogni lezione)

Programma del corso

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