1 G RUPPO 12 Luca Druda Francesco Flor Daniele Palossi P ARALLEL D ISTRIBUTED P ROCESSING OF C...

1

GRUPPO 12

Luca DrudaFrancesco FlorDaniele Palossi

PARALLEL DISTRIBUTED

PROCESSING OF CONSTRAINED

SKYLINE QUERIES BY FILTERING

Bin Cui, Hua Lu, Quanqing Xu, Lijiang Chen, Yafei Dai, Yongluan Zhou

Agenda

1- Descrizione del problema

2- Proposta di soluzione e descrizione PaDSkyline

3- Partizionamento gruppi

4- Piano d'esecuzione intragruppo

5- Punti di filtraggio multipli

6- Analisi dei risultati sperimentali

7- Conclusioni

Descrizione

Query skyline distribuite

Efficienza nella trasmissione dei dati sulla rete

Utilizzo di rete ad alta disponibilità (rete internet)

Comparative shopping

Altri esempi …

Ricerca di Hotel da parte di un turista attraverso determinate preferenze

Ricerca dei migliori titoli azionari su diverse borse

Scenari

La maggior parte dei lavori su query skyline finora considerano storage centralizzati

Inoltre si ha spesso sovrapposizione dei dati su storage multipli e distribuiti

Altri lavori infine si sono soffermati su esecuzione distribuita di query ed elaborazione finale di un server centrale.

6

query

risultati skyline ridotti

risultati skyline completi

Scenario

7

Query

query



Scenario

8

query



Scenario

9

Skyline resultsquery



Scenario

10

query



Scenario

11

Query

query



Scenario alternativo

12

query




13

Skyline results


query



14

Query

query




15

query




16

Skyline results

query




17

query




Problemi

Le strategie precedentemente menzionate incorrevano in alcuni problemi:

Overhead

Traffico elevato: trasmissione di dati non necessari sulla rete

Tempi di risposta elevati

Agenda







7- Conclusioni

Obiettivi

Minimizzare il tempo di risposta per Skyline queries distribuite (utilizzo di punti di filtraggio multipli)

Sfruttamento della capacità computazionale dei vari nodi connessi tramite cavo (calcolo parallelo)

Riduzione del traffico sulla rete attraverso tecniche di filtraggio dei risultati locali ai vari nodi

Non essere legati a particolari reti o politiche di gestione degli overlay (es. CAN, BATON, MANET)

Partizionamento

Definizione delpiano di esecuzione

intra-gruppo

Esecuzione dellaquery intra-gruppo

con filtraggio

Presentazioneimmediata dei

risultati

Processo di soluzione

Algorithm PaDSkyline (S, C)

Input S is the set of data sites C is the set of constraints

in the skyline query

Output the constrained skyline

1. ∏s=icmpPartition (S, C)

2. for each group Sgi∈∏

s in parallel

3. Send <C,Sorg,g

i,plan> to Sg

i

4. repeat

5. receive result reply from a Sgi

6. report Sgi.result

7. until all group heads have replied

Partizionamento

Esecuzione intragruppo

Algoritmo PaDSkyline

26

query



PaDSkyline

27

query




28

query




29

query




Agenda







7- Conclusioni

Minimum Bounding box Region – MBR & Reduced MBR - rMBR

D1

D2

1) Creazione MBR

3) Introduzione constraint x<D1<y

2) Introduzione constraint D2>z

4) Creazione rMBR

rMBR i . min.DR∩ rMBR j=∅ ∧ rMBR j .min.DR∩ rMBR i=∅

LEMMA: legame tra incomparabilità e dominanzaSe due siti S

i e S

j sono incomparabili rispetto ai vincoli della query

per ogni coppia di punti pi ϵ rMBR

i e p

j ϵ rMBR

j non è verificata la

dominanza di pi su p

j e viceversa

Definizione di incomparabilità :Due sorgenti di dati (siti) S

i e S

j sono incomparabili rispetto ai

vincoli della query se e solo se la regione dominante dell'angolo minimo del rMBR di S

i non interseca l'rMBR di S

j e viceversa:

Partizionamento

Partizionamento

rMBRi

rMBRj

rMBRi

rMBRj

rMBRi

rMBRj

rMBRj.min.DR rMBRi

rMBRj

rMBRi.min.DR rMBRi.min.DR

rMBRj.min.DR

Incomparabili Comparabili

Algorithm icmpPartition(S, C)

Input: S is the set of data sites

C is the set of constraints in the skyline query

Output: an incomparable partition of S

// Adjust MBRs and prune unqualified sites

1. for each Ki ∈ S

2. rMBRi = MBRi ∩ C;

3. if (rMBRi == Ø) S = S − {Ki};

// Compute the independent partition of all relevant sites

4. ΠS = {{S1}}; // S1 is the current 1st element in S

5. for each Ki ∈ S − {S1}

6. Si' = Ø;

7. for each Si ∈ ΠS

8. if (∃ Kj ∈ Si s.t. Kj and Ki are not incomparable)

9. ΠS = ΠS − {Si}; Si' = Si' ∪ Si;

10. ΠS = ΠS {{Ki} Si'}∪ ∪

icmpPartition

Esempio di riferimento

S = { A , B , C , D , E , F , G }

35

icmpPartitionDi seguito viene mostrato come l'icmpPartition genera le partizioni:

4. ΠS = {{S1}}; // S1 is the current 1st element in S5. for each Ki ∈ S − {S1}6. Si' = Ø;7. for each Si ∈ ΠS8. if (∃ Kj ∈ Si s.t. Kj and Ki are not incomparable)9. ΠS = ΠS − {Si}; Si' = Si' ∪ Si;10. ΠS = ΠS {{Ki} Si'}∪ ∪


Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

A

EG

DB

F

C

36

Di seguito viene mostrato come l'icmpPartition genera le partizioni:



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

A

EG

DB

F

C

icmpPartition

37



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

B

A

EG

DB

F

C


icmpPartition

38



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

B

A

EG

DB

F

C


icmpPartition

39



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

B

A

EG

DB

F

C

Si


icmpPartition

40



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

B

A

A

EG

DB

F

C

Si

INCOMPARABILI


icmpPartition

41



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

B

A

A

EG

DB

F

C


icmpPartition

42



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

B

A

A

EG

DB

F

C


icmpPartition

43



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

B

A

A

EG

DB

F

C

A DB

F

C

AAS1

S2

Πs


icmpPartition

44



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

C

A

EG

DB

F

C


icmpPartition

45



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

C

A

EG

DB

F

C


icmpPartition

46



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

C

A

EG

DB

F

C


icmpPartition

47



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

C

A

EG

DB

F

C

A Si


icmpPartition

48



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

C

A

A

EG

DB

F

C

INCOMPARABILI

AASi


icmpPartition

49



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

C

A

EG

DB

F

C

AA Si


icmpPartition

50



Ki

Πs { {A},{B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

Ø

C

B

A

EG

DB

F

C

AA Si

COMPARABILI!


icmpPartition

51



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

{B}

C

B

A

EG

DB

F

C

AA Si


icmpPartition

52



Ki

Πs { {A} }

Si'

S = { A , B , C , D , E , F , G }

Kj

{B}

C

B

A

EG

DB

F

C

AA


icmpPartition

53



Ki

Πs { {A} , {C,B} }

Si'

S = { A , B , C , D , E , F , G }

Kj

{B}

C

A

EG

DB

F

C

AAS1

S2

Πs


icmpPartition

Continuando ad iterare fino a che non vengono esaminati tutti gli elementi di “S”, come è facile intuire si otterrà il seguente partizionamento:

Πs = { {A} , {E,D,C,B} , {G,F} }

E

G

DB

FC

AS1

S2

Πs

S3

icmpPartition

Agenda







7- Conclusioni

Dopo aver ottenuto i gruppi si passa alla definizione del piano di esecuzione della query all'interno degli stessi.

Un specifico piano è necessario in quanto i siti all'interno di un gruppo sono comparabili e quindi l'esecuzione della query su uno di essi dipende da o influenza un altro sito.

Il piano di esecuzione può essere realizzato e definito in base a diversi criteri che ne determinano la complessità e l'efficienza.

Esecuzione intragruppo

Metodi di definizione del piano di esecuzione

Grafo con Distanza euclidea

Grafo ottimo Grafo semplificato

PRO Permette di definire buoni piani di esecuzione.

Sfrutta pienamente la parallelizzazione interna al gruppo.

Rappresenta il miglior compromesso tra ottimalità e complessità

CONTRO Non riesce a sfruttare i parallelismi interni e genera solo piani sequenziali

Richiede eccessiva complessità di calcolo

Non sfrutta al meglio la parallelizzazione intra-gruppo.

Creazione del grafo semplificato

{B,C,D,E}

B

C

D

E

B

C

D

EB

All'inizio si ha solo B, perciò lo si trasforma in un nodo


{B,C,D,E}

B

C

D

E

C

B

Successivamente si crea il nodo C e lo si compara con B. Essendo comparabile, C diventa la root dell'albero


{B,C,D,E}

B

C

D

EC

B

D

Successivamente si crea il nodo D e lo si compara con C. Essendo comparabile, D diventa la root dell'albero


{B,C,D,E}

B

C

D

E

C

B

E

D

Successivamente si crea il nodo E e lo si compara con D. Essendo comparabile, E diventa la root dell'albero e l'algoritmo termina non essendoci più altri datasets in lista


{B,C,D,E}

B

C

D

E

C

B

E

DA questo punto il grafo viene rovesciato per avere la vera sequenza di esecuzione della query intragruppo. E quindi diviene il capogruppo.

NOTA: in alcuni casi si possono avere ramificazioni che aumentano il parallelismo, introducendolo anche all'interno del gruppo.


{B,C,D,E}

All'interno di ogni gruppo la query viene elaborata secondo un preciso ordine dai vari siti.

Il capogruppo riceve la query, la elabora e la passa al sito successivo insieme al piano di esecuzione, al suo identificativo e ai punti di filtraggio aggiornati con gli ultimi risultati.

I vari siti si passano la query e rispondono tutti al capogruppo tramite l'identificativo che viene fornito.

Intra-group Algorithm

Sg

S1

S3S2

Sor

g

Sor

g

= richiedente

Sg = headgroup

S1 = sito

NOTA: al fine di ottimizzare i tempi di risposta dei singoli siti si utilizza anche una precomputazione locale al sito stesso, effettuata sull'intero dataset.

Intra-group

Sg

S1

S3S2

Sor

g⟨C , Sorg , Sg . plan⟩

Intra-group

Sor

g

= richiedente

Sg = headgroup

S1 = sito


Sg

S1

S3S2

⟨C , S g , plan' , F c ⟩

Sor


Intra-group

Sor

g

= richiedente

Sg = headgroup

S1 = sito


Sg

S1

S3S2

⟨C , S g , plan' , F c ⟩

⟨C , S g , plan' , F c ⟩⟨C , S g , plan' , F c ⟩

Sor


Intra-group

Sor

g

= richiedente

Sg = headgroup

S1 = sito


Sg

S1

S3S2

⟨C , S g , plan' , F c ⟩


R1

Sor


Intra-group

Sor

g

= richiedente

Sg = headgroup

S1 = sito


Sg

S1

S3S2

⟨C , S g , plan' , F c ⟩


R2R3

R1

Sor


Intra-group

Sor

g

= richiedente

Sg = headgroup

S1 = sito


Sg

S1

S3S2

⟨C , S g , plan' , F c ⟩


R2R3

R1

Sor

g

Rg

⟨C , Sorg , Sg . plan⟩

Intra-group

Sor

g

= richiedente

Sg = headgroup

S1 = sito


Agenda







7- Conclusioni

Il tempo di risposta alla query è influenzato dal numero di byte che viaggiano nella rete.

Avere a disposizione punti dominanti prima dell'esecuzione della query consente di effettuare un filtraggio locale finalizzato ad eliminare un maggior numero di falsi positivi.

Una riduzione del numero di risultati ottenuti comporta un miglioramento del tempo di risposta

Filtering for dummies :-)

Punti di filtraggio multipli

Quanti e quali punti scegliamo?

Risultati skyline dataset A

Risultati skyline dataset B

La query sul dataset A fornisce i punti di filtraggio alla query su B.

Si nota come qualsiasi punto che non sia p, non fornisca miglioramenti nel restringimento del risultato finale.

Scegliere in questo caso più punti di filtraggio è controproducente.

p


Quanti e quali punti scegliamo?

Dato quindi l'insieme dei punti skyline, esistono diversi sistemi per calcolarne il subset che costituirà i punti di filtraggio:

1.Una prima scelta può essere quella di scegliere questi punti in un modo casuale (Random approach). In questo modo il calcolo non è sempre esatto, tuttavia permette di elaborare il subset in modo molto performante.

2.Una seconda scelta più oculata potrebbe invece osservare la qualità di un punto rispetto ad un altro sulla base di quanta porzione dello spazio domina. A tale scopo introduciamo un nuovo parametro, il VDR.


Dx

Dz

Dy

P

Px

Pz

Py

c

P

Vincolo : Dz < c

Volume=c−P z ⋅max D x−P x ⋅max D y−P y

VDR: Volume of Dominating Region

Data Region 1

Data Region 2 Data Region 3

VDRfused = VDRDRegion1VDR DRegion2VDR DRegion3−−VDRDRegion1∩DRegion2−VDR DRegion1∩DRegion3 −VDRDRegion2∩DRegion3VDRDRegion1∩DRegion2∩DRegion3

Applicando il principio di inclusione – esclusione :

a

bc

Calcolo del fused VDR

Il Maximal Sum of VDRs fa l'assunzione che vi siano poche intersezioni e procede al calcolo dei diversi punti scegliendo quelli che hanno i volumi dominanti più grandi.

Il metodo migliora l'efficacia tanto più l'intersezione è piccola

Oltre a calcolare i volumi è necessario avere a disposizione un ordinamento sulla base della dimensione di questi ultimi.

MaxSum

D1

D2

Scelta di due punti di filtraggio da tre punti di skyline

a

b

c

Esempio MaxSum

D1

D2


a

b

c

Area massimale

Esempio MaxSum

D1

D2


a

b

c

Esempio di fallimento MaxSum

Area dominata dall'algoritmo MaxSum

D1

D2

a

b

c


D1

Area dominante ottima

D2

a

b

c


MaxSum semplifica il calcolo del Fused VDR ignorando le intersezioni fra le regioni.

MaxDist invece tiene conto della topologia tra i punti.L'idea alla base di questa seconda euristica è che tanto maggiore è la distanza tra due punti, tanto minore sarà la probabilità che la dimensione dell'intersezione delle loro regioni dominanti sia grande.

Massimizzare la somma delle distanze tra i punti

MaxDist

D1

Area dominante ottima

D2

a

b

c

Uso del MaxDist sull'esempio precedente

D1D1

D2

a

b

c

Esempio di fallimento MaxDist

D1D1

D2D2

a

b

c


D1D1

D2

a

b

c


Agenda







7- Conclusioni

I parametri di valutazione utilizzati nell'analisi dei risultati sperimentali sono:

DRR: Data Reduction RateIndica la percentuale di punti, relativi alla risposta, non inviati al capogruppo perché inutili.

Response TimeIndica il tempo che intercorre tra l'invio della query da parte di Sorg e la ricezione finale dei risultati

PrecisionRappresenta la qualità dei punti di skyline che vengono restituiti a un sito (capogruppo o originatore della query).

Risultati sperimentali

DRR=∑

i=1,i≠org

m

∣unredSK i∣−∣redSK i∣−K i

∑i=1, i≠org

m

∣unredSK i∣

Il data reduction rate viene calcolato come la proporzione tra i risultati skyline omessi (dominati dai punti di filtraggio) e i risultati totali.

L'ottimo è ovviamente il caso con DRR=1 in cui i punti di filtraggio consentono di eliminare tutti i risultati di un sito o potenzialmente di non eseguire affatto la query su tale sito.

DRR: Data Reduction Rate

P=∣A∣∣B∣

La precisione viene calcolata come il rapporto tra i punti che un capogruppo ritorna all'originatore della query e quelli che gli giungono dai siti figli.

Una precisione di valore 1 indica che il capogruppo non dovrà fare alcuna elaborazione dei risultati ottenuti prima di inviarli a S

org perchè il filtraggio ha già eliminato duplicati e falsi positivi.

Una precisione vicina allo zero indica che i risultati pervenuti al capogruppo non sono ottimi e quindi è necessaria elaborazione locale.

A : numero di punti restituiti a Sorg

B : somma dei punti giunti ai diversi Sg

Precision

I seguenti risultati sono relativi ad un dataset reale (NBA Players)Le metodologie esaminate sono:

Naive PaDSkyline con le euristiche:

MaxSum MaxDist Random


I risultati successivi evidenziano che un elevato numero di punti di filtraggio non contribuisce a aumentare l'efficienza.


I grafici seguenti intendono valutare le performance al variare delle dimensioni dei siti. I risultati mostrano come al crescere delle dimensioni dei siti le euristiche scelte impattino maggiormente sulle performance: aumento di precisione e miglioramento del tempo di risposta.


Agenda







7- Conclusioni

I risultati sperimentali dimostrano come la proposta sia efficiente nell'elaborazione distribuita della query (improvement computazionale).

Inoltre l'algoritmo risulta scalabile sia al variare delle dimensioni (attributi) del dataset sia al variare del numero di nodi nella rete.

Conclusioni

1 G RUPPO 12 Luca Druda Francesco Flor Daniele Palossi P ARALLEL D ISTRIBUTED P ROCESSING OF C...

Documents

Transcript of 1 G RUPPO 12 Luca Druda Francesco Flor Daniele Palossi P ARALLEL D ISTRIBUTED P ROCESSING OF C...