Algoritmi per "Information Retrieval"

Paolo Ferragina      Tel. 0502212764

Introdurre i principi, le tecniche e gli strumenti algoritmici e le strutture dati necessarie al progetto di sistemi software efficienti ed efficaci per il recupero di informazioni da grandi collezioni di dati testuali. Introduzione alle problematiche e alle tecniche legate allo sviluppo di motori di ricerca per il Web e per documenti XML.

Conoscenze. Cosa è un (meta-)motore di ricerca per dati testuali, Web e XML. Conoscere la struttura e le caratteristiche progettuali di questi sistemi software complessi, con riferimento ad alcuni motori di ricerca reali quali: Google, Yahoo!, AskJeeves, Vivisimo, e tanti altri. Conoscere le strutture dati principali per l’indicizzazione testuale, per lo storage compresso delle informazioni; gli algoritmi di crawling per il recupero delle pagine dal Web, e per il ranking dei risultati (molti oggi) restituiti dai motori di ricerca. Conoscere le tecniche di base per l’analisi di dati Web: clustering, classificazione, e sistemi di raccomandazione.

Capacità. Saper progettare e valutare la bontà di un motore di ricerca, o di un software per l’accesso e il recupero di dati non strutturati (testi, pagine web) o semi-strutturati (XML).

Comportamenti. Lo studente acquisirà delle conoscenze avanzate sullo stato dell’arte nel campo della progettazione e realizzazione di motori di ricerca per il Web e per XML. In questo modo saprà essere in grado di valutare un software di ricerca o mining di informazioni testuali indipendentemente dal vendor, tenendo conto soltanto delle caratteristiche progettuali dello stesso e dell’applicazione nella quale questo deve essere utlizzato.

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, ...

Study, design and analysis of efficient and effective software systems for Information Retrieval, in the context of large textual databases. Design and development of a search engine combining advanced compression and indexing techniques for textual as well XML data.

Per conseguire gli obiettivi indicati, sarà necessario:

• organizzare il processo di apprendimento in moduli flessibili, specializzati sulle varie componenti di un motore di ricerca;
• partire dal problem solving per arrivare alla proposta di soluzioni algoritmiche efficienti;
• presentare in modo approfondito ogni specifica soluzione algoritmica, ponendo in evidenza gli aspetti legati alla gestione di grandi quantità di dati e al progetto di algoritmi che operano su memorie gerarchiche;

• Crawling
• Parsing
• La Lista Invertita: definizione e algoritmi di costruzione
• Collezioni documentali dinamiche
• Risoluzione di query base, ottimizzazioni e caching: Booleana, Frasi, Proximity, Wildcard
• Occupazione in spazio delle Liste Invertite, Gap coding, tecniche di compressione, Glimpse
• Compressione di documenti: Huffman, Huffword, Gzip, Bzip, CGrep
• Tecniche di ranking testuale: TF-IDF, metodo del coseno, Relevance feedback e metodo di Rocchio
• Valutazione di un motore di ricerca: Precision vs. Recall, Interpolated precision e F-measure
• Velocizzazione di algoritmi di ranking: Latent Semantic Indexing e proiezioni casuali
• Tecniche di ranking basate sulla struttura del grafo del Web: PageRank, HITS, Salsa
• Clustering, Trawling e Classificazione (cenni)

Il corso farà riferimento a tre libri di testo, più una serie di appunti/articoli, e copie di slide disponibili sul sito del corso:

1. Modern Information Retrieval. R. Baeza-Yates e B. Ribeiro-Neto. Addison Wesley, 1999. [Cap. 1, 2, 3 e 5]
2. Managing Gigabytes. I.H. Witten e A. Moffat e T.C. Bell. Morgan Kaufmann, 1999. [Cap. 2, 3, 4 e 5]
3. Mining the Web: discovering knowledge from hypertext data. S. Chakrabarti. Morgan Kaufmann, 2003. [Cap. 2]

L’esame consiste di un progetto o di una prova seminariale, più un colloquio orale sui temi trattati nel corso