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) = {[E1v1,,…Envn]} 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