Algoritmica per il web

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.
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 indici distribuiti di grandi dimensioni.
Metodologie per la costruzione di dizionari di grandi dimensioni: tabelle di hash minimale perfetto ordinate, dizionari di prefissi, compressione lessicografica.
Codici istantanei per la compressione di indici: unario, Elias γ, Elias δ, Golomb, ecc.
Rappresentazione di Elias-Fano e indici quasi-succinti.
Tecniche di ranking testuali (TF/IDF, BM25, LSI, coseno, ecc.).
Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.
Quantizzazione dei prodotti vettoriali e database vettoriali.