====== Algoritmi per Information Retrieval 2008/2009 ====== **Docente**: [[http://www.di.unipi.it/~ferragin/|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. ===== 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? |[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Google_distributed.pdf|Google]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Economist.pdf|The Economist]],[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/time_2006a.pdf|Time (parte a)]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/time_2006b.pdf|Time (parte b)]] | | Modelli di calcolo: External-memory model, Data Streaming model, Cache-Oblivious model | slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/0-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/0-Lecture.pps|pps]] | |Alcuni problemi interessanti: Max subarray, Elementi di max-frequenza, DB //vs// IR-approach al progetto di un motore di ricerca|[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Bentley.pdf|Bentley]]| |Il problema dell'ordinamento su grandi collezioni di dati: single //vs// multiple disks, disk striping, multi-way merge-sort, distribution sort, permuting //vs//sorting, limiti inferiori| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/GreedSort.pdf|Greed Sort]] (saltare i dettagli del ColumnSort e le dimostrazioni), [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Libro_Vitter.pdf|Libro Vitter]] (saltare il dettaglio delle formule 5.2 e 5.4),[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/LowerBound.pdf|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 [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/1-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/1-Lecture.pps|pps]]| | CGrep: Byte-Aligned & Tagged Huffword, Ricerca sul compresso |[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Huffword.pdf|CGrep]]| |Alcuni algoritmi di pattern-matching: Karp & Rabin (ricerca esatta e //fingerprinting//), Agrep (ricerche regex e approssimate)| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/KR.pdf|KR]],[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Agrep.pdf|AGrep]]| | Un semplice compressore: ordina simboli per frequenza e codifica i loro ranghi (anche //(s,c)-dense codes// su slides)|[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/IntegerCodes.pdf|codes]]| |Compressione in streaming: Move-to-Front, Run-Length encoding (RLE)|[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/MoveToFront.pdf|MTF]]| | Arithmetic coding: statico, dinamico e schema PPM | Sezione 2.4 e 2.5 (Prediction by Partial Matching) di Managing-Gigabytes, e slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/2-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/2-Lecture.pps|pps]]| | Dictionary-based compression: LZ77, LZ78, LZW. | Sezione 2.6 di Managing-Gigabytes, e slides in [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/3-Lecture.pdf|pdf]] e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/3-Lecture.pps|pps]]| | Burrows-Wheeler Transform: properietà, costruzione e inversione. Il compressore Bzip2. | Sezione 2.5 (Block-sorting compression) di Managing-Gigabytes, e [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/BW.pdf|articolo originale]]| | Il grafo del Web: proprietà e compressione. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/4-Lecture.pdf|slides]]| | Compressione e Sincronizzazione di (collezioni di) file | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/5-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/survey_rsync.pdf|rsync]] | | Data Sketching e Data Streaming: Bloom Filter, Spectral Bloom Filter, Count Min Sketch, e loro applicazioni| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/6-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/BloomFilterSurvey.pdf|Bloom Filter]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/CMS.pdf|Count Min Sketch]]| | Full-indexing: definizione, suffix tree, suffix array, lcp array. Text mining.| [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/7-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/TextIndexing.pdf|Text Indexing]]| | Motori di Ricerca: introduzione, struttura, e crawling. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/8-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/SearchEngines.pdf|Struttura]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/chap2.pdf|Crawling]]| | Motori di Ricerca: parsing, modelli statistici dei testi (Zipf Law, Heaps Law, Luhn). | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/9-Lecture.pdf|slides]]| | Motori di Ricerca: Inverted Lists = Dizionario + Postings. Indicizzazione del dizionario. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/10-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/LPFC.pdf|Locality Preserving FC]] solo sez 3.2 e no teo 7| | Motori di Ricerca: Memorizzazione dei Postings e risoluzione di Query. |[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/11-Lecture.pdf|slides]],[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/InvertedFiles.pdf|articolo]] | | Motori di Ricerca: Text-based ranking, Link-based ranking. Qualità dei risultati: Precision, Recall, F-measure. Visualizzazione snippets e loro clustering. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/12-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/chap7-chakrabharti.pdf|articolo]] | | Miscellanea: Latent Semantic Indexing e Random Projections. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/13-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/LatentSemanticIndexing.pdf|articolo]] senza (SVD updating)| | Miscellanea: Web SPAM, Web Advertising. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/14-Lecture.pdf|slides]]| | Ricapitolazione argomenti | Parte 1: [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/all1.pps|slides con animazioni]], Parte 2:[[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/all2.pps|slides con animazioni]]|