• Peer-to-Peer Systems
Content-Based Routing of Path
Queries in Peer-to-Peer Systems
Georgia Koloniari and Evaggelia Pitoura
Ingargiola Salvatore
Montauti Andrea
Pompei Fabio
• Sommario
• Introduzione
• Sistemi Peer-to-Peer
• Filtri di Bloom
• Organizzazione reti P2P: Content-Based
• Risultati Sperimentali
• Conclusioni
• Introduzione
“Migliorare le performance di
information retreaving in sistemi P2P”
Ipotesi di lavoro:
• Contenuto nodi: documenti XML schema-less
sintetizzati mediante filtri di Bloom multilivello
• Organizzazione rete: P2P Content-Based
• Tipologia query: path queries (XPath-like)
• Sistemi P2P: Stato dell’Arte
• Sistema Peer to Peer ibrido:
• impiega un server centrale per ottenere
meta-informazioni sull'identità dei Peer che
posseggono le informazioni richieste.
Napster e OpenNap
• Sistema Peer to Peer puro:
• I Peer sono connessi direttamente tra di loro.
• Non è necessario un server principale.
• Query routing: flooding, indici decentralizzati.
Gnutella e Freenet
• Filtro di Bloom
Un Bloom Filter è un vettore di bit definito da due
parametri :
2. K funzioni di Hash indipendenti con CDom in [1,M]
I bit del filtro sono usati per codificare in modo
efficiente un insieme di N oggetti.
Per Costruire un Bloom filter si scorrono uno dopo
l’altro gli oggetti dell’insieme. Applicando K funzioni
hash ad ogni oggetto si ottengono K valori hash, ogni
h1(a) = 4
h2(a) = 2
1
1
1
h3(a) = 5
h4(a) = 8
M=10 bits
1. Array di M bit
1
valore rappresenta la posizione di un bit che deve
essere settato ad uno.
N.B. : più di una chiave può settare lo stesso bit.
K = 4 funzioni di Hash
• Filtro di Bloom: esempio
Empty filter
pane
vino
pasta
Bloom Filter
QUERY
cane
gatto
THIVE
C
I
S
T
A
O
P
EM
O
S
L
N
A
F
• Filtri di Bloom multilivello
Filtri di Bloom semplici inadeguati per
sintetizzare la struttura multilivello dei
documenti XML.
Soluzioni proposte:
• Breadth Bloom Filters (BBF)
• Depth Bloom Filters (DBF)
• Breath Bloom Filter
XML
<sport>
<moto>
</moto>
<auto>
<f3000></f3000>
<f1></f1>
</auto>
</sport>
sport
moto
f3000
auto
f1
BBF0
1 1 1 0 1 0 1 1 1 1
BBF1
1 0 1 0 1 0 0 0 0 0
BBF2
0 1 1 0 0 0 1 0 0 1
BBF3
0 1 0 0 1 0 0 1 1 1
• BBF filter-match operation
sport
moto
Root query:
auto
f3000
/sport/auto/f1
f1
BBF0
1 1 1 0MA1TC0H 1 1 1 1
sport U auto U f1
1 1 1 0 1 0 1 0 1 1
BBF1
1 0 1 0MA1TC0H0 0 0 0
sport
1 0 1 0 1 0 0 0 0 0
BBF2
0 1 1 0MA0TC0H1 0 0 1
auto
0 0 1 0 0 0 1 0 0 1
BBF3
0 1 0 0MA1TC0H 0 1 1 1
f1
0 1 0 0 0 0 0 0 1 1
• Depth Bloom Filter
XML
<sport>
<moto>
</moto>
<auto>
<f3000></f3000>
<f1></f1>
</auto>
</sport>
sport
moto
f3000
DBF0
1 1 1 0 1 0 1 1 1 1
DBF1
0 1 1 0 1 0 0 1 0 1
DBF2
1 0 0 0 1 1 1 0 0 1
auto
f1
• DBF filter-match operation
sport
moto
Root query:
auto
f3000
/sport / auto / f1
f1
DBF0
1 1 1 0MA1TC0H 1 1 1 1
sport U auto U f1
1 1 1 0 1 0 1 0 0 1
DBF1
0 1 1 0MA1TC0H 0 1 0 1
sport/auto U
auto/f1
0 0 1 0 1 0 0 1 0 1
DBF2
1 0 0 0MA1TC1H 1 0 0 1
sport/auto/f1
1 0 0 0 1 0 1 0 0 0
• Risultati Sperimentali
80
BBF ≈ DBF con
filtri maggiori di
78.000 bit
60
simple
breadth
depth
40
20
0
30000
50000
78000
96000
150000
Grandezza Filtri
100
Migliori
performance di BBF
con elevato numero
di elementi
% Falsi Positivi
% Falsi Positivi
100
80
60
simple
40
breadth
20
depth
0
10
25
50
100
Elementi per documento
150
• Struttura gerarchica reti P2P
Local filter
Local filter n6
0 1 0 1 0 1 1 0 0 1
1 0 0Merged
0 0 1 1 filter
1 0 1
Merged filter Nn
N6
1 1 0 1 0 1 1 1 0 1
1 0 0
1 0 1 1
1 0
0 1 0 1
0
n2
Merged filter N7
Merged filter
1 1 0 1 0 0 0 0 0 0
1 1 0 1 0 1 1 1 0 1
Local filter
1 1 1 1 0 0 0 0 0 1
n1
Local filter
Merged filter
0 1 0 1 0 1 10 11 00 01 0 1 1 1 0 1
Local filter n4
Local filter n5
1 0 0 1 0 0 0 0 0 1
1 1 0 0 0 1 1 1 0 1
n5
Merged filter N6
1 1Merged
0 1 0 1 1
1 0 1N7
filter
1 Merged
1 0 1 0 0filter
0 0 0 Nn
0
1 0 0 0 0 1 0 1 0 0
• Content-Based
Struttura gerarchica organizzata non più
sulla prossimità dei nodi bensì sulla
similarità dei loro contenuti
Operazioni analizzate:
• Join
• Query routing
• Update: CountSum, BitSum
• Content-Based: Join
XML
<foto>
<calendario>
<modelle>
</modelle>
</calendario>
</foto>
Merged filter
Merged filter
1 1 0 1 0 1 0 1 1 1
0 1 0 1 0 1 0 1 0 1
Similarity = m – d(Nx, Ny)
Filter nX
1 0 0 0 0 1 0 1 0 0
Funzione
Hash N1
Nx
Merged filter
9
N6
N7
N2
6
5
7
1 0 0 0 0 0 0 1 0 0
Threshold = 6
Filter
nX
Filter nX
nX
1 0 100 000 00 110 100 10 0 0
n1
Query filter
Path query
• Content-Based:
Query routing
//calendario/modelle
1 0 0 1 0 1 0 1 0 1
==
Local filter
1 1 1 0 0 0 0 1 0 0
A
Query filter
1 0 0 1 0 1 0 1 0 1
Query filter
Path query
• Content-Based:
Query routing
//calendario/modelle
1 0 0 1 0 1 0 1 0 1
Local filter N7
1 0 1 1 0 0 0 1 0 0
Merged filter N7
1 1 1 1 0 0 0 1 0 0
Merged filter Nnr
Merged filter N1r
1 1 1 1 0 1 0 1 0 1
Query filter
1 0 0 1 0 1 0 1 0 1
QueryPath
filter
query
• Content-Based: Query routing
1 0 0//calendario/modelle
1 0 1 0 1 0 1
Local filter N1
1 0 1 0 0 0 0 1 0 0
Query filter
1 0 0 1 0 1 0 1 0 1
Merged filter N1
1 1 1 1 0 1 0 1 0 1
Query filter
• Content-Based: Query routing
1 0 0 1 0 1 0 1 0 1
==
Local filter N3
1 1 0 1 0 1 0 1 0 1
Query filter
XML
1 0 0 1 0 1 0 1 0 1
Path query
//calendario/modelle
<foto>
<calendario>
<modelle>
</modelle>
</calendario>
</foto>
• Content-Based: Update
CountSum
BitSum
0
0
1
0
1
0
1
1
0
0
1
0
1
0
1
1
0
0
2
0
3
0
2
5
0
0
2
0
2
0
2
2
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
2
0
1
3
1
0
1
2
2
0
1
3
1
0
1
2
CountSum
BitSum
1
0
1
1
1
0
1
1
3
0
3
5
2
0
2
2
1
0
1
1
1
0
1
1
1
0
1
2
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
2
1
0
1
2
2
1
0
1
0
tempo
CountSum
BitSum
1
0
1
1
1
0
1
1
3
0
3
4
5
2
0
2
2
1
0
1
1
1
0
1
1
1
0
1
2
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
2
1
1
0
1
2
1
2
1
0
1
0
tempo
CountSum
BitSum
1
0
1
1
1
0
1
1
3
0
3
4
3
2
0
2
2
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
1
0
1
0
1
0
1
1
0
1
1
0
1
0
1
0
1
2
1
0
1
0
tempo
CountSum
BitSum
1
0
1
1
1
0
1
1
3
0
3
4
3
2
0
2
2
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
1
0
1
0
1
2
1
0
1
0
tempo
CountSum
BitSum
1
0
1
1
1
0
1
1
3
0
3
5
4
2
0
2
2
1
0
1
1
1
0
1
1
1
0
1
2
1
1
0
1
1
1
0
1
1
1
0
1
1
1
0
1
1
2
1
0
1
1
2
2
1
Con il metodo
Bitsum meno
scambi di messaggi
0
1
0
tempo
• Risultati Sperimentali
80
In sistemi
content-based
convergenza più
veloce
no filter
non content
content
60
40
20
0
0
50
100
150
200
Numero massimo di salti
100
Con filtri multilivello
minor numero di
salti per completare
la query
% of matching-nodes
% of matching-nodes
100
80
60
40
SBF content
BBF content
DBF content
20
0
0
50
100
150
Numero massimo di salti
200
• Conclusioni
Dal
processo
dicotomico
dell’analisi
sperimentale si evince che il miglioramento
delle performance nell’information retreaving
può essere ottenuto mediante:
1. Organizzazione gerarchica Content-Based
2. Filtri di Bloom multilivello BBF
3. BitSum come implementazione dei contatori
• Bibliografia
1. G. Koloniari, E. Pitoura. (2004) Content-Based Routing of Path
Queries in Peer-to-Peer Systems. In Proceedings of the 9°
Intenational Conference on Extending Database Technology, pages
29-47.
2. G. Koloniari, E. Pitoura. Filters for XML-based Service Discovery in
Pervasive Computing. Computer Science Dept, University of
Ioannina, Greece.
3. X. Gong, W. Qian, Y. Yan, A. Zhou. Bloom Filter-based XML Packets
Filtering for Millions of Path Queries. Department on Computer
Science and Enngineering Fundan University, Shanghai, China.
4. N. Gioia. (2004) Un sistema Peer-to-Peer per l’interrogazione
distribuita di dati XML. Tesi di Laurea, Università degli studi di Pisa.
• Peer-to-Peer Systems
Content-Based Routing of Path
Queries in Peer-to-Peer Systems
Georgia Koloniari and Evaggelia Pitoura
Ingargiola Salvatore
Montauti Andrea
Pompei Fabio