Algoritmica per il web
A.A. 2018/2019
Obiettivi formativi
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.
Risultati apprendimento attesi
Non definiti
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Primo semestre
STUDENTI FREQUENTANTI
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.
- Ranking di grafi: vicinanza, PageRank, HITS, eccetera.
- Link spamming e adulterazione avversariale dei meccanismi di ranking.
- 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: Elias, Golomb, compressione aritmetica.
- Rappresentazione di Elias-Fano e indici quasi-succinti.
- Tecniche di ranking testuali (LSI, coseno, Clarke-Cormack, ecc.).
- Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.
- 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.
- Ranking di grafi: vicinanza, PageRank, HITS, eccetera.
- Link spamming e adulterazione avversariale dei meccanismi di ranking.
- 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: Elias, Golomb, compressione aritmetica.
- Rappresentazione di Elias-Fano e indici quasi-succinti.
- Tecniche di ranking testuali (LSI, coseno, Clarke-Cormack, ecc.).
- Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.
Informazioni sul programma
-
Propedeuticità
Algoritmi
Prerequisiti
Il corso richiede una conoscenza delle tecniche algoritmiche di base e dei protocolli di rete. L'esame è orale.
Metodi didattici
Lezioni
Materiale di riferimento
STUDENTI NON FREQUENTANTI
Vedi sito web.
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.
- Ranking di grafi: vicinanza, PageRank, HITS, eccetera.
- Link spamming e adulterazione avversariale dei meccanismi di ranking.
- 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: Elias, Golomb, compressione aritmetica.
- Rappresentazione di Elias-Fano e indici quasi-succinti.
- Tecniche di ranking testuali (LSI, coseno, Clarke-Cormack, ecc.).
- Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.
- 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.
- Ranking di grafi: vicinanza, PageRank, HITS, eccetera.
- Link spamming e adulterazione avversariale dei meccanismi di ranking.
- 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: Elias, Golomb, compressione aritmetica.
- Rappresentazione di Elias-Fano e indici quasi-succinti.
- Tecniche di ranking testuali (LSI, coseno, Clarke-Cormack, ecc.).
- Indici di sottostringhe: trie, alberi di suffissi e vettori di suffissi.
Prerequisiti
Il corso richiede una conoscenza delle tecniche algoritmiche di base e dei protocolli di rete. L'esame è orale.
Materiale di riferimento
Vedi sito web.
Docente/i