Post on 24-May-2015
description
Algoritmi SWS e sistemi P2PAlgoritmi SWS e sistemi P2P
Mazza Dario
Merlino Sebastiano
Messina Marco
Università degli studi di Catania
Ingegneria informatica
A.A. 2008/2009
Mazza, Merlino, Messina 2
Studio e analisi degli algoritmi di Studio e analisi degli algoritmi di affinità semantica tra concettiaffinità semantica tra concetti
In questa sezione verranno descritti e analizzati i seguenti algoritmi:● H-Match (An algorithm for dynamically matching ontologies);
● Edamok (An algorithm for dynamically matching ontologies);
● Chatty Web (An algorithm for dynamically matching ontologies);
● Glue (An algorithm for dynamically matching ontologies);
● Kaon (An algorithm for dynamically matching ontologies);
● VSM (Semantic Search in Peer-to-Peer Systems);● ESS (E cient Semantic web Service discovery in centralized and P2P ffi
environments);● pService (Peer-to-Peer based Web Services Discovery and Matching):
Mazza, Merlino, Messina 3
H-MatchH-MatchPrincipi di base
L'obiettivo generale delle tecniche di compatibilità
ontologica è quello di trovare tutti i concetti che hanno
un'affinità semantica con un concetto di riferimento.
L'algoritmo H-match considera sia le caratteristiche
linguistiche dei concetti, nonché le relazioni semantiche tra
quelli presenti in una stessa ontologia. La valutazione delle
caratteristiche linguistiche è basata su un “thesaurus”, dove il
significato di ciascun termine è rappresentato da un insieme
di relazioni terminologiche.
Mazza, Merlino, Messina 4
H-MatchH-MatchPeculiarità
L'affinità semantica tra due concetti ontologici è valutata, in Helios(o H-Match), dalla stima sia delle relazioni terminologiche attraverso i tesauri sia delle relazioni semantiche valutando il contesto nel quale agiscono i due concetti.H-match ha 3 differenti tecniche di compatibilità:
● compatibilità superficiale: viene preso in considerazione solo l'informazione linguistica proveniente dal thesaurus. Questo tipo di “matching” garantisce alte performance, ma bassa precisione dei risultati;
● compatibilità media: vengono presi in considerazione sia il nome del concetto che le sue proprietà. Si ottiene una precisione più accurata rispetto alla tecnica precedente;
● compatibilità profonda: prende in esame i nomi dei concetti nonché tutto il contesto nel quale essi sono inquadrati.
Mazza, Merlino, Messina 5
H-MatchH-MatchInput/Output
L'algoritmo H-match richiede in input i due
concetti di cui si vuole calcolare l'affinità, la
tecnica di compatibilità da utilizzare, il valore del
peso dell'affinità linguistica (WLA). I valori di
default sono compatibilità profonda e WLA =
0,5. L'output dell'algoritmo è il grado dell'affinità
semantica tra i due concetti.
Mazza, Merlino, Messina 6
H-MatchH-MatchVantaggi
I vantaggi di questo algoritmo sono:● correlazione tra affinità semantica e affinità
linguistica;● possibilità di scegliere diverse tecniche di
matching (algoritmo dinamico);● ottima precisione utilizzando la compatibilità
profonda.
Mazza, Merlino, Messina 7
H-MatchH-MatchSvantaggi
Gli svantaggi dell'H-match sono:
● la compatibilità profonda richiede un'elaborazione troppo onerosa;
● ha una complessità O(N2) dove N è il numero di elementi appartenenti al contesto del concetto considerato;
● l'eterogeneità dei vocabolari in cui sono presenti i concetti da relazionare può causare perdita d'informazione;
● dubbia scalabilità;
● mai testato in un caso reale.
Mazza, Merlino, Messina 8
EdamokEdamokDescrizione generale
E' un progetto di ricerca che implementa il KEx (scambio di
conoscenza) nei sistemi P2P, con il quale si riesce a realizzare la
condivisione della conoscenza tra comunità di interesse di tipo paritarie.
Il sistema, per ottenere una mappatura di tipo semantico tra i concetti
presenti nei diversi peer, utilizza un algoritmo chiamato CTX-match.
Tale algoritmo è basato su una fase di esplicitazione semantica durante
la quale i concetti sono associati con i loro significati nel rispetto del
loro contesto. Alla fase di esplicitazione semantica segue una fase di
comparazione semantica dove i concetti vengono tradotti in assiomi
logici e comparati tra loro. L'algoritmo prevede un approccio logico di
tipo descrittivo.
Mazza, Merlino, Messina 9
Chatty WebChatty WebDescrizione generale
Questo approccio è applicabile a tutti i sistemi decentralizzati
ed offre l'opportunità di studiare l'interoperabilità semantica
come fenomeno globale. Ogni peer offre i propri dati
organizzati secondo uno schema ben preciso (relazionale,
XML, RDF). Il sistema prevede una mappatura corretta tra i
vari schemi adottati dai peer. Chatty web adotta un algoritmo
che riesce ad identificare un insieme sufficientemente grande
di peer per ottenere un'adeguata risposta ad una data query.
Mazza, Merlino, Messina 10
GlueGlueDescrizione generale
E' un sistema che sfrutta la tecnica di apprendimento delle
macchine per trovare una mappatura semantica tra i concetti
ubicati in ontologie diverse e autonome. Glue segue un
approccio di tipo probabilistico: il grado di compatibilità tra
due concetti A e B è calcolato come la probabilità che una
data istanza appartenga ad entrambi i concetti. Sono
applicate 2 tecniche di apprendimento di base. Infine una
procedura di mitigazione dell'etichettatura è utilizzata per
migliorare l'accuratezza della predizione dell'affinità.
Mazza, Merlino, Messina 11
KaonKaonDescrizione generale
E' un sistema di tipo prototipale descritto
solo per via matematica. Il sistema Kaon
pone l'accento sulla definizione ontologica e
sulle proprietà formali dei concetti al fine di
ottenere correttezza e completezza delle
espressioni.
Mazza, Merlino, Messina 12
VSMVSMDescrizione generale
Ogni documento VSM è rappresentato da un vettore di termini. I termini sono parole che si trovano all'interno del documento stesso. Ad ogni termine del vettore viene assegnato un peso. Termini con un peso superiore sono generalmente ritenuti centrali in un documento. Per valutare se un documento è rilevante per una query, il sistema misura la pertinenza tra il vettore della query e il vettore del documento. Un certo numero di sistemi di ponderazione per i termini sono stati proposti per VSM, tra i quali tf-IDF che è un sistema in cui il peso di un termine è alto , se il termine è frequente nel documento considerato, ma infrequente in altri documenti. Lo svantaggio principale della TF-IDF è che richiede informazioni a livello mondiale per il calcolo del peso di un termine.
Mazza, Merlino, Messina 13
ESSESSGeneralità
L'obiettivo del progetto ESS è quello di migliorare la qualità della
ricerca, minimizzando i relativi costi. La filosofia progettuale di
ESS è migliorare l'efficienza e l'efficacia della ricerca, pur
mantenendo semplice, robusta, e completamente di natura
decentralizzata Gnutella. In ESS, ogni nodo è dotato di un vettore
che è una sintesi compatta del suo contenuto. E ogni nodo può
avere due tipi di collegamenti, ossia collegamenti casuali e
collegamenti semantici. I collegamenti casuali collegano nodi
irrilevanti, mentre i collegamenti semantici organizzano i nodi in
gruppi semantici.
Mazza, Merlino, Messina 14
ESSESSDescrizione dell'algoritmo
L'algoritmo di adattamento della topologia è eseguito la prima volta per collegare un nodo al resto della rete tramite collegamenti casuali, o collegamenti semantici o entrambi. L'obiettivo dell'adattamento della topologia è quello di garantire che: (1) nodi pertinenti siano organizzati in gruppi semantici attraverso collegamenti semantici, e (2) la rete possa sostenere un alto numero di nodi. Data una query, il protocollo di ricerca dell'algoritmo ESS individua rapidamente un importante gruppo semantico per la ricerca, basandosi su un meccanismo di tipo selettivo dei nodi. Una volta localizzato il gruppo semantico, ESS inonda il gruppo con la query semantica per recuperare i documenti pertinenti. Le inondazioni semantiche all'interno di un gruppo, che ha nodi semanticamente associati, tendono ad essere rilevanti per la ricerca stessa della query.
Mazza, Merlino, Messina 15
pServicepServiceDescrizione dell'algoritmo
La rete p2p su cui si basa l'algoritmo può essere strutturata o non strutturata. L'overlay network generalmente usata prende il nome di skip graph consistente in un albero bilanciato con accesso in posizioni random. L'utilizzo di skip graph permette una più facile maniera di indirizzare le query ed inoltre di bilanciare l'albero della rete. Le informazioni inerenti i servizi più importanti sono inserite sotto forma di hash key all'interno della rete Chord e si utilizza skip graph per distribuire gli altri servizi. Quando un service provider aggiorna la sua descrizione possono avvenire due processi differenti di aggiornamento a secondo che essa si trovi originariamente all'interno dell'albero della rete chord o del sistema skip graph. Per ricercare dei dati, si effettuerà una ricerca fra i nodi della rete Chord. Per ottenere risultati più profondi si ricercheranno le informazioni conservate nella rete skip graph.
Mazza, Merlino, Messina 16
pServicepServiceRisultati di una richiesta
Tramite un'equazione matematica si può determinare se due servizi descritti mediante WSDL-S sono uguali; i risultati possono essere di 4 tipi:
● Il risultato è esattamente uguale alla richiesta;
● il risultato contiene i servizi richiesti ed inoltre esegue dell'altro; il risultato sussume la richiesta;
● il risultato è contenuto nella richiesta e la soddisfa solo in parte; la richiesta sussume il risultato;
● il risultato e la richiesta sono differenti.
Mazza, Merlino, Messina 17
pServicepServiceComponenti principali
I risultati di ogni query sono memorizzati nel System Monitor dal quale possono essere facilmente invocati. Il sistema pService include tre componenti principali: ● service Inquiry; ● service Matching;● service Invocation.
Mazza, Merlino, Messina 18
pServicepServiceService Inquiry
Il sistema di Service Inquiry è costruito sulla rete ibrida p2p ed è strutturato mediante l'utilizzo di tre livelli:
● Chord_ON (Top level) che mantiene relazione con i vicini nell'overlay network Chord; permette operazioni di osservazione stato, inserimento e cancellazione sui peer dell'overlay Chord;
● SkipGraph_ON (Middle level) che mantiene relazione con i vicini nell'overlay network SkipGraph; permette operazioni di osservazione stato, ricerca, inserimento, cancellazione sui peer dell'overlay SkipGraph;
● TreeNode_ON.
Mazza, Merlino, Messina 19
pServicepServiceService Matching
Il sistema Service Matching introduce due operazioni:
● matchWithOnt(doc1, doc2) in grado di trovare attinenze e similitudini fra i documenti passati;
● matchWithIOPE(doc1, doc2) in grado di trovare le relazioni che legano i due documenti.
Mazza, Merlino, Messina 20
pServicepServiceService Invocation
Il sistema Service Invocation fornisce due primitive:
● fetchService() che restituisce il servizio con la migliore QoS fra quelli memorizzati nella memoria dei ServiceResults;
● invokeService() che invoca direttamente il servizio con la migliore QoS.
Mazza, Merlino, Messina 21
Studio e analisi degli approcci P2P Studio e analisi degli approcci P2P semantici al service discoverysemantici al service discovery
Dopo un'introduzione inerente la descrizione generale delle caratteristiche delle reti P2P, si procederà all'analisi dei seguenti approcci:
● Semantic Overlay Network (SON);
● Skip Graphs (Skip Graphs ASPNES);
● WSPDS (BanaeilSWS2004);
● HyperCube (A Scalable and Ontology-Based P2P Infrastructure for Semantic Web Services);
● pSearch (PeertoPeer Information Retrieval Using SelfOrganizing Semantic Overlay Networks).
Mazza, Merlino, Messina 22
SWS in sistemi P2PSWS in sistemi P2PGeneralità
L'uso di tecnologie basate sul P2P per pubblicare e scoprire i Web Services aumenterà l'affidabilità e la scalabilità delle attuali architetture di calcolo distribuito. Un approccio P2P basato sull'uso delle ontologie permette di ottenere scoperte di servizi in modo dinamico, scalabile e decentralizzato. L'architettura di questo sistema prevede alcuni componenti funzionali:
● Costruttore del modello del processo (PMC);
● Richiesta di acquisizione e descrizione;
● Compositore di processi;
● Esecuzione del processo e valutazione;
● Motore per la scoperta dei servizi;
● Organizzazione del servizio e distribuzione;
● Repository di ontologie.
Mazza, Merlino, Messina 23
SWS in sistemi P2PSWS in sistemi P2PCostruttore del modello del processo
La funzione del PCM è quella di costruire e conservare
un processo logico in un database che contiene modelli
di processi basati sull'analisi del dominio e sull'ontologia
dei processi. Un processo logico potrebbe contenere
descrizioni di tipo semantico delle attività di un processo
e delle relazioni tra esse.
Mazza, Merlino, Messina 24
SWS in sistemi P2PSWS in sistemi P2PRichiesta di acquisizione e descrizione
Attraverso una buona interfaccia gli utenti possono
esprimere le loro richieste individuali al sistema. La
richiesta degli utenti contiene la descrizione sul dominio,
sulla semantica, sulle funzioni e sulle parole chiavi del
servizio.
Mazza, Merlino, Messina 25
SWS in sistemi P2PSWS in sistemi P2PCompositore di processi
Il compositore di processi cerca nel database dei processi
per trovare la logica del processo e poi stabilisce quali
sono i documenti che descrivono l'eseguibile di
quest'ultimo. Dopo ciò informa il motore di ricerca dei
servizi dove è possibile trovare il Web Service
appropriato.
Mazza, Merlino, Messina 26
SWS in sistemi P2PSWS in sistemi P2PEsecuzione del processo e valutazione
Il motore che esegue i processi lega direttamente
il servizio di corrispondenza al processo da
raggiungere durante la procedura di esecuzione.
Mazza, Merlino, Messina 27
SWS in sistemi P2PSWS in sistemi P2PMotore per la scoperta dei servizi
Il motore per la scoperta dei servizi chiede alla struttura
P2P di individuare il gruppo che comprende il servizio
richiesto e poi va al servizio di corrispondenza di tale
gruppo. Dopodiché, il sistema si lega a questo servizio e
lo ritorna al motore di esecuzione del processo affinché
venga eseguito.
Mazza, Merlino, Messina 28
SWS in sitemi P2PSWS in sitemi P2PMotore per la distribuzione dei servizi
Per facilitare l'organizzazione dei servizi, i peer possono
essere divisi in gruppi. Ogni gruppo contiene un certo tipo di
servizi. Il motore per la distribuzione dei servizi cerca un
appropriato gruppo di peer ed inserisce un nuovo peer in tale
gruppo. Questa organizzazione riduce lo spazio di ricerca
durante la scoperta dei servizi.
Mazza, Merlino, Messina 29
SWS in sistemi P2PSWS in sistemi P2PRepository di ontologie
Le funzioni componenti il sistema sono supportate da 3 categorie di ontologie:
● Ontologie di dominio: definiscono le informazioni semantiche in uno specifico dominio;
● ontologie di un Web Service: descrivono la gerarchia dei servizi, nella quale una sottoclasse di servizi eredita le proprietà e le funzionalità dalla superclasse;
● ontologie dei processi: rendono nota la sintassi e l'informazione semantica tra le attività presenti nella logica dei processi.
Mazza, Merlino, Messina 30
Ricerca in una rete P2P non Ricerca in una rete P2P non strutturatastrutturata
In sistemi P2P non strutturati come Gnutella, si organizzano i nodi della rete in un grafo casuale e si utilizza il flooding sul grafo per recuperare i documenti rilevanti per una query. Data una query, ogni nodo visitato, valuta la query localmente, confrontando la richiesta con il proprio contenuto, e poi inoltra la richiesta a tutti i suoi vicini. Query arbitrariamente complesse pertanto possono essere facilmente sostenute su tali sistemi. Anche se questo approccio è semplice e robusto, comporta degli enormi costi dovuti al flooding della rete ogni volta che una query viene inoltrata. Sono stati studiati miglioramenti del meccanismo usato da Gnutella: random walk, ricerca guidata, e l'organizzazione di nodi con contenuti simili in segmenti o gruppi.
Mazza, Merlino, Messina 31
Random WalkRandom Walk
E' utilizzato per affrontare il problema della scalabilità posto dal flooding su sistemi P2P non strutturati come Gnutella. Data una query, un random walk è essenzialmente una ricerca random in cui ad ogni passo la query è trasmessa ad un nodo scelto in modo casuale, senza prendere in considerazione suggerimenti di come probabilmente il prossimo nodo avrà risposte per la query. Due tecniche sono state proposte per porre fine al random walk: TTL (time-to-live) e "controllo". TTL significa che, come accadeva nel flooding, ogni random walk termina dopo un certo numero di salti, mentre il "controllo" si intende un walker controllato periodicamente dal nodo che ha prodotto la query prima di essere trasmesso al prossimo nodo.
Mazza, Merlino, Messina 32
Ricerca guidataRicerca guidata
La ricerca guidata rappresenta la tecnica di ricerca che permette di trasmettere ai nodi vicini le query che hanno maggiori probabilità di avere risposte, invece di inoltrare le query ai vicini scelti casualmente o di intasare la rete con le query da trasmettere. Si hanno tre schemi RI (routing indices): il composto, il count-hop e l'indice di routing esponenziale. L'idea di base della ricerca guidata è un meccanismo di indici distribuiti che mantiene un riferimento a ciascun nodo. Questi indici distribuiti sono piccoli e danno informazioni relativi alla "direzione" da prendere per giungere al documento, piuttosto che la sua effettiva ubicazione. Data una query, il routing indices di un nodo consente di selezionare i "migliori" vicini a cui inviare una query. Un RI è una struttura dati che, data una query, restituisce un elenco di vicini, classificati in base alla loro bontà per la query. La nozione di bontà generalmente riflette il numero dei documenti rilevanti in un nodo "vicino".
Mazza, Merlino, Messina 33
Ricerca basata su gruppi aventi Ricerca basata su gruppi aventi contenuti simili (parte 1)contenuti simili (parte 1)
L'idea di base dei gruppi di ricerca di contenuto analogo è quello di organizzare i nodi contenenti simili documenti in gruppi su sistemi P2P non strutturati come Gnutella. L'intuizione alla base di questa tecnica di ricerca è che i nodi all'interno di un gruppo tendono ad essere rilevanti per la stessa query. Di conseguenza, questa tecnica di ricerca guida la query per i nodi che hanno più probabilità di avere le risposte alla domanda, evitando in tal modo una notevole quantità di inondazioni. La ricerca in SETS, si avvale di un modello di ricerca guidato dal protocollo di routing su un sistema segmentato sovrapposto alla rete costruita da Gnutella.
Mazza, Merlino, Messina 34
Ricerca basata su gruppi aventi Ricerca basata su gruppi aventi contenuti simili (parte 2)contenuti simili (parte 2)
Il sistema è costruito ragruppando dei nodi in cluster, e per ogni cluster corrisponde un argomento. Pertanto,si creano partizioni di nodi in argomenti, in modo che i nodi con documenti simili appartenenti allo stesso segmento. Data una query, prima si calcola l'argomento R, si scelgono i segmenti che sono più rilevanti per la query e quindi si esegue la ricerca di questi documenti. Tuttavia, il nodo designato è potenzialmente un punto di fallimento ed anche un collo di bottiglia . Si organizzano i nodi utilizzando dei predicati associativi. Una regola guida è un insieme di nodi che soddisfano alcuni predicati; ogni nodo può appartenere a una serie di regole guida, e per ciascuna regola guida a cui partecipa in esso mantiene un piccolo elenco di altri nodi appartenenti alla stessa guida regola. L'idea chiave delle regole guide è che i nodi appartenenti ad una di esse devono contenere dati simili. Di conseguenza, la ricerca guidata limita la propagazione di query all'interno di alcune regole-guida specificate, invece di inondare tutta la rete.
Mazza, Merlino, Messina 35
Ricerca in sistemi P2P strutturatiRicerca in sistemi P2P strutturati
Dopo la prima generazione di sistemi P2P come KaZaA e Gnutella, sistemi P2P strutturati (o DHT-based), la seconda generazione di sistemi P2P, è stata proposta per fornire scalabilità a quei sistemi P2P Gnutella-based. Tali sistemi DHT-based data una chiave, possono individuare il corrispondente documento con solo O (log N) salti (N è il numero dei nodi del sistema). In sistemi P2P strutturati, la replica è stata sfruttata per migliorare la disponibilità dei dati e l'efficienza della ricerca. E' stato proposto un algoritmo probabilistico per migliorare la posizione di latenza esistente nei sistemi che fanno uso di una DHT, se la replica di un documento richiesto esiste vicino alla fonte della query. Una struttura ad indici distribuiti è costruita su ciascun nodo. Comunque, sostenere query complesse, come la ricerca di parole chiave e semantica del contenuto / ricerca su DHT è un compito non banale.
Mazza, Merlino, Messina 36
Ricerca tramite parola chiave Ricerca tramite parola chiave (parte 1)(parte 1)
Nella ricerca di parole chiave, una query contiene una o più parole chiave (o le condizioni) e il sistema di ricerca restituisce una serie di documenti che contengono tutte le parole chiave richieste per la query. Fondamentalmente, sono state proposte tre strutture di indicizzazione a sostegno dei sistemi P2P strutturati che fanno uso della ricerca tramite parole chiave: indicizzazione globale, indicizzazione ibrida, indicizzazione ibrida ottimizzata. Nella indicizzazione globale, il sistema nel suo insieme mantiene un indice invertito dei documenti che contengono il termine ricercato. Ogni nodo memorizza l'elenco invertito completo di questi termini che sono mappati nella sua DHT tramite un identificatore. Per rispondere a una query contenente più termini, la query viene instradato ai nodi responsabili di tali termini. A questo punto si individuano i documenti che sono costituiti da tutti i termini richiesti. Anche se l'indicizzazione globale comporta solo un piccolo numero di nodi per una query di ricerca, ha l'inconveniente di richiedere la comunicazione tra più nodi.
Mazza, Merlino, Messina 37
Ricerca tramite parola chiave Ricerca tramite parola chiave (parte 2)(parte 2)
Il costo della comunicazione cresce proporzionalmente con la lunghezza della lista. Nell'indicizzazione ibrida, ogni nodo mantiene l'elenco completo di tali termini mappato nella sua DHT. In aggiunta, per ogni documento nella lista invertita per alcuni termini t, il nodo mantiene inoltre la lista completa dei documenti che si riferiscono a tali termini. Dato un documento e più parole chiave di ricerca, la query viene instradato a nodi responsabili di tali termini. Ognuno di questi nodi esegue una ricerca locale senza contattare gli altri, poiché essi hanno la lista completa per ciascun documento nei rispettivi elenchi. Questa indicizzazione ibrida aumenta l'efficienza di ricerca al costo di pubblicare più meta-dati.
Mazza, Merlino, Messina 38
Ricerca tramite parola chiave Ricerca tramite parola chiave (parte 3)(parte 3)
Per diminuire i costi associati all'indicizzazione ibrida, fu proposto un sistema di indicizzazione ibrida ottimizzato. L'idea di base dietro tale sistema è che i meta-dati di un documento sono pubblicati solo per alcuni termini, piuttosto che per tutti i suoi termini. Ad esempio, un documento contenente D termini pubblica la sua lista solo per il termine responsabile in una query. Dato che conoscendo, la locazione di tali termini è ancora possibile determinare il documento che è la risposta completa alla query. Tuttavia, i risultati della ricerca possono essere non ottimali. Fu proposto di adottare tecniche di espansione automatica della query per affrontare questo problema.
Mazza, Merlino, Messina 39
Ricerca semanticaRicerca semantica
La ricerca semantica è basata su un contenuto di ricerca costituito da solo testo, le query sono espresse in linguaggio naturale. Quando una query è rilasciata da un utente, una rappresentazione della query è derivata dal suo testo integrale, abstract, o titolo, e poi presentata al sistema di recupero delle informazioni. La ricerca semantica presenta un impegnativo problema per i sistemi P2P strutturati: data una query, il sistema di ricerca deve o avere un gran numero di nodi o perdere alcuni documenti rilevanti. Sono stati proposti alcuni sistemi di ricerca semantica posti in cima ai sistemi P2P strutturati. Una caratteristica importante di tali sistemi di ricerca è di estendere gli algoritmi come Vector Space Model (VSM) e Latent Semantic Indexing (LSI), in ambiente P2P. La sovrapposizione semantica è una logica di rete in cui i documenti sono organizzati in vettori in modo che la distanza tra due documenti è proporzionale alla loro differenza semantica.
Mazza, Merlino, Messina 40
Semantic Overlay Network Semantic Overlay Network ( SON)( SON)
In generale il sistema prevede che le query siano instradate verso
un adatto SONs, incrementando le possibilità che il servizio
ricercato sia ritrovato velocemente e riducendo il carico relativo
alla ricerca ai soli nodi contenenti il servizio. E' un'organizzazione
della rete di tipo flessibile che migliora le performance relative
alle query mantenendo un alto grado di autonomia del nodo. I
nodi sono connessi tra loro in base alla somiglianza tra i loro
contenuti a livello semantico.
Mazza, Merlino, Messina 41
Costruzione di una Semantic Costruzione di una Semantic Overlay NetworkOverlay Network
● Valutazione della potenziale gerarchia di classificazione usando la distribuzione attuale dei dati nei nodi, trovando una buona gerarchia;
● decidere se questa gerarchia va posta (salvata) in ogni nodo o solo in alcuni.
Ogni nodo che si unisce al sistema deve:● mandare un pacchetto in flooding nella rete per ottenere la gerarchia
adottata;● avviare un classificatore di documenti basato sulla gerarchia
ottenuta, classificando tutti i propri documenti;● essere assegnato ad uno specifico SON.
Si possono usare due meccanismi per propagare le informazioni su tutta la rete:● flooding;● adozione di super peer.
Mazza, Merlino, Messina 42
Gerarchia di classificazioneGerarchia di classificazione
Una buona gerarchia di classificazione è quella che :
● produce un insieme di documenti che appartengono ad un piccolo numero di nodi;
● produce dei nodi che hanno un numero sufficientemente piccolo di insiemi di documenti;
● permette la facile implementazione di algoritmi di classificazione che commettono un basso numero di errori.
Mazza, Merlino, Messina 43
Vantaggi nell'adozione di SONVantaggi nell'adozione di SON
● Alta percentuale di richiamo con solo 1/5 dei messaggi necessari agli altri approcci ( Gnutella);
● facilità nel trovare anche servizi poco richiesti;
● autonomia dei nodi;● alta scalabilità.
Mazza, Merlino, Messina 44
Svantaggi nell'adozione di SONSvantaggi nell'adozione di SON
● Non si raggiunge in alcun caso il 100% di richiamo;
● difficoltà nella precisa classificazione dei nodi in maniera automatica;
● difficoltà nella precisa classificazione delle query.
Mazza, Merlino, Messina 45
Skip GraphsSkip GraphsDescrizione struttura dati (parte 1)
L'approccio dell'algoritmo è quello di sfruttare la struttura di base ad albero per garantire certe funzionalità, mentre l'applicazione di un semplice sistema di bilanciamento di tipo distribuito serve a preservare l'equilibrio e la distribuzione del carico. E' un nuovo modello per una rete peer-to-peer basato su una struttura di dati distribuiti che viene detta skip graphs. Questa struttura dati distribuita dispone di diversi vantaggi: posizione dinamica delle risorse l'inoltro del nodo e la cancellazione può essere effettuata in tempo logaritmico, e ogni nodo in un skip graphs richiede soltanto lo spazio per memorizzare le informazioni sui suoi vicini. Questo può essere utile per alcune applicazioni come il prefetching di pagine web poiché rafforza la navigazione, la ricerca e l'efficienza. Vi è stato un certo interesse nel sostenere le query complesse in sistemi peer-to-peer. Skip graphs è resistente al fallimento dei nodi: uno skip graphs tollera la rimozione di una grande frazione dei suoi nodi scelti in modo casuale senza creare problemi alla rete. Skip graphs può essere costruito anche senza la conoscenza del numero complessivo di nodi in anticipo. Al contrario, sistemi come Pastry e Chord richiedono la conoscenza a priori della dimensione del sistema. I sistemi skip graphs non hanno bisogno di conoscere la dimensione del keyspace in anticipo.
Mazza, Merlino, Messina 46
Skip GraphsSkip GraphsDescrizione struttura dati (parte 2)
Una skip list è una struttura dati ad albero randomizzata ed equilibrata, organizzata come una torre di liste collegate. Il livello 0 di una skip list è una lista di tutti i nodi in ordine crescente di chiave. Per ogni i superiore a 0, ogni nodo di livello i - 1 appare in modo indipendente al livello i fissato. In una skip list doppiamente legata, ogni nodo memorizza un puntatore predecessore e un puntatore successore per ogni elenco in cui appare, per una media di 1-p puntatori per nodo. Le liste, al livello superiore agiscono come "corsie di passaggio rapido" che consentono di ottenere la sequenza di nodi da attraversare rapidamente. La ricerca di un nodo, con una particolare chiave di ricerca coinvolge prima il livello più alto, fino a scendere la livello in cui il nodo si trova.
Mazza, Merlino, Messina 47
Skip GraphsSkip GraphsDescrizione struttura dati (parte 3)
Considerando il percorso di ricerca in senso inverso si ha che non più di 1-p nodi sono posti in media per ogni livello. Una skip list da sola non è sufficiente per un sistema P2P scalabile e robusto, in quanto è priva di ridondanza e quindi è vulnerabile a fallimenti e congestione. Poiché solo pochi nodi appaiono nella lista di più alto livello, ciascuno di tali nodi agisce come un unico punto di fallimento, e costituisce un "hot spot" che deve elaborare una frazione costante di tutte le operazioni di ricerca. Le skip list offrono anche alcune garanzie: i singoli nodi non sono separati dal resto anche con guasti casuali. Dal momento che ogni nodo è collegato, in media, a solo O (1) altri nodi, anche una costante probabilità di fallimenti farà isolare una grande frazione di nodi sopravvissuti. La soluzione è quella di definire una generalizzazione di una lista chiamata skip graphs. Come in una skip list, ciascuno degli n nodi in un skip graphs è un membro di più liste collegate. Il livello 0 della lista consiste di tutti i nodi in sequenza. Uno skip graphs supporta la ricerca, l'inserirmento, la cancellazione e operazioni analoghe a quelle delle liste. Perché ci sono molte liste ad ogni livello, la possibilità che ogni singolo nodo partecipa in alcune ricerche è piccola, ciò elimina i singoli punti di guasto. Inoltre, ogni nodo ha Θ (log n) vicini di casa, in media, e con elevata probabilità nessun nodo è isolato.
Mazza, Merlino, Messina 48
Skip GraphsSkip GraphsAlgoritmo (parte 1)
In una reale attuazione in un sistema P2P che utilizza uno skip graph, ogni nodo di tale struttura sarà una risorsa. Le risorse sono ordinate in ordine crescente lessicografico delle loro chiavi. La mappatura di queste chiavi può essere fatta in due modi: o ogni macchina è responsabile per le risorse che essa ospita o si utilizza un approccio che fa uso di una DHT. Il primo approccio dà sicurezza e gestibilità, mentre il secondo dà buon bilanciamento del carico. Ogni nodo in uno skip graphs memorizza l'indirizzo e la chiave del suo successore e predecessore, a ciascuno dei O (log n) livelli. Inoltre, ogni nodo ha bisogno anche di O (log n) bit di spazio per la sua adesione al vettore. In entrambi gli approcci di cui sopra, con n risorse in rete, ogni macchina deve mantenere O (log n) collegamenti per ogni risorsa che ospita, per un totale di O (n log n) collegamenti in tutta la rete. Questi fattori possono portare ad alto traffico di messaggi se ogni macchina periodicamente deve controllare se i suoi legami sono funzionali, come è comune in molte implementazioni P2P. Re-recentemente, una nuova struttura di dati chiamata albero è stata introdotta. Essa supera queste limitazioni. Un albero utilizza un numero costante di puntatori per nodo. Un tema centrale per l'attuazione di un grafico è la gestione delle liste.
Mazza, Merlino, Messina 49
Skip GraphsSkip GraphsAlgoritmo (parte 2)
La costruzione, l'inserimento in nuovi nodi, e la ricerca in uno skip graphs può essere fatta utilizzando semplici algoritmi. Gli skip graphs sono molto resistenti, tollerano una grande frazione di fallimento dei nodi senza perdere la connettività. Utilizzando il meccanismo di riparazione, l'interruzione della struttura può essere riparata in assenza di altri difetti. Rimane una questione da affrontare: il gran numero di puntatori per macchina nel sistema. Sarebbe interessante per la progettazione di un sistema peer-to-peer che si mantenesse un minor numero di puntatori possibile per macchina. Sarebbe interessante studiare le prestazioni in questa direzione, magari utilizzando degli skip graphs multidimensionali. Come con altri overlay network, sarebbe interessante vedere come la rete funziona in presenza di guasti. Infine, sarebbe utile sviluppare un meccanismo autonomo di stabilizzazione e riparazione.
Mazza, Merlino, Messina 50
WSPDSWSPDSDescrizione generale (parte 1)
Servizio di discovery decentralizzato basato su una architettura Peer-to-peer non strutturata (Gnutella). I vari serventi collaborano nella risoluzione delle query, il servizio di discovery, quindi, può essere visto come un servizio cooperativo. Vengono utilizzati, per descrivere i servizi, WSDL (per l'analisi dei parametri di input/output tramite sintassi description:location) e, come già detto, WSIL (per i metadati aggiunti e la ricerca basata su name/abstract). Viene utilizzato un sistema di flooding detto probabilistico basato sul sistema QDN (Query Data Network); ogni servente viene descritto in base ai servizi che offre ed inoltre, ogni volta che un servente si ritrova a dover fare il forward di una query esso la inoltra solo ai serventi suoi vicini aventi identità simile alla descrizione fornita tramite query.
Mazza, Merlino, Messina 51
WSPDSWSPDSDescrizione generale (parte 2)
Nel set-up della rete, quindi, ogni servente non tiene memoria di tutti i suoi vicini (sarebbe inutile), ma solo di quelli aventi descrizione semantica simile alla sua. Durante la ricerca delle query si tiene conto anche di meccanismi di sussunzione.Si può osservare come ogni servente sia composto da due motori:
● Motore di comunicazione;
● local query.
Mazza, Merlino, Messina 52
WSPDSWSPDSMotore di comunicazione (parte 1)
Responsabile di ricevere le query degli utenti trasformandole in local query e global query unendo i risultati e fornendo una risposta all'utente. In grado, inoltre, di ricevere le query dai propri vicini, risolverle localmente e fornire risposta al richiedente. Si occupa del forwarding dei messaggi nella rete. Per la comunicazione vengono utilizzati messaggi basati su SOAP. Il sistema Gnutella è stato migliorato utilizzando una tecnica detta probabilistic flooding. Il set-up della rete avviene tramite un sistema di caching; ogni servente mantiene una cache dei peer che ha recentemente osservato come attivi. Tale cache viene utilizzata dal servente ogni volta che il servente verrà riattivato e dovrà valutare i propri vicini.
Mazza, Merlino, Messina 53
WSPDSWSPDSMotore di comunicazione (parte 2)
La prima volta che un servente viene attivato può sfruttare la conoscenza di peer che forniscono servizi d'uso generale e che sono praticamente sempre attivi. I serventi valutano periodicamente i propri vicini utilizzando il classico sistema implementato da Gnutella (ping-pong). La ricerca avviene tramite un sistema di forwarding dei messaggi nella rete. Quando un peer riceve una query, inoltra la stessa ai propri vicini; esso esegue, inoltre, una query locale per verificare se esso stesso possiede il servizio ed in caso positivo restituisce una risposta al richiedente. Il messaggio è marcato tramite un campo TTL.
Mazza, Merlino, Messina 54
WSPDSWSPDSLocal query
Riceve le query dal motore di comunicazione, esegue una ricerca locale e passa nuovamente i risultati al motore di comunicazione. Sfrutta le specifiche WSIL per trovare servizi locali corrispondenti alle query ricevute. Il file WSIL fornisce per ogni servizio dei metadati che verranno utilizzati dal parser per il discovery del serivizio. Secondo lo standard WSIL possono essere anche specificate le features che nel futuro il servizio implementerà.
Mazza, Merlino, Messina 55
HyperCubeHyperCubeDescrizione generale (parte 1)
La rete è strutturata mediante l'utilizzo di un ipercubo i cui vertici sono i nodi della rete stessa. Il diametro della rete è definito come la massima distanza fra due nodi nella struttura. La struttura è simmetrica e nessun nodo ha posizione di maggior rilievo rispetto agli altri. La distanza fra due nodi vicini è marcata da un indice di distanza. I messaggi vengono inviati tramite un sistema broadcast a distanza predefinita (diametro della rete), ossia il nodo che invia il messaggio predetermina la distanza massima ed invia il messaggio a tutti i suoi vicini. Il messaggio sarà taggato con un indice rappresentante la distanza fra il nodo che invia il messaggio e quello che lo riceve. Ogni nodo ricevuto il messaggio valutera d=diam-t ove diam è il diametro della rete e t è il valore del tag sul messaggio. d rappresenta la distanza massima verso cui il messaggio possa essere inoltrato; esso sarà, quindi, inviato a tutti i vicini a distanza minore o uguale a d. Il sistema di broadcast può anche essere ristretto a dei sub-ipercubi.
Mazza, Merlino, Messina 56
HyperCubeHyperCubeDescrizione generale (parte 2)
Quando un nuovo peer entra nella rete esso può essere innestato al posto di un peer attualmente presente che verrà quindi spostato di posizione (il nuovo peer occuperà la posizione più adatta alla sua posizione semantica rispetto agli altri); nel momento in cui un peer invece esca dalla rete, un altro peer presente occuperà il suo posto. Una struttura simile è assicurata dal fatto che un peer può essere connesso più volte ad un altro nella struttura dell'ipercubo (anche con distanze differenti) e un peer può occupare una posizione anche solo temporaneamente in attesa di ingressi futuri. Un simile algoritmo (ricorsivo) presenta complessità logaritmica. Possiamo utilizzare topologie di rete differenti dall'ipercubo; lo stesso appartiene ad una classe di grafi detta di Cayley. Un grafo di Cayley che assicura migliori prestazioni in termini di scalabilità di numero di peer (complessità sottologaritmica).
Mazza, Merlino, Messina 57
HyperCubeHyperCubeDescrizione generale (parte 3)
La struttura della rete è organizzata semanticamente in modo che i peer siano raggruppati in strutture dette Cluster che sono assegnate a specifiche combinazioni logiche di concetti ontologici. Ogni cluster presenta una struttura ad ipercubo o a stella e tutti i cluster sono tenuti insieme mediante una struttura ad ipercubo o a stella i cui nodi sono rappresentati dai cluster. Lo schema di indirizzi concatena un set di concept coordinates ed un set di storage coordinate. Le concept coordinates permettono di identificare un cluster nell'ipercubo esterno. Le storage coordinates permettono, invece, di indicizzare i peer all'interno di un cluster. La concatenazione di concept coordiates e di storage coordinates rappresenta l'indirizzo logico del peer.
Mazza, Merlino, Messina 58
HyperCubeHyperCubeDescrizione generale (parte 4)
Il sistema di invio delle query consiste di due momenti; dapprima, la query è inviata al cluster ove si ipotizza che si trovi un peer che fornisce il servizio richiesto e poi si utilizza un invio broadcast a tutti i peer del cluster. Una query, prima di essere inviata, viene ridotta ai suoi mintermini (ossia elementi di base della query; ad esempio la query E A D ∨ ∧consiste nei mintermini E ed A D). Si osserva a quale ∧gruppi potrebbe essere indirizzata la query; ogni mintermine rappresenta un gruppo di concept cluster nella rete. La query è inoltrata al gruppo cosicché possa essere inviata in broadcast a tutti membri del gruppo. Una volta che la query raggiunga un peer, questo ha la possibilità di rispondere alla stessa (ad esempio contattando il richiedente).
Mazza, Merlino, Messina 59
HyperCubeHyperCubeDescrizione generale (parte 5)
I peer possono entrare a far parte della struttura contattando altri peer. La descrizione semantica dei servizi offerti dal peer sarà utile per poterlo assegnare ad un dominio. Se il peer descrive se stesso tramite concetti non specifici di nessun gruppo esso sarà inserito all'interno del gruppo (comunque) più specifico. Determinato il gruppo di appartenenza di un peer, sarà inviato in broadcast un messaggio a tutti i peer del gruppo affinché essi lo inseriscano nelle loro tabelle di routing. È desiderabile utilizzare un algoritmo in grado di valutare automaticamente se è il caso di realizzare un nuovo gruppo (ciò non è stato ancora realizzato, i gruppi sono attualmente preimposti).
Mazza, Merlino, Messina 60
pSearchpSearchOrganizzazione dell'overlay semantico
I peer sono organizzati in semantic overlay che formano i pSearch Engine all'interno dei quali i nodi hanno funzioni omogenee. Non tutti i nodi nella struttura devono far parte dell'engine ma verranno utilizzati solo quelli stabilmente connessi (il tutto rimane comunque dinamico) ogni componente dell'engine si occuperà dell'indirizzamento in un proprio sottoinsieme di vicini. pSearch utilizza una rete CAN per organizzare i nodi di engine l'algoritmo è detto pLSI. Il pLSI impone che la dimensione della rete CAN sia pari a quella dello spazio semantico LSI. La chiave identificativa nella rete di un documento sarà pari al suo vettore semantico. Allorquando venisse ricevuta una query, essa sarà instradata usando il suo vettore semantico. Qualunque nodo dell'engine confronterà il vettore semantico della query con il proprio e quello dei propri vicini.
Mazza, Merlino, Messina 61
pSearchpSearchSvantaggi
Esistono vari problemi dovuti all'utilizzo di un simile approccio:
● pLSI setta la dimensione della CAN ad un numero di nodi pari allo spazio semantico LSI, tuttavia la dimensione massima per la CAN è notevolmente più ridotta;
● l'utilizzo di vettori semantici come chiavi per la CAN risulta sbilanciare la struttura della rete stessa;
● risulta difficile limitare la ricerca a spazi ridotti di molte dimensioni.
Mazza, Merlino, Messina 62
pSearchpSearchRolling Index
Per risolvere le query più velocemente pSearch utilizza un metodo detto Rolling Index. Dato un vettore semantico esso viene ricombinato un certo numero di volte così da creare dei rotated semantic vectors. I vettori “ruotati” di documenti diversi generati con lo stesso numero di rotazioni formano un rotated space all'interno del quale possono essere effettuate ricerche (essendo il matching indipendente dalla posizione degli elementi nel vettore). In questo modo, sacrifichiamo spazio in memoria ma ottimizziamo le ricerche. Per occupare meno spazio, i vettori rotati vengono suddivisi in sottovettori; si dimostra come la ricerca non risenta di questo accorgimento. La ricerca globale migliora di molto tramite l'utilizzo del Rolling Index tuttavia, non si notano grandi miglioramenti nella ricerca di singoli documenti; per risolvere tale difetto si utilizzerà una cosiddetta selective rotation tramite la quale, oltre che memorizzare l'indice del documento nei suoi rotated spaces lo memorizzeremo anche nei rotated spaces dei suoi sottovettori.
Mazza, Merlino, Messina 63
pSearchpSearchBilanciamento del carico
Al fine di bilanciare il carico di rete, all'ingresso di un nuovo peer nella stessa, il vettore che lo rappresenta viene ruotato un numero casuale di volte e tale vettore è usato come punto attraverso il quale inizia il routing; tale processo è detto content-aware node bootstrapping. Per ridurre lo spazio di ricerca si suppone che i vari nodi formino, attorno ad essi, dei cluster di nodi trattanti argomenti semanticamente simili (se si trova un documento rilevante, in prossimità di esso vi saranno risultati simili. Vengono utilizzati sistemi di euristica). La ricerca avverrà, quindi, in sottoinsiemi formati dai cluster.