Attenzione! Il gruppo di discussione del corso algoweb2017 è stato creato su Google Groups.

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 l'indicizzazione della semantica latente e la parte sui vettori di suffissi.

Per riferimento, potete tenere in considerazione innanzitutto le dispense (esclusi i le parti sui dettagli del modello probabilistico e i capitoli 7, 11, 12, 13 e 14), i lucidi su HyperBall e la parte di definizioni dell'articolo sugli assiomi per la centralità fino a PageRank. 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 capitoli 18 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. Le dispense e i lucidi del corso di Manning a Stanford sono una miniera di informazioni utili.

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 e quelli su HyperBall.

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

Sono disponibili i lucidi su la rappresentazione di Elias–Fano e gli indici quasi-succinti.

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 informazioni più dettagliate sul modello probabilistico (un po' negletto) c'è un eccellente survey. 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.

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.

Vettori di suffissi

Il lavoro di Kärkkäinen and Sanders 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.