David Novak and Pavel Zezula

M-CHORD: A SCALABLE

DISTRIBUTED SIMILARITY SEARCH

STRUCTURE

GRUPPO 13Decorte Andrea Giammarino Giuseppe

2Gruppo 13 M-Chord

Utente f0rnisce un’immagineTrovare immagini simili nel database

basandosi su distanza quadratica tra lefeatures

Esempio

)()())(();,(1 1

, qhAqhqhqhaAqhL TD

i

D

jjjiijiA

Difficoltà nel lavorare con dati di questo genere?

3Gruppo 13 M-Chord

Dati ad alta dimensionalitàFunzioni distanza onerose computazionalmente

(nell’ordine di O(D2))Dati non gestibili efficientemente con spazi vettorialiQuery multidimensionali di similarità

Servono nuove strategie!

Scenario

4Gruppo 13 M-Chord

Introduzione di spazi metrici anziché vettorialiSviluppo di strategie distribuite per dividere il

carico di lavoro su nodi interconnessi tra loroAl 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)

Idee e soluzioni esistenti

5Gruppo 13 M-Chord

Sviluppare una struttura per la ricerca distribuita che sia applicabile a spazi metrici basandosi su alcune soluzioni esistenti:iDistanceProtocollo Chord

Esse verranno integrate ed estese nella struttura di M-Chord

Proposta degli autori

6Gruppo 13 M-Chord

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à:

Spazio metrico

)(),(),(

),(),(

0),(

0),(

zydyxdzxd

xydyxd

yxiffyxd

yxd

).(

)(

)(

)(

etriangolardiseg

simmetria

identità

negativitànon

7Gruppo 13 M-Chord

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

c è una costante per separare i clusterValori sono memorizzati in un B+-tree sulla

base della chiave iDist(x)

iDistance

cixpdxiDist i ),()(

8Gruppo 13 M-Chord

iDistance

P0

P2C0

C1

C2

C 2*C 3*C

P1

9Gruppo 13 M-Chord

Chord (http://pdos.csail.mit.edu/chord/)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 messaggiDinamico, consistent hashingDominio mappato uniformemente

nell’intervallo [0,2m)

10Gruppo 13 M-Chord

ChordLe chiavi Ki sono disposte su un cerchio

A ogni nodo Ni viene assegnata la chiave

Ki dallo stesso dominioNodo 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)

11Gruppo 13 M-Chord

N1

N8

N14

N21

N51

N48

N42

N38N32

+1+2+4

+8+16

+32

Finger Table

N8+1 N14

N8+2 N14

N8+4 N14

N8+8 N21

N8+16

N32

N8+32

N42

Chord: finger table• Finger table ha

dimensioni minori rispetto al numero totale nodi

• Necessario mantenerla

aggiornata nel tempo

• Non contiene info necessarie

per raggiungere valori di chiave

direttamente

• Tiene anche in conto

possibilità di failure del nodo

12Gruppo 13 M-Chord

Chord: esempio lookupN1

N8

N14

N21

N51

N48

N42

N38N32

lookup(54)

K54Cercando 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

N56

13Gruppo 13 M-Chord

Idee alla base di M-Chord:Generalizzare iDistance a spazi metrici e

adattare il suo dominio a quello di ChordDividere il dominio in intervalli da distribuire

sui diversi nodiSviluppare gli algoritmi Range e kNNIntrodurre meccanismi di pruning

M-Chord

14Gruppo 13 M-Chord

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

M-Chord: Pruning

xr

q Pi

d(x,Pi)

- d(q,Pi)>r ?

rqpdxpdnii ii |),(),(|:)0(

15Gruppo 13 M-Chord

Selezione pivotCriterio di selezione: aumentare il più possibile

il filtraggioDominio dei dati

Necessaria una funzione di trasformazione h per normalizzare il dominio fornito da iDistance sull’intervallo [0, 2m) ed ottenere una distribuzione uniforme

M-Chord: Pivot e dominio

)),(()( cixpdhxmchord i

16Gruppo 13 M-Chord

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 SSi 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)

M-Chord: Funzionamento

17Gruppo 13 M-Chord

Attivazione altri nodiI nodi a cui non sono assegnate chiavi sono non

attiviOgni 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

M-Chord: Funzionamento

18Gruppo 13 M-Chord

Segue l’idea di range query di iDistanceIl nodo Nq che avvia la query procede nel

seguente modo:Determina per ogni cluster Ci l’intervallo di

chiavi Ii

Per ogni i invia una richiesta di INTERVALSEARCH(Ii, q, r) al nodo Ni responsabile per il punto centrale dell’intervallo Ii

M-Chord: Range search

)]),((),),(([ rciqpdhrciqpdhI iii

19Gruppo 13 M-Chord

Se nodo non responsabile dell’intero intervallo, inoltra richiesta a predecessore/successore

Ogni nodo crea risposta localeche include gli x | d(q,x)≤ r

Invio risposta segnalandoeventualmente che ènecessario attendere quelladi altri nodi

Qui si sfruttano distanzecalcolate in precedenzae formula di filtraggio di iDistance

M-Chord: INTERVALSEARCH (Ii, q, r)

I1

I2

I3

NqNI1

NI2

NI3

wait

20Gruppo 13 M-Chord

iDistance può escludere un cluster i da ricerca se

d(pi, q) –r > max-disti

Tale pruning non è applicabile in ambienti distribuiti (max-disti non conosciuto da tutti i nodi)

M-Chord: Range search

Pi

max-disti

qr

21Gruppo 13 M-Chord

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

M-Chord: kNN search

22

Nodo responsabile per mchord(q) cerca nel cluster Ci a cui appartiene q

1. Localizza la foglia del B+-Tree dove si trova q2. 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

4. Se d(q,x) < δk aggiungo x a RS al posto del k-esimo oggetto e aggiorno δk

5. Continuo ricerca finché non ho esplorato tutto I i o tutto cluster Ci

M-Chord: kNN search fase 1

)]),((),),(([ kikii ciqpdhciqpdhI

Gruppo 13 M-Chord

q

K=2

δk = distanza K-esimo oggetto

- δk + δk

mchord(q)

23Gruppo 13 M-Chord

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

M-Chord: kNN search fase 2

24Gruppo 13 M-Chord

2 dataset di esempio: Immagini rappresentate da vettori di 45

dimensioniCorpus di testi confrontati con edit distance

Buona scalabilità all’aumentare delle dimensioni della query e del datasetCresce tuttavia numero messaggi scambiati

Possibilità di influire sulle prestazioni agendo su politiche di split dei nodi

Prestazioni

25Gruppo 13 M-Chord

Buoni livelli di parallelismo intraquery (stessa query processata in parallelo) ed interquery (più query contemporanee)

Prestazioni

26Gruppo 13 M-Chord

Costi maggiori per kNN query

Prestazioni

27Gruppo 13 M-Chord

Limiti:Previsto solo inserimento nuovi oggetti, no

eliminazione/aggiornamentoNessun supporto per disconnessione nodiPruning di iDistance da adattare a ambiente

distribuitoUlteriori studi:

Prestazioni su spazi vettoriali a bassa dimensionalità

Replicazione

Sviluppi futuri

GRUPPO 13

Decorte Andrea

Giammarino Giuseppe

Grazie per l’attenzione