Sistemi Informativi LS
7 Marzo 2005
Università di Bologna
Crawling the Hidden Web
Claudio Fusconi
Michele Orselli (relatore)
Alberto Renzi
Da: Crawling the Hidden Web
Sriram Raghavan Hector Garcia-Molina
Computer Science Departement
Stanford University
Agenda
Publicly Indexable Web e Hidden Web
Hidden Web Crawlers
Modello Generico di un Crawler per Hidden Web
HiWE: Hidden Web Exposer
LITE: Layout-based Information Extraction
Prove sperimentali
Conclusioni
Introduzione
I crawler sono programmi che navigano il web, creando
poi repository locali della porzione di web esplorata;
percorrono quello che viene chiamato Publicly Indexable
Web ossia tutte le pagine raggiungibili tramite link.
Con Hidden Web ci si riferisce a tutte quelle informazioni
non raggiungibili direttamente ma solo tramite form
Parte più estesa del web
500 x PIW [BrightPlanet 2000]
InvisibleWeb.com elenca oltre 10.000 database
Come posso realizzare un crawler che riesca a raggiungere
anche l’Hidden Web?
Sfide
Sfide e
e approcci
approcci
Differenze rispetto ad un crawler PIW:
1. Capacità di processare, analizzare e interagire con i
form
2. Raccolta e gestione dei dati di input per le query
Approccio basato su:
Task-specificity: consiste nel selezionare una porzione
dell’hidden web ed estrarne i contenuti basandosi sui
requisiti di una particolare applicazione
Human-assistance: configuriamo il Crawler e gli forniamo
valori ad hoc per la generazione delle query
Un Modello Generico
Hidden Web Crawler
Form page
Form
Representation
Task
specific
database
Download form
Match
Set of value
assignments
Form submission
Web
search
front-end
repeat
Response
Analysis
Repository
Download response
Response
page
Hidden
Database
Form Representation
Form Representation
Task
specific
database
Match
Set of value
assignments
Response Analysis
Titolo:
Supporto
Storico
Avventura
Commedia
DVD
VHS
Submit
ogni volta che il crawler incontra una form deve estrarne i
contenuti e costruirne una propria rappresentazione
interna F:
F=({E1,E2,…En},S,M)
E1,E2,…En = elementi contenuti nella form
S = informazioni di submission
M = meta-informazioni sulla pagina
Repository
Genere:
Form Representation:
Reset
Task Specific DB
Task specific database:
Form Representation
Task
specific
database
contiene tutte le informazioni necessarie alla
formulazione di query di ricerca per quel particolare
task.
Match
Set of value
assignments
Response Analysis
Repository
La struttura del database così come la forma dei dati
che contiene dipende dalla specifica implementazione.
Come vedremo successivamente, HiWE utilizza un
labeled fuzzy set.
Stone
Polanski
Scott
Alexander
Blade Runner
Matrix
Aliens
Matching Function
Matching function:
Form Representation
Task
specific
database
prende in ingresso la rappresentazione interna del form e
il contenuto del DB e produce in output una serie di
possibili valori di assegnamento:
Match
Set of value
assignments
Response Analysis
Repository
Match(({E1,E2,…En},S,M),D) = {[E1v1,,…Envn]}
I valori così ottenuti vengono utilizzati per riempire il form.
Il procedimento si ripete ciclicamente fino al verificarsi di
una condizione di terminazione
Titolo:
Genere:
Supporto
Storico
Avventura
Commedia
DVD
VHS
Submit
Stone
Reset
Alexander
Scott
Polanski
Aliens
Response Analysis
Form Representation
Task
specific
database
Match
Set of value
assignments
Response Analysis
Repository
Response Analysis:
la risposta a un invio di una form viene
ricevuta e memorizzata nel repository
Vengono distinte le pagine che
contengono risultati della ricerca e pagine
che contengono messaggi di errore.
Il feedback può essere utilizzato per fare
tuning della funzione di matching
Valutazione delle Performance
Come misuro le performance dei Hidden Web Crawler?
Uso gli stessi indicatori dei crawler per il PIW (velocità, scalabilità,
importanza delle pagine…)?
No, si preferisce usare la submission efficiency
Ntotal = numero di richieste inviate (submit)
Nsuccess = numero di richieste inviate la cui pagina di
risposta contiene uno o più risultati positivi
SEstrict = Nsucces / Ntotal
Conservativo
Nvalid = numero di form semanticamente corrette
SElenient = Nvalid / Ntotal
Costoso
HiWE: Hidden Web Exposer
L’Università di Stanford ha costruito un prototipo chiamato
HiWE (Hidden Web Exposer)
Caratteristiche:
 Utilizza una Label Value Set (LVS) table come DB interno
 Label matching realizzato tramite un algoritmo “minimum edit distance”
 Tecnica layout-based per l’estrazione dell’informazioni dalle form (LITE)
LVS Table
Label1
URL List
URL 1
Value-Set1
URL 2
Label2
…
Labeln
WWW
Value-Set2
URL N
...
Value-Setn
Parser
Crawl Manager
LVS Manager
Form Analyzer
Form Processor
Form submission
Feedback
Custom data sources
Response Analyzer
Response
HiWE - Rappresentazione del Form
Dato un form F=({E1,E2,…En},S,Ø) vengono raccolte due informazioni per ogni suo
elemento:
1. Label(Ei): descrizione testuale
2. Dom(Ei): insieme di valori che possono essere assegnati ad Ei
Possiamo distinguere due tipi di domini:
1.Elementi con dominio finito (checkbox, radiobutton, menu a tendina)
2.Elementi con dominio infinito (textbox, textarea)
Elemento E1
Label(E1) = “Titolo”
Titolo:
Dom(E1) = { s | s stringa di testo}
Genere:
Supporto
Giallo
Avventura
Commedia
DVD
VHS
Submit
Reset
Elemento E2
Label(E2) = “Genere”
Dom(E2) = { “Giallo”, “Avventura”, “Commedia” }
Elemento E3
Label(E3) = “Supporto”
Dom(E3) = { “DVD” , “VHS” }
Hiwe – Task-specific DB
Informazioni task specific organizzate in categorie, ognuna identificata da una label 
tabella LVS (Label Value Set)
Per ogni riga (L,V)
– L  label
– V = {v1, … , vn}  fuzzy set
Funzione di appartenenza Mv assegna ad ogni elemento di V un peso nel range [0,1]
Titolo:
Genere:
Supporto
Label
Giallo
Avventura
Commedia
DVD
VHS
Submit
Reset
Titolo
Fuzzy value set
{ Blade Runner (1.0) , … , }
Label Value Set (LVS) Table
Hiwe – Matching function (1)
Matching function
Per ogni elemento Ei si calcola un fuzzy set Vi (possibili assegnamenti ad Ei)
In caso di elementi con dominio infinito verifica la corrispondenza tra una label presente nel
db e una ricavata dal form
Due attività:
• Label Matching (soglia σ)
• Ranking
Label
titolo { Aliens (0.95),…, Matrix(0.8) }
Titolo:
Genere:
Supporto
Giallo
Avventura
Commedia
DVD
Label Value Set (LVS) Table
V1 = { Aliens (0.95),…, Matrix(0.8) }
V2 = {Giallo (1), Commedia (1), Azione (1)}
VHS
Submit
Fuzzy value set
Reset
V3 = {DVD (1), VHS(1) }
Match (F) = {[E1  v1, …, En  vn]: vi  Vi }
Hiwe – Matching function (2)
Ranking value assignments
Calcolo di uno score che quantifica la “bontà” di un assegnamento di valori alle
variabili del form utilizzando i pesi dei valori. Ciò permette, utilizzando un  min di
migliorare l’efficenza di invio, non inviando delle combinazioni di valori il cui rank è
al di sotto di questa soglia.
Funzioni di aggregazione:
Rank ([E1  v1, …, En  vn]) =
– Min{M(vi)}
(Fuzzy conjunction)
– 1/n x  M(vi)
(Average)
– 1 -  (1 - M(vi))
(Probabilistic)
Esempio (fuzzy conjunction) con min = 0.9 :
([E1  Aliens (0.95), E2  Azione (1), E3  DVD (1)]) = 0.95
([E1  Matrix (0.8), E2  Azione (1), E3  DVD (1)]) = 0.8
HiWE – LVS table
HiWE supporta vari meccanismi per inserire oggetti nella tabella LVS:
Explicit Initialization
Si possono inserire label e relativi set di valori durante l’ inizializzazione del
crawler. Questa tecnica è adatta per inserire elementi che è molto probabile
incontrare in una particolare ricerca
Built-in entries
Inserisco categorie comuni e spesso usate (date, giorni della settimana, ecc)
Wrapped data sources
Il LVS Manager può comunicare e ricevere nuovi elementi per la tabella LVS
attraverso interrogazioni di sorgenti dati esterne. Supporto a due operazioni:
1.Inserimento nuove categorie
2.Ampliamento categorie esistenti
Crawling experience
Se abbiamo nella LVS una label con un dominio chiuso, possiamo usare
questi ultimi come set di valori per una label simile ma con infiniti valori
LVS table – Wrapped data sources
LVS
….
Regioni Marche , Umbria, Molise
,…,Lazio
Servizi di catalogazione online come le Yahoo directory
e le Open Directory Project, hanno una struttura che
permette di usarle per popolare in modo efficiente la
tabella LVS.
….
LVS Manager
Wrapper
2-Umbria
Yahoo
Directory
Abruzzo
Molise
Categorie
…
Lazio
R1)…, Regioni d’Italia {Abruzzo,…,Lazio} ,…
R2)…, Regioni d’Italia {Abruzzo,…,Lazio} ,…
R3)…, Regioni d’Italia {Abruzzo,…,Lazio} ,…
R1∩R2∩R3
LVS Table - Crawler Input
Label
Fuzzy value set
Genere Giallo (1) , Avventura (1) , Commedia (1)
Label Value Set (LVS) Table
Titolo:
Genere:
Supporto
Titolo:
Giallo
Avventura
Commedia
Regista:
DVD
VHS
Submit
Genere:
Reset
Submit
Reset
HiWE – Computing weights
Quando inseriamo un elemento nella LVS dobbiamo anche assegnarli un peso.
seconda della tecnica che ho usato per inserire l’elemento avrò casi diversi:
Built-in / Explicit Initialization
Il peso dell’oggetto è definito a priori (solitamente 1) e non varia
Wrapped data sources
Il peso inizialmente è calcolato dal Wrapper e viene incrementato/decrementato in
caso di successo/insuccesso
Crawling Experience
Tre casi:
1. Estrazione di label(E) e calcolo LabelMatch(E)  inserimento nuovi valori e
aggiornamento valori esistenti
2.Estrazione di label(E) e nessun match  nuova entry in LVS
3. Fallimento nell’estrazione di una label  calcolo insieme più “vicino” e
aggiornamento valori
A
HiWE – LITE
LITE (Layout-based Information Extraction)
 Estrae il testo basandosi sul layout della form
 Strategia: pruning dell’albero DOM per isolare il form
Problemi:
 il layout della pagina non si riflette nel codice
 Tag con semantica poco usati (caption, label)
text1
Layout
Pruning
text4
Pagina con form
Label(E1) = text1
Label(E2) = text4
Form
E1
text2
text3
E2
Ranking
Candidati
E1  {text1, tex2}
E2  {text3, text4}
HiWE - Parametri di configurazione
1
Siti da navigare
2
Inizializzazione tabella LVS
3
Inizializzazione data source (wrapped)
4
Soglia per label matching (σ)
5
Soglia di ranking (ρmin)
6
Minima dimensione form (α)
7
Funzione di aggregazione
LVS Table
Label1
URL List
URL 1
Value-Set1
URL 2
Label2
…
Labeln
WWW
Value-Set2
URL N
...
Value-Setn
Parser
Crawl Manager
LVS Manager
Form Analyzer
Form Processor
Form submission
Feedback
Custom data sources
Response Analyzer
Response
HiWE – Esperimenti
Prove sperimentali su tre differenti task:
1.
2.
3.
Articoli, reports e white papers relativi alle industrie di semiconduttori
(relativi agli ultimi 10 anni)
Recensioni articoli e informazioni storiche su films diretti da registri
vincitori di Oscar (negli ultimi 30 anni)
Report tecnici su DB di 30 dipartimenti di informatica (degli ultimi 5 anni)
HiWE – Effetti della funzione di Ranking
 fuz migliore efficienza
 avg riporta più risultati, ma è meno efficiente (utile
se l’obiettivo è recuperare più dati possibili)
 prob scarsi risultati
HiWE - Effetto di α
HiWE – Effetti su LVS del crawler
Conclusioni
Crawler PIW vs Hidden web crawler
Modello generico per un crawler per Hidden web
HiWE come Hidden web crawler
Limiti:
– Non considera riempimenti parziali delle form
– Non tiene conto delle dipendenze tra campi delle form
Search Engines for the Invisible Web
AlltheWeb
– http://www.alltheweb.com
Bright Planet
– http://www.brightplanet.com/
Direct Search
– http://www.freepint.com/gary/direct.htm
Google Scholar
– http://scholar.google.com
IxQuick
– http://ixquick.com/
Search-22
– http://www.search-22.com
Search Adobe PDF Online
– http://searchpdf.adobe.com/
Turbo10
– http://turbo10.com
Vivisimo
– http://www.vivisimo.com
Bibliografia
• “Crawling the Hidden Web” Sriram Raghavan Hector Garcia-Molina
Computer Science Departement Stanford University, Available at
http:// dbpubs.stanford.edu/pub/2001-19
• S. Raghavan and H. Garcia-Molina. “Crawling the hidden web”
Technical Report 2000-36, Computer Science Dept., Stanford
University, Dec. 2000. Available at
http://dbpubs.stanford.edu/pub/2000-36.
• J. Cho and H. Garcia-Molina. “The evolution of the web and
implications for an incremental crawler” In Proc. of the 26th Intl. Conf.
on Very Large Databases, 2000.
• J. Cho, H. Garcia-Molina, and L. Page. “Efficient crawling through url
ordering” In Proc. of the 7th Intl. WWW Conf., 1998.
Questions
Scarica

Document