Questa è una vecchia versione del documento!
Indice
Algoritmi per Information Retrieval [AA293]
Docente: Paolo Ferragina
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.
Obiettivi del corso
Studio, progetto e analisi di sistemi software efficienti ed efficaci per l’Information Retrieval nell’ambito di collezioni di documenti testuali, html e semi-strutturati (p.e. XML). Questo studio si concentrerà su tutti i componenti princiali di un moderno motore di ricerca: Crawler, Parser, Compressor, Indexer, Query resolver, Ranker. Esamineremo le soluzioni algoritmiche correntemente adottate per ciascuno di essi in maniera approfondita, valutando le loro prestazioni e i loro limiti computazionali. Discuteremo anche i fondamenti pratici e teorici per l’organizzazione e l’analisi dei sistemi di IR, con valutazione delle loro prestazioni. Infine analizzeremo numerose altre tecniche algoritmiche per il: data streaming, data compression, data indexing, data sketching, data searching, e (cenni di) text mining.
Modalità di esame
L'esame consiste di una prova scritta, contenete domande sul programma del corso, e di un colloquio di approfondimento.
Vi allego un insieme di compiti relativi a prove di anni precedenti. Alcuni quesiti potrebbero riferirsi ad argomenti non trattati quest'anno, nel caso contattatemi!
Prossimi Appelli
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 |
| 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 |
| Miscellanea: Web SPAM, Web Advertising. | slides |