Algoritmi per “Information Retrieval”

Informazioni generali:

• Docente: Prof. Paolo Ferragina, Dipartimento di Informatica, Pisa.

• Impegno: ~ 50 ore (teoria + esercitazioni), per un totale di 6 CFU.

• Orario delle lezioni: Lunedì, ore 16-18 (aula C); Mercoledì, ore 16-18 (aula C).

• Ricevimento studenti: Venerdì, ore 11-13 (studio docente).

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-strutturate (p.e. XML). Questo studio si concentrerà su tutti i componenti princiali di un moderno motore di ricerca: Crawler, Parser, Indexer, Query resolver, Ranker, Archive compressor. 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 altre tecniche algoritmiche utili in vari ambiti: delta-compression, set reconciliation, min-wise permutations, bloom filter, P2P synchronization protocols, ...

Modalità di esame:   Un progetto svolto in gruppi di al massimo 2 persone, o un seminario su un argomento indicato dal docente, e un esame orale sugli argomenti del corso.
 

Libri di testo:

[MG]  Managing Gigabytes. I.H. Witten e A. Moffat e T.C. Bell. Morgan Kaufmann, 1999.

• Capitoli 2, 3, 4 e 5

[MW]  Mining the Web: discovering knowledge from hypertext data. S. Chakrabarti. Morgan Kaufmann, 2003.

• Capitolo 2

⇒ ⇒ E altri articoli sugli argomenti trattati nel corso..

Programma del corso e materiale didattico aggiuntivo (registro delle lezioni, copie materiale)

• Prologue
• Algorithm design is no longer a 5-mins thinking task!!
• Bloom Filters and Count-Min sketches: theory and applications.
• Document compression: Huffman (canonical), Huffword, Arithmetic, Gzip (and LZ-variants), RLE, MTF, Bzip and the boosting technique, integer coding techniques.
• Compressed storage of document collections, Inverted lists and Dictionaries
• Full-text Indexing for texts and XML data: Suffix Array, String B-tree, FM-index and XBW-Index.
• Crawling.
• Parsing and Basic Text Models.
• Basic query processing, optimizations, caching, and dynamic collections.
• Textual document scoring and fast cosine calculation, Relevance feedback and Rocchio's method.
• Reducing dimensionality: Latent Semantic Indexing and Random Projections.
• Link-based Ranking: PageRank, HITS and some variants.
• Evaluation of a search engine: Precision vs. Recall, Interpolated precision and F-measure.
• Cenni su Clustering e Classificatione.
• Seminario su Yahoo Widget Engine.
• Seminario su Algoritmi per memorie flash.
• Seminario su Algoritmi Cache-Oblivious.