Strumenti Utente

Strumenti Sito


magistraleinformatica:ir:air08:start

Algoritmi per Information Retrieval 2008/2009

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.

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? 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, Locality Preserving FC solo sez 3.2 e no teo 7
Motori di Ricerca: Memorizzazione dei Postings e risoluzione di Query. slides,articolo
Motori di Ricerca: Text-based ranking, Link-based ranking. Qualità dei risultati: Precision, Recall, F-measure. Visualizzazione snippets e loro clustering. slides, articolo
Miscellanea: Latent Semantic Indexing e Random Projections. slides, articolo senza (SVD updating)
Miscellanea: Web SPAM, Web Advertising. slides
Ricapitolazione argomenti Parte 1: slides con animazioni, Parte 2:slides con animazioni
magistraleinformatica/ir/air08/start.txt · Ultima modifica: 26/03/2010 alle 15:08 (9 anni fa) da peppe