Web algorithmics

A.A. 2019/2020
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Inglese
Obiettivi formativi
L'insegnamento 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.
Risultati apprendimento attesi
Lo studente dovrà essere in grado di progettare e implementare un crawler e un indicizzatore di testi di grandi dimensioni, con particolare attenzione agli algoritmi utilizzati per ordinare i risultati.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre
Programma
- 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.
Prerequisiti
Algoritmi di base su grafi (visite). Fondamenti di algebra lineare (matrici, autovalori, autovettori).
Metodi didattici
Lezioni frontali.
Materiale di riferimento
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. Sono inoltre disponibili i lucidi utilizzati per le lezioni monografiche. Tutto il materiale è raggiungibile dal sito del docente.
Modalità di verifica dell’apprendimento e criteri di valutazione
Esame orale. L'esame si basa su un sottoinsieme degli argomenti del corso pubblicato di anno in anno sul sito web del docente.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Siti didattici