Motori di Ricerca
presente e futuro prossimo
Cosa è un motore di ricerca ?
Paolo Ferragina, Università di Pisa
Un lavoro storico: Brin & Page
Paolo Ferragina, Università di Pisa
[1998]
Motore di Ricerca: struttura
?
Archivio Pagine
Crawler
Query
Analizzatore
pagine
Indicizzatore
Risolutore
Controllo
Testo
Utilità
Struttura
Paolo Ferragina, Università di Pisa
Analizzatore
Rilevanza
Il Web
 “Surface Web”: 25 ÷ 75 Terabytes (1Tb = 1000 Gb)

6 miliardi di pagine (cambiano circa 10 milioni al giorno)

Pagina in media 5 ÷ 40Kb, #links ~ 10

Circa il 23% delle pagine è duplicato
 “Hidden Web”: circa 500 volte più grande

Siti intranet, database, pagine dinamiche,…

Circa 4,200 Tb di dati testuali interessanti
Paolo Ferragina, Università di Pisa
Una immagine pittorica del Web
Paolo Ferragina, Università di Pisa
Alcuni dati
Paolo Ferragina, Università di Pisa
Velocità di cambiamento
[snapshot settimanale nel 2004: 154 web sites, 35 mil pg, 65Gb]
Normalizzata
rispetto
prima
settimana
Paolo Ferragina, Università di Pisa
Motori di Ricerca
presente e futuro prossimo
Cosa è un crawler ?
Paolo Ferragina, Università di Pisa
Fase di Crawling
 Numerosi problemi di progettazione:

Copertura: Quali pagine occorre visitare ?

Aggiornamento: Quanto spesso occorre visitarle ?

Invadenza: Come minimizzare il carico dei siti visitati ?

Efficienza: Come parallelizzare il processo di “crawling” ?

Scalabilità: Come gestire il “flusso” di pagine ?
Paolo Ferragina, Università di Pisa
“Ciclo di vita” di un Crawler
Link Extractor
Downloader
while(<ci sono pagine da esaminare nel repository>){
<prendi una pagina p>
<estrai i link contenuti in essa>
<inserisci i link estratti in una coda, ciascuno
con una priorità dipendente dalla politica scelta>
<marca p come pagina da cui abbiamo estratto i link>
}
while(<ci sono link assegnati dal Manager>){
<estrai i link>
<scarica le pagine pi dalla rete>
<invia le pi al page repository>
}
Crawler Manager
<estrai un gruppo di link dalla coda in ordine di priorità>
while(<ci sono link nel gruppo>){
foreach link u {
if ( (u  “pagine già viste” )
|| ( u  “pagine già viste” && <sul Web server la pagina è più recente> )
&& ( <u è un link accettato dal robot.txt del sito>) ) {
<risolvi u rispetto al DNS>
<invia u alla coda dei downloaders>
} }
Paolo Ferragina, Università di Pisa
Politica di selezione delle pagine
 Data una pagina P, definire quanto sia “buona”.
 Esistono molte metriche:

Guidate dal topic coperto dal motore

Guidate dalla popolarità

BFS, DFS, Random

Strategie combinate
4
1
3
2
BFS
Paolo Ferragina, Università di Pisa
7
7
6
5
1
5
2
DFS
6
4
3
Raggiungimento di pagine interessanti
Paolo Ferragina, Università di Pisa
Alcuni risultati
Paolo Ferragina, Università di Pisa
Focused Crawling
 Si scelgono selettivamente le pagine sulle quali continuare la visita,
in accordo a un insieme di topic rilevanti definiti apriori.

I topic sono specificati mediante documenti campione

I topic sono specificati mediante indirizzi
 Risparmio di risorse di rete e di hardware.
 Esempi di crawler open-source

Nutch, also used by Yahoo

Hentrix, used by Archive.org
Paolo Ferragina, Università di Pisa