DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== 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]]|