Strumenti Utente

Strumenti Sito


air:start

Questa è una vecchia versione del documento!


Algoritmi per Information Retrieval [AA293]

Docente: 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.

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).
    • Capitoli: 2 e 4.3-4.5
  • 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? Google, The Economist,Time (parte a), Time (parte b)
Modelli di calcolo: External-memory model, Data Streaming model, Cache-Oblivious model slides in pdf e pps
Alcuni problemi interessanti: Max subarray, Elementi di max-frequenza, DB vs IR-approach al progetto di un motore di ricercaBentley
Il problema dell'ordinamento su grandi collezioni di dati: single vs multiple disks, disk striping, multi-way merge-sort, distribution sort, permuting vssorting, limiti inferiori Greed Sort (saltare i dettagli del ColumnSort e le dimostrazioni), Libro Vitter (saltare il dettaglio delle formule 5.2 e 5.4),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 pdf e pps
CGrep: Byte-Aligned & Tagged Huffword, Ricerca sul compresso CGrep
Alcuni algoritmi di pattern-matching: Karp & Rabin (ricerca esatta e fingerprinting), Agrep (ricerche regex e approssimate) KR,AGrep
Un semplice compressore: ordina simboli per frequenza e codifica i loro ranghi (anche (s,c)-dense codes su slides)codes
Compressione in streaming: Move-to-Front, Run-Length encoding (RLE)MTF
Arithmetic coding: statico, dinamico e schema PPM Sezione 2.4 e 2.5 (Prediction by Partial Matching) di Managing-Gigabytes, e slides in pdf e pps
Dictionary-based compression: LZ77, LZ78, LZW. Sezione 2.6 di Managing-Gigabytes, e slides in pdf e pps
Burrows-Wheeler Transform: properietà, costruzione e inversione. Il compressore Bzip2. Sezione 2.5 (Block-sorting compression) di Managing-Gigabytes, e articolo originale
Il grafo del Web: proprietà e compressione. slides
Compressione e Sincronizzazione di (collezioni di) file slides, rsync
Data Sketching e Data Streaming: Bloom Filter, Spectral Bloom Filter, Count Min Sketch, e loro applicazioni slides, Bloom Filter, Count Min Sketch
Full-indexing: definizione, suffix tree, suffix array, lcp array. Text mining. slides, Text Indexing
Motori di Ricerca: introduzione, struttura, e crawling. slides, Struttura, Crawling
Motori di Ricerca: parsing, modelli statistici dei testi (Zipf Law, Heaps Law, Luhn). slides
Motori di Ricerca: Inverted Lists = Dizionario + Postings. Indicizzazione del dizionario. slides
Motori di Ricerca: Memorizzazione dei Postings e risoluzione di Query. slides,articolo
Motori di Ricerca: Text-based ranking, Link-based ranking. slides, articolo, sez 4.3-4.5 in MG
Motori di Ricerca: Qualità dei risultati, Visualizzazione snippets e loro clustering. slides
Miscellanea: Latent Semantic Indexing. slides, articolo
Miscellanea: Web SPAM, Web Advertising. slides
air/start.1227697388.txt.gz · Ultima modifica: 26/11/2008 alle 11:03 (16 anni fa) da Paolo Ferragina