David Novak and Pavel Zezula
GRUPPO 13
Decorte Andrea
Giammarino Giuseppe
 Utente f0rnisce un’immagine
 Trovare immagini simili nel database
basandosi su distanza quadratica tra le
features
LA (h, q; A) 
D
D
T
a
(
h

q
)(
h

q
)

(
h

q
)
 A  (h  q)
 i, j i i j j
i 1 j 1
Difficoltà nel lavorare con
dati di questo genere?
Gruppo 13 M-Chord
2
 Dati ad alta dimensionalità
 Funzioni distanza onerose computazionalmente
(nell’ordine di O(D2))
 Dati non gestibili efficientemente con spazi vettoriali
 Query multidimensionali di similarità
Servono nuove strategie!
Gruppo 13 M-Chord
3
 Introduzione di spazi metrici anziché vettoriali
 Sviluppo di strategie distribuite per dividere il carico di
lavoro su nodi interconnessi tra loro
 Al momento della pubblicazione, numerosi studi su
applicazioni di ricerca distribuita, ma la maggior parte
di loro si concentrano su spazi vettoriali
 Gli unici riguardanti spazi metrici sono GHT*
(nativamente metrica, basata sui Generalized
Hyperplane Tree) e MCAN, che estende il protocollo
CAN (Content Addressable Network)
Gruppo 13 M-Chord
4
 Sviluppare una struttura per la ricerca distribuita che
sia applicabile a spazi metrici basandosi su alcune
soluzioni esistenti:
 iDistance
 Protocollo Chord
 Esse verranno integrate ed estese nella struttura di M-
Chord
Gruppo 13 M-Chord
5
Uno spazio metrico M è una coppia (U, d)
 U è il dominio degli oggetti
 d è una funzione di distanza
Tutti gli oggetti di U soddisfano le seguenti proprietà:
d ( x, y )  0
d ( x, y )  0 iff x  y
d ( x, y )  d ( y , x )
d ( x, z )  d ( x, y )  d ( y  z )
(non negatività)
(identità )
( simmetria )
(diseg . triangolar e)
Gruppo 13 M-Chord
6
 Metodo di indicizzazione per ricerca di similarità in
spazi vettoriali
 Partizione dei dati in n cluster, rappresentati da un
pivot pi
 A ogni oggetto x viene assegnata chiave
unidimensionale che tiene conto della distanza dal
pivot
iDist ( x)  d ( pi , x)  i  c
 c è una costante per separare i cluster
 Valori sono memorizzati in un B+-tree sulla base della
chiave iDist(x)
Gruppo 13 M-Chord
7
P2
C0
C2
P0
C1
P1
C
2*C
Gruppo 13 M-Chord
3*C
8
 Protocollo P2P per Distributed Hash Table
 Chord specifica come chiavi debbano essere assegnate
ai nodi, come si possa localizzare nodo responsabile
per una chiave e come esso recuperi valore di una
chiave specifica
 Basato su scambio di messaggi
 Dinamico, consistent hashing
 Dominio mappato uniformemente nell’intervallo
[0,2m)
Gruppo 13 M-Chord
9
 Le chiavi Ki sono disposte su un cerchio
 A ogni nodo Ni viene assegnata la chiave
Ki dallo stesso dominio
 Nodo Ni responsabile per tutte le chiavi
dell’intervallo (Ki-1, Ki](mod 2m)
 Ogni nodo mantiene successore, predecessore e finger
table, che garantisce un routing di complessità O(log n)
Gruppo 13 M-Chord
10
• Finger table ha
dimensioni minori
rispetto al numero
totale nodi
N8
• Tiene anche in conto
possibilità di failure del
nodo
+1
N51
• Necessario mantenerla
aggiornata nel tempo
N48
• Non contiene info
necessarie per
raggiungere valori di
chiave direttamente
Finger Table
N1
+2
+4
+32
+8
N8+1
N14
N8+2
N14
N8+4
N14
N8+8
N21
N8+16
N32
N8+32
N42
N14
+16
N42
N21
N38
N32
Gruppo 13 M-Chord
11
Cercando la chiave 54 è
necessario visitare 2 altri nodi.
Se non avessi finger table, li
dovrei passare tutti!
Algoritmo semplificato per
cercare una chiave:
• Se appartiene a chiavi locali,
restituisci il valore
• Altrimenti accedi alla finger
table e cerca il più grande
predecessore della chiave
richiesta, in modo da
avvicinarsi il più possibile al
nodo che contiene la chiave
K54
N56
N1
N8
lookup(54)
N51
N48
N14
N21
N42
N38
N32
Gruppo 13 M-Chord
12
Idee alla base di M-Chord:
 Generalizzare iDistance a spazi metrici e adattare il
suo dominio a quello di Chord
 Dividere il dominio in intervalli da distribuire sui
diversi nodi
 Sviluppare gli algoritmi Range e kNN
 Introdurre meccanismi di pruning
Gruppo 13 M-Chord
13
 Durante partizionamento, che sfrutta diagrammi di
Voronoi, distanze dei punti da ogni pivot sono salvate per
essere poi sfruttate nel pruning delle query di Range
 Data una query Range(q, r), per diseguaglianza triangolare
oggetto x può essere escluso senza valutare d(q, x) se
i (0  i  n) :| d ( pi , x)  d ( pi , q) | r
r
x
q
Pi
d(x,Pi) - d(q,Pi) >r ?
Gruppo 13 M-Chord
14
 Selezione pivot
 Criterio di selezione: aumentare il più possibile il
filtraggio
 Dominio dei dati
 Necessaria una funzione di trasformazione h per
normalizzare il dominio fornito da iDistance
sull’intervallo [0, 2m) ed ottenere una distribuzione
uniforme
mchord ( x)  h(d ( pi , x)  i  c)
Gruppo 13 M-Chord
15
 Topologia della rete corrisponde a quella di Chord
 Fase di inizializzazione (SampleSet S, numero pivot)
 Un solo nodo attivo che copre tutto (chiave 2m-1)
 Selezione dei pivot su S
 Si applica formula di iDistance su S per avere
distribuzione dei dati e si ricava funzione di
trasformazione h in modo da poter calcolare mchord(x)
Gruppo 13 M-Chord
16
 Attivazione altri nodi
 I nodi a cui non sono assegnate chiavi sono non attivi
 Ogni nodo attivo può invocare una richiesta di split
secondo criteri personalizzati (carico…)
 Procedura di split
 Si determina la nuova chiave Ki da assegnare al nodo
 Si spostano i dati al nuovo nodo e si segue il
meccanismo standard di join di Chord
 Si cerca di seguire le forme dei cluster se intervallo copre
più di un cluster
Gruppo 13 M-Chord
17
 Segue l’idea di range query di iDistance
 Il nodo Nq che avvia la query procede nel seguente
modo:
 Determina per ogni cluster Ci l’intervallo di chiavi Ii
I i  [h(d ( pi , q)  i  c  r ), h(d ( pi , q)  i  c  r )]
 Per ogni i invia una richiesta di INTERVALSEARCH(Ii, q, r)
al nodo Ni responsabile per il punto centrale
dell’intervallo Ii
Gruppo 13 M-Chord
18
 Se nodo non responsabile dell’intero intervallo, inoltra
richiesta a predecessore/successore
 Ogni nodo crea risposta locale
che include gli x | d(q,x)≤ r
 Invio risposta segnalando
eventualmente che è
Nq
necessario attendere quella
di altri nodi
 Qui si sfruttano distanze
NI2
calcolate in precedenza
e formula di filtraggio di iDistance
Gruppo 13 M-Chord
I3
NI3
I1
NI1
wait
I2
19
 iDistance può escludere un cluster i da ricerca se
d(pi, q) –r > max-disti
r
q
max-disti
Pi
 Tale pruning non è applicabile in ambienti distribuiti
(max-disti non conosciuto da tutti i nodi)
Gruppo 13 M-Chord
20
 Approccio di iDistance non adatto ad ambienti
distribuiti (query di range a raggio crescente)
 Proposta degli autori:
1.
Utilizzo un’euristica a basso costo per trovare k oggetti
vicino q; δk è un’approssimazione (upper bound) della
distanza del k-esimo oggetto
Gruppo 13 M-Chord
21
 Nodo responsabile per mchord(q) cerca nel cluster Ci a
cui appartiene q
1. Localizza la foglia del B+-Tree dove si trova q
2. Esplora a sinistra e destra le foglie e aggiunge i primi
k oggetti al ResultSet, inizializzando δk
3. Continua a esaminare x finché le chiavi mchord(x)
appartengono
a I i  [h(d ( pi , q)  i  c   k ), h(d ( pi , q)  i  c   k )]
K=2
4. Se d(q,x) < δk aggiungo x a RS al posto del k-esimo
- δk δ
q
oggetto e aggiorno
+ δk
k
5. Continuo ricerca finché non ho esplorato tutto Ii o
δk = mchord(q)
distanza K-esimo oggetto
tutto cluster Ci
Gruppo 13 M-Chord
22
2.
Eseguo una query di Range (q, δk) su altri cluster (salto
spazio già esplorato) e restituisco i k oggetti più vicini
 Si presume la presenza di almeno k oggetti in Ci,
altrimenti strategia ottimistica
Gruppo 13 M-Chord
23
 2 dataset di esempio:
 Immagini rappresentate da vettori di 45 dimensioni
 Corpus di testi confrontati con edit distance
 Buona scalabilità all’aumentare delle dimensioni della
query e del dataset
 Cresce tuttavia numero messaggi scambiati
 Possibilità di influire sulle prestazioni agendo su
politiche di split dei nodi
Gruppo 13 M-Chord
24
 Buoni livelli di parallelismo intraquery (stessa query
processata in parallelo) ed interquery (più query
contemporanee)
Gruppo 13 M-Chord
25
 Costi maggiori per kNN query
Gruppo 13 M-Chord
26
 Limiti:
 Previsto solo inserimento nuovi oggetti, no
eliminazione/aggiornamento
 Nessun supporto per disconnessione nodi
 Pruning di iDistance da adattare a ambiente distribuito
 Ulteriori studi:
 Prestazioni su spazi vettoriali a bassa dimensionalità
 Replicazione
Gruppo 13 M-Chord
27
GRUPPO 13
Decorte Andrea
Giammarino Giuseppe