RICERCA ITALIANA     

Algoritmi per Internet e Web di prossima generazione: Metodologie, Progetto ed Esperimenti

Università degli Studi di Roma "Tor Vergata"

Abstract

Questo progetto coinvolge cinque gruppi di ricerca italiani, con una consolidata esperienza a livello internazionale nel progetto di algoritmi e di strutture dati, in uno sforzo comune rivolto a:

(1) Sviluppare nuove tecniche e metodologie algoritmiche;

(2) Identificare e risolvere problemi algoritmici in applicazioni di rilievo;

(3) Contribuire al trasferimento veloce di tecnologie algoritmiche evolute all'interno di strumenti software, librerie e sistemi.

L'enfasi principale del progetto sarà su una combinazione di ricerca orientata alle applicazioni in due domini di fondamentale importanza (Internet e Web di prossima generazione) e di innovazione metodologica nell'ingegneria degli algoritmi, nella visualizzazione dell'informazione e nelle tecniche algoritmiche generali. Come conseguenza naturale del nostro approccio metodologico ed orientato alle applicazioni, il piano di ricerca è organizzato in tre Workpart (WP) tra loro strettamente correlate:

WP1 - Metodologie Evolute per Internet ed il Web. Intendiamo sviluppare metodologie algoritmiche fondamentali per le applicazioni emergenti in Internet e nel Web, ad un livello di generalità tale da renderle ampiamente applicabili. Inoltre, intendiamo sviluppare metodologie e testbed sperimentali per l'ingegneria degli algoritmi.

WP2 - Algoritmica per Internet: Progetto ed Esperimenti. In reti Internet di prossima generazione, la capacità di ottimizzare l'uso delle risorse di rete giocherà un ruolo cruciale al fine di ridurre i costi e di migliorarne l'efficienza e l'affidabilità. Intendiamo progettare e realizzare nuove tecniche algoritmiche capaci di assicurare una maggiore efficienza nella comunicazione e nell'uso di risorse nelle reti di prossima generazione.

WP3 - Algoritmica per il Web: Progetto ed Esperimenti. La sempre crescente quantità di informazioni disponibili sul Web ha posto nuove sfide allo sviluppo di algoritmi efficienti per numerosi problemi relativi al data mining, al recupero di informazioni e alla visualizzazione. In questo progetto, intendiamo studiare la struttura ipertestuale del Web, sviluppare e validare modelli per il grafo del Web, progettare tecniche algoritmiche in grado di operare ricerche ed aggiornamenti su grandi quantità di dati Web residenti in sistemi complessi di memorie, e realizzare nuovi sistemi per la visualizzazione e la navigazione di comunità Web.

Il consorzio è composto da circa 50 ricercatori, per un totale di 456 mesi-uomo in un periodo di due anni. Di questi, 384 mesi provengono da personale strutturato, postdoc, studenti di dottorato ed altro personale di ricerca universitario, i cui costi non sono finanziati da questo progetto, e 72 mesi da personale di ricerca sostenuto dal progetto. Il costo totale del progetto è di Euro 276.000, di cui Euro 193.200 sono richiesti al MIUR ed Euro 82.400 sono finanziati dalle unità di ricerca. <<<

Coordinatore Scientifico del Programma di Ricerca

Giuseppe Francesco ITALIANO Università degli Studi di ROMA "Tor Vergata"

Obiettivo del Programma di Ricerca

I metodi tradizionali di progetto degli algoritmi appaiono talvolta inadeguati a rispondere alle sfide poste dalle applicazioni future. Recuperare informazioni dal Web implica la gestione di operazioni sofisticate di ricerca su enormi quantità di dati, per cui diventa sempre più importante sviluppare nuove tecniche algoritmiche per le (complesse) architetture di calcolo utilizzate a tale scopo. L'Internet di prossima generazione pone anche sfide di grande portata: le modalità della comunicazione nelle reti stanno cambiando drasticamente, e le reti di domani, eterogenee e di grandi dimensioni, necessitano di strategie di controllo più efficienti di quanto non sia possibile fare oggi.

Questo progetto è dedicato allo studio di nuove tecniche e metodologie algoritmiche, all'identificazione ed alla soluzione di problemi algoritmici cruciali in applicazioni importanti, ed all'accelerazione del trasferimento di tecnologie algoritmiche evolute in sistemi reali. In generale, i principali obiettivi del progetto sono:

(1) Contribuire alla scienza ed all'ingegneria degli algoritmi e delle strutture dati che, stimolate dai domini applicativi sopra descritti, saranno arricchite con nuove metodologie e tecniche.

(2) Progettare ed analizzare nuovi e più efficienti algoritmi per affrontare problemi specifici relativi ad Internet e al Web, con l'obiettivo di avere un impatto su applicazioni cruciali in queste aree.

(3) Valutare l'efficacia delle soluzioni proposte non soltanto attraverso strumenti analitici, ma anche attraverso lo sviluppo di prototipi e la loro sperimentazione su dati di test reali.

Al fine di perseguire questi obiettivi, useremo un approccio combinato di ricerca orientata alle applicazioni in due importanti domini applicativi (Internet e Web di prossima generazione) e di innovazione metodologica nell'ingegneria degli algoritmi, nella visualizzazione dell'informazione e nelle tecniche algoritmiche generali. Come conseguenza naturale del nostro approccio contemporaneamente metodologico ed orientato alle applicazioni, ci concentreremo su tre specifici ordini di problemi:

1. Metodologie Evolute per Internet ed il Web
Internet ed il Web suggeriscono lo studio di nuove soluzioni algoritmiche per un vasto insieme di problemi, alcuni dei quali saranno considerati in questo progetto. In alcuni casi, le nuove sfide al progetto di algoritmi efficienti possono essere ancora affrontate all'interno di modelli di calcolo e paradigmi di progettazione consolidati. In altri casi, nuovi modelli o paradigmi sono auspicabili, se non necessari. Lo sviluppo del contesto di riferimento più appropriato è quindi un prerequisito necessario per il progetto di nuove tecniche algoritmiche in questo ambito. In questa workpart, identificheremo e svilupperemo metodologie algoritmiche chiave che emergono dalle applicazioni Internet e Web, che sono di natura generale e quindi ampiamente applicabili a vari contesti. Inoltre, produrremo metodologie e dati di test per la sperimentazione algoritmica, ed in particolare per algoritmi che utilizzino la struttura gerarchica della memoria nelle moderne piattaforme di calcolo.

2. Algoritmica per Internet: Progetto ed Esperimenti
L'Internet di prossima generazione presenterà nuove sfide algoritmiche al fine di rendere le reti in grado di:
- offrire molteplici tipologie di servizio con differenti qualità di servizio in termini di ampiezza di banda, ritardo, jitter ed affidabilità;
- resistere ai guasti, e quindi ripristinare rapidamente le normali funzionalità dopo malfunzionamenti sui link, situazioni di congestione ed instabilità dell'instradamento.
In questo contesto, assumerà un ruolo fondamentale la capacità di ottimizzare l'uso delle risorse di rete al fine di ridurre i costi e di migliorarne l'efficienza e l'affidabilità. Per questo motivo, intendiamo progettare e realizzare techniche algoritmiche generali in grado di realizzare un uso efficiente delle risorse.

3. Algoritmica per il Web: Progetto ed Esperimenti
La sempre crescente quantità di informazioni disponibili sul Web ha posto nuove sfide allo sviluppo di algoritmi efficienti per il recupero di informazioni e per la visualizzazione di grandi quantità di dati. Un'estesa attività di ricerca si è anche concentrata sullo studio delle proprietà del Web ed in particolare del grafo formato dai documenti Web e dai collegamenti ipertestuali (link) tra questi documenti. Lo sviluppo di modelli per tale struttura rende possibile l'analisi delle sue proprietà e della loro evoluzione nel tempo. Questo studio è anche di grande rilevanza per applicazioni cruciali Web, come i motori di ricerca, e per l'individuazione delle comunità virtuali presenti nel Web, un importante passo per la comprensione di come l'informazione è ivi distribuita. Studieremo, proporremo e verificheremo modelli per il grafo del Web, e progetteremo nuovi sistemi per la visualizzazione e la navigazione delle comunità Web. Le applicazioni Web sono anche una ricca fonte di nuovi problemi algoritmici. Infatti tali applicazioni devono essere in grado di gestire grandi quantità di dati che sono tipicamente memorizzate in piattaforme di calcolo con sofisticati sistemi di memoria. Intendiamo progettare tecniche algoritmiche adeguate a gestire possibili malfunzionamenti di tali sistemi, capaci di operare ricerche e aggiornamenti su grandi quantità di dati, come ad esempio grandi collezioni di documenti HTML e XML, attraverso l'utilizzo diretto della gerarchia di memoria delle piattaforme di calcolo.

Un approccio completamente integrato alla modellazione, al progetto, all'analisi, all'implementazione ed all'ingegnerizzazione, è un elemento cruciale per il successo di un progetto ambizioso come questo. La modellazione implica un compromesso tra la descrizione fedele di tutte le caratteristiche dei sistemi di elaborazione e della struttura delle reti e l'esigenza di rendere trattabile il compito dell'analisi e del progetto di algoritmi. Ciò nonostante, il progetto di algoritmi, sebbene ispirato da un particolare modello, non deve affatto trascurare i dettagli implementativi: le prestazioni misurate nell'implementazione dovrebbero costituire un benchmark anche per le attività di progetto e di modellazione. Il livello crescente di sofisticazione richiesto dalle fasi di modellazione e di analisi possono inoltre rendere i risultati scientifici più difficili da accedere e da implementare per i non specialisti; la ricerca nel campo degli algoritmi può quindi avere un impatto molto limitato se il suo trasferimento iniziale in librerie, strumenti software ed altri sistemi non è realizzato come parte integrante della stessa attività di ricerca.

Questo approccio integrato è garantito dalla presenza nel consorzio di ricercatori con esperienza consolidata sia nel progetto di algoritmi che nella loro implementazione all'interno dello sviluppo di strumenti software versatili, abilità spesso presenti nella stessa persona. La capacità del consorzio di raggiungere gli obiettivi del progetto è assicurata anche dall'accesso ad adeguate piattaforme hardware e software (a puro titolo di esempio, l'unità di ricerca 2 possiede una macchina parallela con un sofisticato sistema di memoria; l'unità di ricerca 4 partecipa ad una rete di eccellenza sul progetto dell'Internet di prossima generazione, e può quindi accedere a dati di test sulla rete e a simulatori di rete; altre unità di ricerca hanno accesso a vaste raccolte di dati relative ad Internet e al Web). Questo rende possibile la realizzazione delle differenti fasi della ricerca, dal progetto di algoritmi alla loro simulazione, e al loro trasferimento in ambienti di rete reali. Crediamo che questi elementi offrano una forte evidenza della possibilità che molti degli obiettivi di questo progetto, se non tutti, possano essere raggiunti con successo dal consorzio di ricerca. <<<

Risultati parziali attesi

Di seguito sono elencati i principali risultati attesi nella Fase 1, raggruppati in base ai vari task del progetto.

Task 1.1 Modelli e Paradigmi Algoritmici
- Prima versione di una libreria software open-source per gestire grafi di enormi dimensioni
- Modello di Calcolo Architetturale Parametrizzato (APMC)
- Progetto di nuovi algoritmi tolleranti a errori di memoria per problemi combinatori fondamentali

Task 1.2 Metodologie di Visualizzazione
- Caratterizzazione di classi di grafi con cluster per i quali il test di c-planarità può essere eseguito in tempo polinomiale
- Nuovi risultati sulle proprietà di alberi k-densi e di k-alberi
- Algoritmi polinomiali per il calcolo di disegni radiali di grafi con livello dei vertici pre-assegnato

Task 2.1 Algoritmi per l'Instradamento su Internet
- Nuovi algoritmi per il calcolo dinamico di cammini minimi a sorgente singola e di t-spanner
- Studi teorici e sperimentali sugli equilibri di Nash e sul prezzo dell'anarchia con riferimento alle politiche di gestione della congestione
- Tecniche efficienti di IP lookup e classificazione di pacchetti

Task 2.2 Esplorazione e Visualizzazione di Internet
- Modelli e algoritmi di disegno per la visualizzazione di reti a differenti livelli di astrazione
- Studio di algoritmi e progetto di una piattaforma per l'acquisizione della topologia di reti miste IPv4-IPv6
- Modellazione degli aspetti dinamici dell'instradamento in Internet al livello dei Sistemi Autonomi (AS) e studi sulle cause di instabilità e sulla loro inferenza dagli archivi di conversazioni BGP

Task 3.1. Algoritmi per la Ricerca sul Web
- Framework di valutazione delle prestazioni di algoritmi per l'estrazione di pattern ricorrenti/critici
- Analisi teorica e sperimentale sulla stabilità di algoritmi di ranking basati sull'analisi dei link
- Tecniche efficienti per l'uso di pattern al fine di individuare similarità nei testi

Task 3.2 Esplorazione e Visualizzazione del Web
- Prototipo di un sistema per visualizzare ed esplorare comunità Web
- Identificazione delle componenti del grafo del WebDi seguito sono elencati i principali risultati attesi della Fase 2, raggruppati in base ai vari task.

Task 1.1 Paradigmi e Modelli Algoritmici
- Secondo rilascio della libreria software open-source per grafi di grandi dimensioni, e studio empirico delle proprietà di campioni dal Web.
- Estensioni del modello APMC e valutazione sperimentale (su tre diverse piattaforme hardware) degli algoritmi adattivi sviluppati come casi di studio.
- Progetto di algoritmi tolleranti a errori in memoria esterna.

Task 1.2 Metodologie di Visualizzazione
- Algoritmi efficienti per produrre disegni c-planari per le classi di grafi per le quali il problema è trattabile.
- Algoritmi efficaci ed efficienti per disegnare alberi k-densi e k-alberi in 2D e 3D.
- Algoritmi polinomiali per calcolare disegni radiali di grafi planari usando il numero minimo di livelli.

Task 2.1 Algoritmi per l'Instradamento su Internet
- Ingegnerizzazione degli algoritmi concepiti nella Fase 1 per l'instradamento su Internet.
- Meccanismi di ripartizione del costo per il progetto di reti "single source Rent-or-Buy" basati sulla randomizzazione e condivisione del costo atteso dell'infrastruttura di rete.
- Benchmark sperimentale per schemi di IP lookup e classificazione di pacchetti.

Task 2.2 Esplorazione e Visualizzazione di Internet
- Esperimenti di esplorazione di reti in un ambiente misto IPv4-IPv6 tramite una nuova libreria software sviluppata a tale scopo, e rapporti sulla diffusione del protocollo IPv6.
- Sistema per l'esplorazione visuale della rete che mostra informazioni a livello di router e di AS.
- Sistema per il monitoraggio della rete degli AS per ricercare cause di instabilità.

Task 3.1 Algoritmi per la Ricerca sul Web
- Algoritmi per la ricerca di pattern ricorrenti/critici in grandi quantità di dati in memoria esterna.
- Algoritmi per analisi dei link su specifici modelli per il grafo del Web.
- Tecniche di potenziamento per la compressione di dati e strutture di dati efficienti per l'indicizzazione di testi.

Task 3.2 Esplorazione e Visualizzazione del Web
- Servizio Web per l'eplorazione e la visualizzazione di comunità Web.
- Framework per lo studio dell'evoluzione temporale del grafo del Web. <<<

Durata

24 mesi

Base di partenza scientifica nazionale o internazionale

Le tecnologie algoritmiche rivestono un ruolo vitale nella crescita spettacolare di Internet e del Web: questo è testimoniato non solo dalla ricchezza della letteratura scientifica in questo ambito, ma anche da un numero di aziende, come Akamai, Google e Yahoo, che hanno basato la maggior parte del loro successo su nuove idee algoritmiche per Internet. Il presente progetto di ricerca si colloca nell'area degli algoritmi e delle strutture dati per le applicazioni in Internet e nel Web. In particolare, il progetto è focalizzato su metodologie algoritmiche evolute e sul progetto e la sperimentazione di tecnologie algoritmiche per Internet e Web. Questo paragrafo sullo stato dell'arte è incentrato principalmente su tali argomenti, e presenta una breve rassegna del lavoro finora svolto quale fondamento scientifico per la nostra agenda di ricerca.

Metodologie Evolute per Internet e per il Web

Molte delle applicazioni in Internet e nel Web, come ad esempio la ricerca sul Web, generano insiemi di dati sempre più vasti, dell'ordine dei PetaByte. Di conseguenza, gli algoritmi per problemi su dati di enormi quantità devono tener conto della capacità limitata della memoria interna e della relativa lentezza dell'accesso alla memoria esterna rispetto a quella interna (a titolo di esempio, citiamo un rallentamento di circa sei ordini di grandezza nel caso di un disco rigido). Inoltre le moderne piattaforme di calcolo ospitano un sistema piuttosto sofisticato di gerarchie di memoria che premia la località dei dati in quanto questi vengono trasferiti a blocchi. Diversi modelli computazionali proposti in letteratura hanno introdotto alcuni parametri architetturali: gerarchie di memoria interna ed esterna [AC+94, VS94] e proprietà di ampiezza di banda e latenza nella rete di interconnessione [V90, BF+01].

In un tale contesto, le gerarchie di memoria hanno un impatto diretto sull'efficienza del software che opera su grandi quantità di dati: se i dati non rientrano nella capacità della memoria interna, la velocità degli algoritmi utilizzati può aumentare notevolmente se gli algoritmi sono pienamente consapevoli dei parametri della gerarchia di memoria delle piattaforme adottate (e.g., dimensione dei blocchi, delle linee della cache, ecc...). Tuttavia, al variare delle piattaforme, e delle loro gerarchie di memoria, le prestazioni di tali algoritmi possono degradare e/o risultare più o meno efficienti. Ne consegue che, se desideriamo ottenere del software portabile tra architetture diverse, è necessario del lavoro di ulteriore reingegnerizzazione degli algoritmi nella nuova piattaforma. Questo aspetto ne limita fortemente l'impatto globale.

Un possibile approccio per risolvere tale problema è l'uso di algoritmi cache-oblivious [F+99]. Sebbene siano consapevoli dell'esistenza della gerarchia di memoria, tali algoritmi non hanno accesso ai parametri della gerarchia. Gli algoritmi di questo tipo possono rivelarsi ottimi per una vasta serie di parametri [F+99,BD+00,AB+02,FG03]. Tuttavia, non sempre è possibile ottenere prestazioni vicine all'ottimo su più piattaforme utilizzando un unico codice sorgente (non adattivo) [BP01,BF03]. Come alternativa agli algoritmi cache-oblivious, l'idea di progettare del software che si adatti in maniera efficiente alla piattaforma sottostante è diventata popolare negli anni recenti in seguito al successo di pacchetti software come FFTW [FJ98] per la trasformata di Fourier e ATLAS [WPD01] per l'algebra lineare. A differenza della loro controparte cache-oblivious, gli algoritmi adattivi producono del codice diversamente ingegnerizzato su piattaforme differenti, ottimizzando così l'uso delle risorse computazionali. Per rendere tutto ciò trasparente all'utente, gli algoritmi adattivi hanno dei parametri interni caratterizzanti quelli della piattaforma ospite per meglio sfruttarne il potenziale computazionale. Tale software è basato su intuizioni e conoscenze specifiche per il problema computazionale affrontato. Osserviamo che allo stato attuale non c'è alcuna metodologia generale che riesca a rendere adattivo un algoritmo, ma sono disponibili soltanto risultati preliminari [Y+03].

Le memorie dei moderni sistemi sono sempre più economiche e di grande capacità ma anche soggette a errori. Gli algoritmi classici spesso falliscono nel produrre sempre una risposta corretta quando ci sono errori di memoria: per esempio, progettare algoritmi di ordinamento e di ricerca tolleranti agli errori risulta un problema pressante in motori di ricerca quali Google [F02]. Il problema del calcolo in presenza di errori è stato analizzato precedentemente in una varietà di contesti [AD91,CLGKP94,FI04]. La ricerca finora svolta si è tuttavia incentrata o sul recupero dagli errori in un contesto statico, attraverso la replicazione dei dati e l'uso di codici correttori di errori [CLGKP94], oppure ha considerato algoritmi in grado di tollerare malfunzionamenti temporanei di parti del processore, per esempio i comparatori [AD91]. Questi approcci non sono adatti per errori di memoria altamente dinamici e distruttivi. Recentemente, il problema dell'ordinamento in presenza di tali errori è stato studiato in [FI04].

Gli strumenti di visualizzazione permettono di affrontare la complessità di Internet e del Web. La difficoltà di visualizzare questo tipo di reti deriva principalmente dalla natura eterogenea della loro vasta topologia, che consiste di molti sottografi con differenti densità e fattori di connessione. Applicare modelli e tecniche standard per il disegno di grafi [DETT99,KW01] alla visualizzazione di tali reti è un compito arduo, ed è necessario esplorare nuovi approcci metodologici per migliorare l'efficacia dei modelli, degli algoritmi e dei sistemi sviluppati finora [DK01,JM03]. Alcuni paradigmi di disegno stanno ricevendo una sempre maggiore attenzione. In particolare:
- Le tecniche di visualizzazione mediante cluster permettono di trattare un enorme numero di nodi di Internet; solo pochi risultati sono attualmente conosciuti in tal senso [D98,DDM01].
- Le proprietà degli alberi k-densi e dei k-alberi [B98,LP02] permettono di rappresentare le topologie con fattori di densità estremamente variabili. Gli algoritmi per calcolare disegni compatti di k-alberi sono noti [DM03,WD03], ma molto lavoro rimane ancora da fare rispetto ad altri criteri estetici.
- Il paradigma di disegno radiale sembra piuttosto naturale per visualizzare la struttura gerarchica di una rete, ma la ricerca in questa area è ancora a uno stadio preliminare [BBF03,DD03].

Algoritmica per Internet

La complessità delle operazioni di base che i router dovranno eseguire nelle reti Internet di prossima generazione aumenterà in modo significativo. Infatti la rete dovrà essere tollerante ai guasti e in grado di ripristinare velocemente le sue funzionalità dopo cadute di connessioni, congestioni e instabilità di varia natura. Dovrà inoltre essere così flessibile da garantire l'accesso a tecnologie eterogenee e fornire differenti livelli di qualità dei servizi in termini di ampiezza di banda, ritardi, sfasamenti e affidabilità. Sarà molto probabilmente una rete cosiddetta "all IP" senza coordinamento globale, in grado di affrontare la lenta transizione dall'attuale protocollo di rete, IPv4, al nuovo IPv6. È quindi cruciale sia arricchire i fondamenti algoritmici delle operazioni critiche nei router (essenzialmente aggiornamenti delle tabelle, instradamento dei pacchetti e controllo della congestione), sia progettare strumenti di visualizzazione per scoprire, esplorare e monitorare la rete.

La prossima generazione di metodi di instradamento dovrà essere in grado di effettuare aggiornamenti molto frequenti delle tabelle di routing in seguito a variazioni dinamiche del traffico. Molti schemi di instradamento per Internet come OSPF (Open Shortest Paths First) [ISO89,M99] instradano i pacchetti lungo i cammini minimi per evitare congestioni. Mentre algoritmi veloci per il calcolo dei cammini minimi sono ormai noti da vari decenni [D59], solo recentemente sono stati proposti metodi efficienti per aggiornare i cammini minimi in un grafo soggetto a cambiamenti dinamici [K99,DI01,DI03]. Molti degli algoritmi progettati finora si applicano a problemi su cammini minimi per tutte le coppie mentre esistono poche soluzioni per il caso di sorgenti singole, di grande interesse per l'instradamento su Internet. Inoltre, le strutture dinamiche devono essere mantenute in modo distribuito, come testimoniato da attività di ricerca in corso. Per esempio, l'approccio di [NPW03], in cui un opportuno arco di avvicendamento è precalcolato per ciascun arco che potrebbe fallire, garantisce di ottenere tabelle di instradamento tolleranti a un singolo guasto ma sembra avere una natura sequenziale invece che distribuita.

Nel progetto di protocolli di reti, molta attenzione è stata recentemente rivolta alla teoria dei giochi , specialmente per gli algoritmi di controllo della congestione. I concetti della teoria dei giochi sono candidati naturali per studiare il comportamento di agenti di rete e per progettare algoritmi atti a incoraggiare la cooperazione tra utenti "egoisti" in reti "anarchiche", come ad esempio è il caso di Internet. I candidati ideali per studiare tale comportamento si ritrovano nell'instradamento di Internet, nell'allocazione di banda di trasmissione, nei meccanismi che assicurano un'equa condivisione del costo dei servizi di rete e delle infrastrutture [JV01]. I lavori precedenti analizzano discipline di servizio per gli switch con distribuzioni del traffico che ricadono nel modello a fluidi [SH95, GK02], mostrando come il comportamento tradizionale (FIFO) e quello egoista non garantiscano efficienza ed equità, ma conducano a un collasso del sistema a causa della congestione.

Per quanto riguarda l'esplorazione e la visualizzazione della rete, esiste una ricca letteratura in proposito (e.g., [BC99, SMW02,CDDMP02]). Tuttavia il compito di esplorare la rete in un ambiente misto con protocolli IPv4-IPv6 è stato considerato raramente [CDP04] e non hai mai prodotto uno strumento di esplorazione visiva. Siccome la sostituzione del protocollo IPv4 è ritenuta un processo lento e complesso, sarà cruciale monitorare la fase di transizione. Inoltre, sebbene l'analisi del grafo dei sistemi autonomi (o SA, che sono organizzazioni indipendenti la cui cooperazione garantisce la consegna dei pacchetti IP tramite Internet) sia sufficientemente nota, l'informazione deducibile dalle relazioni commerciali tra SA [SARK02, DPP03] non è stata mai usata per l'analisi delle instabilità dell'instradamento interdominio. Inoltre, i risultati di tale analisi non risultano essere stati propriamente visualizzati, possibilmente integrandoli con informazioni a basso livello di astrazione.

Algoritmica per il Web

L'enorme quantità di dati disponibili nel Web richiede tecniche efficienti per la ricerca e l'aggiornamento di vasti insiemi di dati, come le raccolte di documenti in formato HTML e XML. Un vantaggio sostanziale può essere ottenuto sfruttando direttamente le gerarchie di memoria attraverso metodi algoritmici innovativi che facciano uso della compressione dei dati [FM00,GV00]. In diverse applicazioni di reperimento di informazioni sul Web (Web Informatin Retrieval o WebIR), è anche cruciale identificare pattern ripetuti, per cui si rende necessario individuare pattern simili piuttosto che identici: questo problema è arduo in quanto il numero di pattern simili può essere esponenziale. Nella loro forma generale, i pattern sono espressioni regolari, una delle forme preferite per esprimere pattern flessibili nelle collezioni di dati testuali come XML. A partire da [AIS93], molti algoritmi sono stati proposti per l'estrazione di pattern frequenti su insiemi di transazioni. Alcuni [OPPS02] raffinano la strategia dell'algoritmo A-priori [AS94] per la generazione dei pattern in ampiezza, introducendo nuove strutture dei dati e strategie per il calcolo delle frequenze. Altri [HPY00,LPWH02] adottano invece un approccio di generazione in profondità, combinando efficientemente le fasi di generazione dei candidati e di calcolo delle frequenze. Recentemente è stato arguito in [PZ03] che i trie compressi possano ottenere le migliori prestazioni in molti casi. Gli algoritmi più recenti in questa direzione sono discussi in [FIMI03]. Nell'estrazione di pattern sequenziali si cercano le sottosequenze frequenti per una data collezione di sequenze, di particolare utilità per i dati provenienti dal Web [HK01]. Una prima strategia ispirata dall'algoritmo A-priori è stata proposta in [AS95] e raffinata in [SA96]. Algoritmi più efficienti sono stati quindi presentati in [Z01,P+01].

Motivati dalla tecnologia per i motori di ricerca, una vasta attività di ricerca si è indirizzata verso la misurazione di alcuni parametri del grafo del Web [BMR+00, LLM+03]. Lo studio della struttura topologica di questo grafo ha rivelato una struttura "self-similar" del Web, con la presenza ubiqua di leggi di potenza che sono tipiche di strutture invarianti rispetto ala scala. Una descrizione affascinante del Web mostra una struttura a "papillon" (bow tie) con una componente fortemente connessa che include circa il 25% delle pagine, e due regioni periferiche di taglia quasi eguale. Molti di questi studi si sono concentrati su ampi campionamenti del Web raccolti durante mesi di attività di navigazione, e poco si è fatto [KH03] per analizzare l'evoluzione temporale delle proprietà del grafo del Web.

Tale evoluzione è naturalmente correlata con il problema della stabilità degli algoritmi che effettuano l'analisi dei link (collegamenti), un ingrediente fondamentale nei moderni motori di ricerca. L'idea alla base di tali algoritmi di ordinamento per rilevanza [K98,BP98] è che una pagina autorevole è puntata da pagine "hub", dove un "hub" punta a sua volta a pagine autorevoli. Le tecniche impiegate si basano sui metodi spettrali in cui le pagine sono classificate mediante gli autovettori calcolati per la matrice di adiacenza del grafo del Web oppure per quella del grafo di cocitazione. Un importante aspetto è la natura dinamica dei link, per cui alcuni lavori recenti [NZJ01, BRRT03] hanno considerato il problema dell'analisi dei link dal punto di vista della stabilità in corrispondenza di piccole perturbazioni dei link tra pagine.

Una crescente attenzione è stata rivolta al progetto di algoritmi efficaci ed efficienti per la scoperta delle comunità Web [B03,FLG00,GKR98]. I disegni prodotti dai sistemi esistenti per la visualizzazione delle mappe e dei siti del Web [DK01,RCMC00] sono per lo più adatti a grafi che hanno una struttura ad albero o sono sparsi; per grafi densi e di taglia enorme, questi disegni possono avere un alto numero di incroci e curvature. In particolare, non sono stati sviluppati specifici sistemi e servizi efficaci per la visualizzazione delle complesse topologie delle comunità del Web: questo richiede l'ottimizzazione delle dimensione dei vertici e delle etichette, e devono essere considerati anche i vincoli derivanti dalla planarità e dal clustering [BDLN02,DDM01,DETT99]. Infine, le mappe del Web sono ampiamente usate per arricchire la percezione del contenuto dei siti Web [MB98,SH00]. Nonostante l'impressionante serie di tecniche sviluppate nell'ultimo decennio, è solitamente difficile per l'utente ottenere una rappresentazione personalizzata della mappa del Web relativamente ad alcuni argomenti di interesse. <<<