Programma

Il corso si propone di mettere lo studente a contatto con tecniche avanzate relative alla raccolta di grandi collezioni documentali e alla costruzione di motori di ricerca, con particolare attenzione al web e ai suoi meccanismi di ranking. Il corso richiede una conoscenza delle tecniche algoritmiche di base e dei protocolli di rete. Verrà trattato un sottoinsieme degli argomenti seguenti, anche in base all'interesse degli studenti:

Per informazioni/chiarimenti, dopo avere letto alcune indicazioni di base potete scrivere al docente (Sebastiano Vigna).

Modalità d'esame

L'esame è orale. La data è fissata tramite appuntamento (gli appelli sono, di fatto, puramente nominali).

Il materiale per l'esame comprende gli argomenti spiegati a lezione, esclusa la parte discorsiva sul crawling, i dettagli sulle liste di salti (skip list) a più livelli, la costruzione degli hash perfetti minimali monotoni (ma è inclusa la costruzione generica contenuta nelle dispense!), l'algoritmo di Tarjan e i dettagli degli algoritmi di compressione per i grafi del web.

Per riferimento, potete tenere in considerazione innanzitutto le dispense (esclusi i capitoli sui dettagli del modello probabilistico e quelli sugli algoritmi di prossimità). Dal Manning (vedi più sotto) il capitolo 1, il capitolo 2 fino a 2.4.1 escluso, i paragrafi 4.1-4.3, il paragrafo 5.3 (che si sovrappone in parte alle dispense), il paragrafo 6.2-6.4.3, i paragrafi 8.1-8.5 e i capitoli 18, 20 e 21 (che si sovrappongono in parte alle dispense; il 20 contiene cenni alla compressione dei grafi).

Testi consigliati

Dato che quasi tutti gli argomenti trattati sono relativamente recenti, o oggetto di ricerca, non è possibile dare un testo unitario. Ci sono però numerosi libri, articoli e dispense in linea che coprono gli argomenti discussi, primo fra tutti il nuovo libro di Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press, 2008. C'è anche un interessantissima bibliografia ragionata scritta da Moffat, Zobel e Hawking (tipi che sanno il fatto loro).

Sono anche disponibili i lucidi sulla compressione dei grafi del web.

Standard di rete

Gli standard su cui sono basati Internet e il web sono disponibili sotto forma di RFC o di raccomandazioni pubblicate dal World Wide Web Consortium.

Crawling

Il classico lavoro di Allan Heydon and Marc Najork, Mercator: A Scalable, Extensible Web Crawler (World Wide Web 2(4):219-229, 1999), sul crawler di Altavista è un buon inizio, e contiene molte idee divenute poi classiche. Un lavoro molto recente (2008) presenta un crawler basato su strutture dati ad hoc che, decisamente, straccia la concorrenza.

La rassegna di Hector Garcia-Molina e Junghoo Cho, Parallel Crawlers, sebbene non contenga nuove idee offre una tassonomia ragionata di alcune tecniche per costruire crawler distribuiti.

Infine, l'articolo su UbiCrawler contiene una descrizione dettagliata dell'utilizzo di tecniche di hashing coerente.

Lo stracitato lavoro di Marc Najork and Janet L. Wiener, Breadth-First Search Crawling Yields High-Quality Pages, presentato al 10th International World Wide Web Conference, 2001, argomenta a favore delle visite in ampiezza, anche se il nostro lavoro sul PageRank indotto da crawl parziali rimette in discussione le valutazioni fatte precedentemente.

Ovviamente, girarsi un po' i siti personali degli autori suddetti può portare a scoprire altri lavori interessanti. Dato che si tratta quasi sempre di lavori di tipo ingegneristico/implementativo, la lettura è alla portata di chiunque.

Costruzione e compressione di indici

Il classico Managing Gigabytes, di Ian H. Witten, Alistair Moffat e Timothy C. Bell, pubblicato da Morgan Kaufmann (ISBN: 1558605703), è un classico sulla costruzione e compressione di indici inversi. È un po' datato in alcune parti (il capitolo sulla costruzione degli indici, in particolare, è da evitare), ma in genere è molto lucido e chiaro.

Per questioni più generali riguardanti il recupero delle informazioni, Modern Information Retrieval, di Ricardo Baeza-Yates e Berthier Ribeiro-Neto, pubblicato da Addison Wesley (ISBN: 020139829X), non è affatto male, sebbene qualche capitolo del libro sia un po' “fuffico” (ma credo possiate scoprire facilmente quali).

Il corso di Algorithms for Massive Data Sets di Princeton fornisce molte dispense utili, in particolare su codifica di Huffman e codifica aritmetica, codici istantanei per indici inversi, modelli di descrizione degli scarti (gap) e filtri di Bloom.

Per quanto riguarda le liste di salti perfette compresse, c'è il nostro preprint.

Ranking esogeno

Esistono letteralmente centinaia di libri sulle catene di Markov e le loro applicazioni. Sono disponibili le dispense utilizzate al MIT per il corso di probabilità e processi stocastici, che forniscono un'introduzione autocontenuta al problema. Il classico di Eugene Seneta, Non-negative Matrices and Markov Chains, pubblicato da Springer (ISBN: 0-387-29765-0), contiene una trattazione molto completa dell'argomento.

La rassegna di Amy Langville e Carl Meyer è un buon punto di riferimento per PageRank, HITS e SALSA.

Ranking endogeno

Il testo di Baeza-Yates e Ribeiro-Neto contiene una descrizione abbastanza dettagliata di molti modelli di recupero delle informazioni. Per informazioni più dettagliate sul modello probabilistico (un po' negletto) c'è un articolo degli inventori del modello (non proprio leggibilissimo). Per capire meglio una versione realistica di BM25, c'è un articolo recente di Robertson, Zaragoza e Taylor in cui gli autori estendono la formula al caso multi-indice.

Per quanto riguarda il reticolo degli intervalli, l'articolo originale di Clarke, Cormack e Burkowski è un punto di partenza, anche se la descrizione del reticolo degli intervalli è decisamente farraginosa. Anche il resoconto dei risultati ottenuti a TREC-4 è molto interessante. Gli algoritmi quasi lineari pigri per il calcolo delle operazioni su anticatene di intervalli saranno descritti in un nostro prossimo articolo, e sono disponibili i lucidi utilizzati a lezione.

L'indicizzazione della semantica latente è descritta in un celebre lavoro di Scott Deerwester, Susan T. Dumais, George W. Furnas, Thomas K. Landauer e Richard Harshman.

Alberi e vettori di suffissi

Di nuovo, il testo di Baeza-Yates e Ribeiro-Neto contiene le informazioni essenziali, anche se, trattandosi di un campo di ricerca in fermento, nuovi risultati importanti appaiono continuamente negli atti dei principali convegni.

Software

Molti degli argomenti del corso descrivono gli algoritmi, i codici e le tecniche utilizzate nel software prodotto da membri del LAW. MG4J è un motore di indicizzazione a testo pieno; WebGraph è un framework per la compressione dei grafi del web.