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:

• Anatomia di un motore di ricerca e tecniche di indicizzazione.
• Raccolta di informazioni: problemi algoritmici, tecnici e sociali nella creazione di crawler.
• Strategie di visita a confronto.
• Filtri di Bloom.
• Alberi di fusione strutturati a registri (LSM trees).
• Struttura globale del web e strumenti algoritmici per la sua analisi.
• Rappresentazione del grafo del web: problemi di compressione.
• Crawler paralleli e distribuiti. Tecniche di hashing coerente.
• Centralità di reti: vicinanza, centralità armonica, Katz, PageRank, autovettore dominante, ecc.
• Tecniche per la costruzione di indici inversi.
• Metodologie per la costruzione di dizionari di grandi dimensioni: tabelle di hash minimale perfetto ordinate, dizionari di prefissi, compressione lessicografica.
• Codici privi di prefissi per la compressione di indici: unario, Elias γ, Elias δ, Golomb, ecc.
• Tecniche di ranking testuali (TF/IDF, BM25, LSI, coseno, ecc.).
• Rappresentazione di Elias–Fano e indici quasi-succinti.
• Sistemi di numerazione asimmetrica.
• Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.

Informazioni più complete sull'effettivo contenuto del corso sono disponibili nella sezione successiva. Per informazioni/chiarimenti, dopo avere letto alcune indicazioni di base potete scrivere al docente (Sebastiano Vigna).

Telegram

Per comunicazioni urgenti verrà utilizzato un canale Telegram.

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 l'indicizzazione della semantica latente, le parti teoriche su autovalori/autovettori e catene di Markov (ma chiaramente dovete averne un'idea per spiegare le centralità spettrali, PageRank, etc.), la compressione aritmetica, i vettori di suffissi, le tecniche di quantizzazione dei prodotti e i mondi piccoli navigabili gerarchici (HNSW).

Per riferimento, per il corso di laurea in informatica potete tenere in considerazione innanzitutto le dispense, i lucidi sulla compressione dei grafi del web, quelli su HyperBall, e quelli sulla rappresentazione di Elias–Fano. 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 e i paragrafi 8.1-8.4. I capitoli 20 e 21 si sovrappongono in parte alle dispense sono più completi e possono essere un'utile lettura aggiuntiva.

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 libro di Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press, 2008. Le dispense e i lucidi del corso di Manning a Stanford sono una miniera di informazioni utili.

Sono anche disponibili i lucidi sulla compressione dei grafi del web, quelli su HyperBall, quelli su la rappresentazione di Elias–Fano e gli indici quasi-succinti e i lucidi animati dell'esempio di esfoliazione.

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 lavoro che descrive il nostro crawler affronta diverse questioni avanzate, e il codice è disponibile.

Costruzione e compressione di indici

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

Ranking esogeno

La parte di rassegna del nostro articolo sugli assiomi per la centralità contiene una discussione dettagliata degli metodi di ranking discussi a lezione (Seeley, l'autovettore dominante, Katz, PageRank, vicinanza, centralità armonica).

Ranking endogeno

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.

Quantizzazione di prodotti

È disponibile una rassegna molto chiara, così come maggiori dettagli sui multi-indici e una descrizione degli hierarchical navigable small-wolrd graphs.

Vettori di suffissi

Il lavoro di Kärkkäinen, Sanders e Burkhardt descrive un algoritmo relativamente semplice che costruisce un vettore di suffissi in tempo lineare.

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.