| Entrambe le parti precedenti la revisione
Revisione precedente
Prossima revisione
|
Revisione precedente
|
air:start [04/12/2008 alle 12:01 (16 anni fa)]
Paolo Ferragina |
air:start [26/03/2010 alle 15:08 (14 anni fa)] (versione attuale)
peppe |
| ====== Algoritmi per Information Retrieval [AA293] ====== | ====== Algoritmi per Information Retrieval [AA293] ====== |
| **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. | |
| |
| |
| ===== 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 [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/Vecchi_testi_AIR.zip|insieme di compiti]] relativi a prove di anni precedenti. Alcuni quesiti potrebbero riferirsi ad argomenti non trattati quest'anno, nel caso contattatemi! | |
| |
| ==== Prossimi Appelli ==== | |
| |
| ^ Data ^ Ore ^ Aula ^ Prova ^ | |
| | 13 Gennaio '09 | 14:30 | B1 | [[|testo]] | | |
| | 3 Febbraio '09 | 09:30 | B e E | [[|testo]] | | |
| |
| |
| ===== 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]]| | |
| | 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/14-Lecture.pdf|slides]], [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/LatentSemanticIndexing.pdf|articolo]] | | |
| | Miscellanea: Web SPAM, Web Advertising. | [[http://www.di.unipi.it/~ferragin/Teach/InformationRetrieval/15-Lecture.pdf|slides]]| | |
| |
| | |
| |
| |
| |
| |
| |
| | La pagina è stata spostata [[magistraleinformatica:ir:|qui]]. |
| |
| |
