RICERCA ITALIANA     

Web Ram: web retrieval and mining

Università degli Studi di Roma "La Sapienza"

Abstract

Questo programma di ricerca è relativo ad un insieme di problemi aperti della ricerca contemporanea nel settore dell'information retrieval per il web (motori di ricerca). I problemi di cui ci vogliamo occupare sono sufficientemente importanti da meritare di essere studiati indipendentemente gli uni dagli altri ma, al contempo, essi presentano interazioni a vari livelli formando un tutto coerente:


1. Crawling:

- uno degli obiettivi del progetto è collezionare una serie di snapshot di porzioni ragguardevoli del web (ad es. il dominio .it) allo scopo di (a) studiare l'evoluzione temporale del web e (b) sviluppare tecniche algoritmiche che siano in grado di restituire documenti che non solo siano rilevanti (rispetto ad una data query) ma anche aggiornati

- un altro obiettivo è quello di mettere a punto strategie di crawling in grado di unire i pregi di approcci esistenti. In particolare si vuole sviluppare strategie che siano molto efficienti in termini di utilizzo della memoria ma al contempo siano "cortesi" e in grado di raccogliere subito pagine di alta qualità


2. Spam: si vuole sviluppare nuovi algoritmi che siano in grado di individuare lo spam e calcolare di conseguenza il rank delle pagine


3. Aggregazione di segnali: i motori di ricerca allo stato dell'arte usano una varietà di segnali che vengono aggregati in modo opportuno in modo da assegnare alle pagine web un unico valore di "rilevanza" (rispetto ad una data query). Abbiamo un nuovo e promettente approccio per combinare due dei segnali più importanti-- PageRank e cosine similarity-- che intendiamo perseguire. Ci vorremmo inoltre occupare del modo migliore di aggregare altri importanti segnali quali le query streams, le click streams ed informazioni estratte tramite text mining con particolare attenzione ad implementazioni scalabili e distribuite di tali schemi.

4. Nuove strutture dati per l'indicizzazione:

- posizionamento degli skip: la struttura base per indicizzare collezioni di testi, tra cui le pagine web, è la lista invertita. I cosidetti skip vengono usati per velocizzare le query booleane ma non sembra esserci nessuno studio sistematico per determinare il modo migliore di piazzare tali skip. Questo è quello che ci proponiamo di fare

- nearest neighbours: è ben noto che uno dei problemi base dell'information retrieval, trovare i documenti più rilevanti rispetto ad una data query, si riconduce al seguente problema geometrico: dato un insieme di punti ed un punto di query Q, trovare i K punti più vicini a Q. Abbiamo un algoritmo e delle strutture dati nuove e molto promettenti che intendiamo studiare e confrontare sperimentalmente con le soluzioni più avanzate dello stato dell'arte.


5. Fondamenti:

- Vogliamo studiare un modello generativo nuovo e molto promettente per la generazione di collezioni di testo

- Modelli per grafi finiti auto-simili: l'auto-similarità del web viene considerata da molti come un fatto acquisito ma in realtà non esiste nenache una definizione esatta di tale concetto. E' nostra intenzione proporre nuove definizioni in questo ambito, applicarle al grafo del web e corroborare empiricamente i vari modelli frattali che sono sttai proposti

- Assiomatizzazione dei sistemi di ranking: i sistemi di ranking per il web sono simili per loro natura ai sistemi di voto e di scelta sociale. Questi ultimi sono stati studiati utilizzando l'appoccio assiomatico che ha portato a importanti risultati quali il teorema di impossibilità di Arrow. Approcci simili per lo studio del PageRank sono comparsi di recente ed è nostra intenzione proseguire su questa linea esplorando possibili applicazioni ad altri sistemi di ranking <<<

Coordinatore Scientifico del Programma di Ricerca

Alessandro Panconesi Università degli Studi di ROMA "La Sapienza"

Obiettivo del Programma di Ricerca

L'information retrieval per il web (Web IR) è un'area molto vitale della ricerca informatica contemporanea di indubbio rilievo economico-industriale. Il suo sviluppo mostra chiaramente come molte delle idee cruciali da un punto di vista economico e applicativo sono nate grazie a ricerche matematicamente sofisticate di natura fondamentale svoltesi nell'ambito degli algoritmi e delle strutture dati. Ad esempio, è noto che il motore di ricerca Google è basato sul cosidetto PageRank, un meccanismo che assegna un livello di "qualità" alle pagine che in ultima analisi si riduce al calcolo efficiente della distribuzione stazionaria di una opportuna catena di Markov. Similmente, il successo commerciale di Teoma, uno dei leder monidali nel settore dei motori di ricerca, è basato su una implementazione efficiente di un ingegnoso algoritmo di ranking dovuto a Jon Kleinberg e noto come Hits. Gli esempi abbondano.

La ricerca in Web IR procede in modo naturale su quattro binari che, per essere maggiormente efficaci, è opportuno che interagiscano cointinuamente in un circolo virtuoso:

1. Raccolta dati: per raccogliere snapshot del web
2. Analisi dei dati: per eseguire analisi statistiche e data mining del web in modo da rilevare regolarità e peculiarità nella sua struttura
3. Algoritmi e strutture dati: per sviluppare nuove applicazioni allo stato dell'arte
4. Modelli matematici e loro validazione: per proporre modelli che riproducano caratteristiche cruciali del web

In larga misura il Web IR è una disciplina sperimentale basata sulla raccolta dei dati. A causa delle enormi dimensioni del web questa attività è essa stessa un'attività di ricerca ed è inoltre di importanza fondamentale in quanto (a) esistono ben pochi archivi pubblicamente accessibili e (b) il web cambia nel tempo e deve essere monitorato di conseguenza. Alcuni membri del nostro consorzio sono delle riconosciute autorità a livello mondiale in questo settore e pertanto il nostro progetto offre le migliori garanzie che questa attività possa essere intrapresa con successo.

Vale forse la pena di sottolineare come questo aspetto del nostro progetto abbia importanti ripercussioni di natura sociale. La tecnologia dei motori di ricerca è al momento dominata da un ristretto gruppo di multinazionali con enormi risorse a disposizione. Non sarebbe certamente auspicabile da un punto di vista sociale (nè per il Paese) se il know-how riguardante questa importante tecnologia diventasse monopolio esclusivo di pochi conglomerati. L'attività di collezione dei dati è VITALE per controbilanciare questa pericolosa tendenza in quanto essa assicura che il livello di conoscenza di queste tecnologie nel dominio pubblico possa rimanere al passo.

Sulla falsariga della suddivisione delineata in precedenza ecco le attività che intendiamo perseguire:

1. Raccolta dati:

1.1 E' nostra intenzione raccogliere degli snapshot del web e di renderli pubblicamente accessibili, in questo modo mettendo a disposizione una infrastruttura FONDAMENTALE per qualunque tipo di ricerca sul web a livello nazionale ed internazionale

1.2 Ci concentreremo sugli aspetti dinamici dell'evoluzione del web. Raccogliendo snapshot di porzioni consistenti del web (ad es. il dominio .it) ad intervalli regolari saremo in grado di fornire, per la prima volta, dei data set che sono il prerequisito indispensabile per lo studio dell'evoluzione del web. Grazie a ciò sarà anche possibile sviluppare applicazioni algoritmiche in grado di fornire risposte che non solo siano rilevanti (rispetto ad una data query) ma anche aggiornate

1.3 Vogliamo studiare nuove strategie di crawling che siano efficienti in termini di risorse (in particolare memoria interna)

2. Data mining e analisi statistica dei dati:

2.1 Come decritto in 1.2 vogliamo studiare l'evoluzione temporale del web

2.2 Spam detection: questo è uno dei temi principali della ricerca contemporanea nel settore. Abbiamo dei nuovi, promettenti approcci in grado di individuare pagine spam e di ridurre conseguentemente il loro ranking relativamente a pagine di buona qualità

3. Algoritmi e strutture dati:

3.1 Aggregazione di segnali: i moderni motori di ricerca utilizzano un insieme ampio di segnali che vengono combinati in un unico ranking. Abbiamo un approccio nuovo e molto promettente per combinare due dei segnali più importanti- PageRank e cosine similarity- che intendiamo esplorare. Esploreremo altresì l'aggregazione della link analysis con altre fonti quali le click stream, le query stream e le informazioni provenienti dal text mining. Siamo particolarmente interessati a sviluppare implementazioni scalabili e distribuite di tali schemi.

3.2 Posizionamento degli skip: la struttura dati fondamentale per l'indicizzazione dei web corpora è la lista invertita. I cosidetti skip sono largamente usati per velocizzare la risposta alle query di tipo booleano. Ciononostante non sembra esserci uno studio sistematico della migliore strategia del loro posizionamento e questo è ciò che intendiamo fare

3.3 Nearest Neighbours: E' noto che il compito fondamentale che un motore di ricerca deve assolvere-- trovare i documenti più rilevanti rispetto ad una data query-- si riconduce al seguente problema geometrico: dato un insieme di punti ed un punto di query Q, trovare i K punti più vicini a Q. Abbiamo nuovi algoritmi e strutture dati molto promettenti che intendiamo studiare e comparare sperimentalmente con le migliori soluzioni note per questo problema.

3.4 Calcolo distribuito del (Page) Rank: Consideriamo un sistema distribuito organizzato come una rete P2P i cui nodi sono a conoscenza di una porzione dell'intero grafo del web. Il problema è sviluppare algoritmi distribuiti efficienti dal punto di vista della comunicazione che consentano di combinare queste visioni parziali.

3.5 Spam-resilient ranking: Abbiamo un approccio nuovo e promettente per calcolare il ranking delle pagine web che è in grado di evitare lo spam


4. Modelli matematici e loro validazione:

4.1 Vogliamo studiare un modello nuovo e molto promettente per generare collezioni di testo. Questo è in stretto rapporto con 3.3

4.2 Modelli frattali per il grafo del web: la presunta auto-similarità del web viene considerata da molti come un dato acquisito ma in realtà non esistono neanche definizioni precise di auto-similarità. Vogliamo proporre nuove definizioni di auto-similarità e applicarle al caso del grafo del web ed inoltre vogliamo valutare attraverso un'accurata indagine sperimentale la rispondenza alla realtà delle varie definizioni sinora proposte.

4.3 Assiomatizzazione dei sistemi di ranking: il ranking del web è simile per sua natura ai sistemi di voto e di scelta sociale. Questi ultimi sono stati studiati con il metodo assiomatico, cosa che ha portato a celebri risultati quali il Teorema di Impossibilità di Arrow. Approcci simili sono recentemente venuti alla ribalta nel caso del PageRank ed è nostra intenzione proseguire questa linea di ricerca, estendendola ad altri metodi di ranking.

Sebbene ogni attività descritta meriti di esser perseguita in quanto tale, le attività nel loro insieme formano un quadro coerente. E' pertanto nel perseguirle insieme che si possono ricavare i maggiori benefici. Ad esempio, è sfruttando la distribuzione a potenza dell'in-degree osservata negli alberi generati dal processo di crawling che membri del nostro consorzio hanno potuto sviluppare una tecnica di compressione che, in virtù dei suoi soli 3 bit per link, è il vero detentore del record mondiale di compressione del garfo del web. A sua volta, queste tecniche di compressione hanno comportato crawling più efficienti creando in questo modo un circolo virtuoso.

Il nostro consorzio, in virtù dello stretto rapporto professionale che esiste tra i suoi membri dà le migliori garanzie che questo tipo di interazione possa avere luogo e che i vari aspetti del progetto siano portati avanti come le parti di un tutto, come è auspicabile che avvenga. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

In questo documento passiamo brevemente in rassegna alcuni aspetti dello stato dell'arte che sono rilevanti per le tematiche di ricerca che intendiamo sviluppare nell'ambito del progetto.

NEAREST NEIGHBOURS:

Trovare l'insieme dei documenti più rilevanti rispetto ad una data interrogazione (query) si può ricondurre spesso e volentieri al seguente problema geometrico: dato un insieme S di punti in uno spazio a d dimensioni, e dato un punto Q, determinare i punti di S più vicni a Q. Questo problema è noto come Nearest Neighbour (NN). In applicazoni tipiche la dimensione dello spazio è molto grande o addirittura enorme. Questo fatto, noto come "la maledizione della dimensionalità" rende in pratica inutilizzabili le sofisticate soluzioni algoritmiche sviluppate nell'ambito della geometria computazionale in quanto il tempo di esecuzione di quegli algoritmi tipicamente dipende esponenzialmente dalla dimensione dello spazio (si veda, ad esempio [1]).

Per quanto riguarda le applicazioni di information retrieval (IR) tra le soluzioni interessanti che sono state proposte troviamo le p-sfere [26]. Questo metodo ha però bisogno di conoscere un campione della distribuzione delle query. A grandi linee, l'idea è di sfruttare questa conoscenza per organizzare lo spazio opportunamente, in modo che le query possano essere indirizzate rapidamente verso la porzione dello spazio più rilevante.

In [6] gli autori propongono degli algoritmi di approssimazione basati sulla nozione di rank aggregation (un concetto che risale alla Rivoluzione Francese quando Condorcet inziò lo studio dei sistemi elettorali). Il corpus e la query vengono proiettati su un vettore random ed il documento la cui proiezione è più vicina a quella della query ottiene un "voto". Risultati teorici in [14] mostrano che usando un numero piccolo di vettori random il documento realmente più vicino alla query verrà "eletto" con alta probabilità. Successivi risultati sperimentali in [6] mostrano come lo scehma funzioni bene per alcune applicazioni di interesse.
Questi esperimenti però riguardano vettori densi e con un numero relativamente basso di dimensioni (qualche dozzina). Rimane quindi da verificare se lo schema possa funzionare bene nel caso del text retrieval e lo stesso discorso vale per [26].

In [7] gli autori usano tecniche di hashing. L'analisi teorica mostra che il metodo individua il NN con alta probabilità ma l'analisi sperimentale si limita a considerare scenari a bassa dimensione. I lavori [10, 11, 12] studiano il problema per la cosine-similarity invece che per la distanza euclidea.

Altri approcci sono basati su apposite strutture dati come gli R-tree [18] e le sue numerose varianti (si veda ad esempio la rassegna [24]). Una variante progettata specificatamente per il problema del NN, gli SR-tree, è discussa in [23] ma lo studio sperimentale contenuto in [26] mostra come le p-sfere, se non altro in alcuni ambiti di interesse, abbia prestazioni migliori.

SAMPLING DEL WEB:

Riferimenti bibliografici: [Ba96, AP03, BY05, BYSJ02, CMRZ04, DL04, HH00]

Speigare la struttura del Web è un compito utile ma, per le via delle sue dimensioni, all'apparenza proibitivo (stime correnti parlano di quasi 12 miliardi di pagine). Pertanto si è ricorsi a tecniche di campionamento per cercare di determinare le caratteristiche topologiche del Web.

Tali tecniche sono essenzialmente di due tipi: passeggiate aleatorie e il cosidetto campionamento verticale, che comporta di determinare in partenza le pagine che si vogliono raccogliere con un crawl. Gli studi esistenti analizzano le varie strategie proposte (larger-sites first, breadth-first, OPIC, partial-pagerank) con lo scopo di determinarne il comportamento rispetto alla capacità di raccogliere il prima possibile le pagine più significative.


SPAM DETECTION:

Riferimenti bibliografici:[BP98, GM05, FM04, ZG04, BC05, DS05, GM04]

Il cosidetto link spamming (LS) è oggigiorno molto diffuso e la sua presenza ha conseguenze negative sulla qualità delle risposte che vengono date dai motori di ricerca. La sua individuazione è quindi un problema di importanza crescente.

La ricerca pregressa ha mostrato come la presenza del LS è spesso collegata con anomalie nella distribuzione di alcune proprietà del grafo del Web (ad es. dell'in e out degree) o alla presenza di sottografi densi. Altre ricerche mostrano come il LS sia sensibile a cambiamenti nel damping factor nel calcolo del PageRank. Il modo migliore di combinare questi segnali rimane oggetto di ricerca. Uno degli approcci proposti individua alcune pagine con alto rango (rank) ed esplora successivamente le pagine ad essa vicina in modo da verificare che il rango sia genuino e non dovuto ad "anomalie" nella struttura del grafo.
Un approccio complementare è quello invece di partire da pagine considerate buone e di estendere man mano la porzione di grafo esente da LS. Entrambi i metodi però richiedono l'intervento umano per l'individuazione dell'insieme iniziale di pagine. Un altro approccio ancora considera la distribuzione di alcune grandezze caratteristiche come la grandezza della pagina e la distribuzione di parole chiave, confrontandola con un campione di pagine etichettate manualmente.


INTEGRAZIONE dei LINK con il CONTENUTO, i WEB LOGS e l'ANALISI TEMPORALE:

La link analysis (LA) fornisce un potente strumento per classificare e operare il ranking dei documenti. Ciò non di meno, per avere risultati di buona qualità essa deve essere integrata con altre fonti di informazione come l'informazione temporale, di contenuto (testo, multimedia) e statistihe di utilizzo (web usage).

Il ruolo del "tempo" sta diventando sempre più cruciale per poter sviluppare algoritmi di ricerca ch esiano in grado di fornire all'utente informazioni aggiornate. Negli ultimi dieci anni il Web ha esibito un imponente tasso di crescita e a causa della grande mole di dati in esso contenuti i motori di ricerca hanno dovuto far fronte all'oneroso compito di mantenere aggiornate le strutture di indicizzazione. Gran parte della letteratura sull'argomento si è concentrata su porzioni del Web raccolte nell'arco di pochi mesi [BKM00, DLSa, DLSb] mentre ben poca ricerca è stata sinora dedicata all'analisi della sua evoluzione temporale.
Per cattirare la relazione tra tempo, autorevolezza e popolarità delle pagine alcuni studi recenti hanno iniziato a far uso dell'informazione temporale [ACHLS04, KHS03, KNRT03].

I file dei log dei motori di ricerca contengono informazioni relative alle query sottoposte dagli utenti e includono sia le query che le pagine successivamente prescelte dall'utente. Questi dati possoino fornire utili informazioni sugli interessi delle persone e fornire un collegamento tra interesse e contenuto [B05]. Il clustering di queste informazioni (traces) si propone di identificare gruppi di utenti in base al tipo di informazioni cercate [BHM04]. Un contesto organico è stato proposto per rappresentare le relazioni tra oggetti eterogenei quali pagine web, query, hyperlink, e click-through sequences [XFF05].


CRAWLING. Il progetto Ubi, nato da una collaborazione tra il DSI, l'Istituto di Matematica Computazionale del CNR di Pisa e l'Istituto Applicazioni Telematiche, sempre del CNR di Pisa, punta allo sviluppo di software altamente scalabile e distribuito per lo studio del web. Il primo risultato di questo progetto è UbiCrawler (precedentemente denominato Trovatore), un crawler web composto da entità autonome autocoordinantesi realizzato in Java in collaborazione con Paolo Boldi, Bruno Codenotti e Massimo Santini [7]. È possibile lanciare uno numero arbitrario di agenti UbiCrawler, incrementando corrispondentemente la quantità di informazioni assorbite dalla rete.
Tramite UbiCrawler sono stati raccolti dati per contratti di ricerca con privati, e per il Language Observatory Project, un consorzio di università asiatiche che ha come obiettivo la misurazione della crescita delle lingue asiatiche sul web.

ANALISI DEL GRAFO DEL WEB. Uno degli aspetti più interessanti dello studio del web è l'analisi delle caratteristiche del grafo del web, cioè del grafo che ha un nodo per pagina e un arco da x a y se x contiene un collegamento ipertestuale a y. L'analisi e la manipolazione di grafi di queste dimensioni (miliardi di archi) rende necessarie tecniche completamente nuove di rappresentazione dei dati. In collaborazione con Paolo Boldi è stato realizzato WebGraph (http://webgraph.dsi.unimi.it/), un framework per l'analisi e lo studio di porzioni del web di grandi dimensioni [8, 3]. WebGraph fornisce software libero e dataset di grandi dimensioni che possono essere utilizzati con infrastrutture minimali; molti dei dataset sono stati raccolti da UbiCrawler. Il livello di compressione realizzato dagli algoritmi di WebGraph è il migliore mai realizzato, e il software e i dataset sono correntemente utilizzati da diversi gruppi di ricerca in tutto il mondo.

Analisi. Il macchinario creato per fotografare e memorizzare il porzioni del web e descritto precedentemente è stato utilizzato per iniziare uno studio sistematico dei metodi di ranking utilizzati dai motori di ricerca, e in particolare di PageRank, un algoritmo di ranking statico (cioè non dipendente dall'interrogazione) basato esclusivamente sulla struttura di grafo del web. Utilizzando come misuratore di correlazione la tau di Kendall, abbiamo appurato che la ricerca in ampiezza, che raccoglie rapidamente pagine con PageRank elevato, crea delle istantanee parziali che travisano il ranking relativo delle pagine: vengono cioè raccolte rapidamente pagine importanti, ma il loro ordine relativo (calcolato durante la raccolta) è inesatto [101]. Sempre in questa direzione, siamo riusciti a dare formule chiuse per tutte le derivate di PageRank in funzione del fattore di attenuazione [102]. Lo studio ha portato alla formulazione di varianti interessanti di PageRank che meglio sopportano la diminuizione dell'attenuazione, come TruRank [6]. Le attività suddette hanno portato alla realizzazione di programmi sofisticati di analisi statistica e calcolo lineare, che sono distribuiti come software libero (http://law.dsi.unimi.it/).


Indicizzazione di grandi collezioni

Dopo la raccolta di un'istantanea del web, è spesso utile costruire un motore di ricerca che permetta di reperire ed esaminare il contenuto dell'istantanea stesso. A questo scopo è stato realizzato MG4J, un motore di indicizzazione per collezioni documentali di grandi dimensioni, realizzato in Java e distribuito come software libero (http://mg4j.dsi.unimi.it/). MG4J contiene nuovi algoritmi per il calcolo di operatori come la congiunzione ordinata, la prossimità, ecc., e per permettere l'avanzamento veloce all'interno di una lista di affissioni [4]. Il codice di trattamento del testo è basato su una nuova implementazione estremamente compatta ed efficiente delle stringhe mutabili [5]. <<<