Mohammad Kolahdouzan and Cyrus Shahabi
Voronoi-Based K
Nearest Neighbor
Search for Spatial
Network Databases
GRUPPO 13:
Mengoli Dario
Rovatti Fabrizio
Tassoni Davide
Relatore: Mengoli Dario
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
1
Introduzione



Trovare i K Nearest-Neighbors in un Spatial
Network Database
Approcci esistenti sono basati sul:
1.
Calcolo on-line delle distanze tra query e oggetti
(Incremental Network Expansion)
2.
Utilizzo di strutture a indici (M-tree, R-tree)
Gli svantaggi di questi approcci sono:
1.
2.
Performance basse se le entità non sono densamente
distribuite nella rete
Non applicabile per distanze non euclidee (es. distanze di
rete)
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
2
Devo trovare i 5
ristoranti più vicini
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
3
Regole generali

1.
2.
3.
4.
5.
6.
Per ottenere un buon risultato un algoritmo
deve avere alcune caratteristiche:
Incorporare le connettività di rete (es. strade)
Dare risposte efficienti per oggetti in movimento
Scalabile
Essere efficiente nell’inserimento di collegamenti o
nodi nella rete
Indipendente dalla densità dei punti di interesse
Possibilità di query con vincoli su direzione e range
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
4
Voronoi Diagram


Partiziona lo spazio in poligoni disgiunti
Ogni punto appartiene a una sola cella ad
eccezione dei punti di bordo che sono
condivisi tra le celle adiacenti
Punto di
interesse
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
5
Voronoi Diagram


Partiziona lo spazio in poligoni disgiunti
Ogni punto appartiene a una sola cella ad
eccezione dei punti di bordo che sono
condivisi tra le celle adiacenti
Cella di
Voronoi
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
6
Voronoi Diagram


punto dentro
Partiziona lo spazio in poligoniOgni
disgiunti
il
poligono
ha
come nearest
Ogni punto appartiene a una sola
cella point
ad
il generatore del
eccezione dei punti di bordo che
sono
poligono
condivisi tra le celle adiacenti
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
7
Network Voronoi Diagram

Specializzazione di un diagramma di Voronoi
calcolato su una rete (dove gli oggetti sono
posizionati sugli archi che connettono i nodi)


Gli archi possono rappresentare le strade e i nodi i
punti di intersezione tra le strade
Le distanze tra gli oggetti dipendono dalle
connettività della rete e non dalla loro
posizione spaziale (non si considera la
distanza euclidea)
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
8
Network Voronoi Diagram
Nodo
Link
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
9
Network Voronoi Diagram
Punti di
interesse
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
10
Network Voronoi Diagram
Network
Voronoi
Polygon
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
11
Network Voronoi
Diagram
Punto di Bordo
equidistante dai
generatori (punto di
interesse) delle celle
adiacenti
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
12
Approccio utilizzato da VN3
1.
2.
3.
4.
5.
6.
Creazione del Network Voronoi Diagram
Precalcolo delle distanze e memorizzazione
Generazione di un indice spaziale sui poligoni di
Voronoi (R-tree)
Salvataggio per ogni cella dei poligoni adiacenti in
tabelle di lookup
Calcolo del primo NN utilizzando l’indice spaziale
Iterazione per K-1 volte per trovare gli altri NN:
1.
2.
Filter step
Refinement step
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
13
Passo 1 – Network Voronoi
Diagram e Tabelle di Lookup


Generazione dei Network Voronoi Polygons
Precalcolo delle distanze, generazione dell’indice
spaziale (R-tree) e delle tabelle di lookup
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n3
P1
b5
n1
b6
b30
b31
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b1
n2
b4
b37
b17
b19
b2
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
14
Passo 1 – Network Voronoi
Diagram e Tabelle di Lookup


Generazione dei Network Voronoi Polygons
Precalcolo delle distanze, generazione dell’indice
spaziale (R-tree) e delle tabelle di lookup
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n3
P1
b5
n1
b6
b30
b31
P10
b16
P3
b1
n2
b4
b37
b17
b19
b2
b3
P5
b27
P11
b20
b22
P13
b38
b14
b15
b8
b7
P6
b35
P9
1. Adiacenza
poligoni
b36
2. Distanze
precalcolate
b34
b13
3. Punti di
b12 bordo
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
15
1. Distanza tra i punti di bordo con i punti
Passo 1 – Network
Voronoi
interni al poligono (per ogni NVP)
2. Distanza tra i punti di bordo del poligono
Diagram e Tabelle di Lookup


Generazione dei Network Voronoi Polygons
Precalcolo delle distanze, generazione dell’indice
spaziale (R-tree) e delle tabelle di lookup
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n3
P1
b5
n1
b6
b30
b31
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b1
n2
b4
b37
b17
b19
b2
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
16
Passo 1 – Network Voronoi
Diagram e Tabelle di Lookup
b1 P1  dGenerazione
n (b1, P1)
b1
b1
dei Network Voronoi Polygons
Questi
calcoli verranno
eseguiti
n1  dPrecalcolo
n (b1, n1)
delle distanze,
generazione
dell’indice
per ogni singolo poligono.
n2 dspaziale
(b
,
n
)
(R-tree)
e
delle
tabelle di lookup
n
1
2
b1 n 3
b2 …
…
dn (b1, n3)
b
……
39
P12
b21
P4
b23
b1 b2
dnb25(b1, b2 )
…
……
…
b27
b40
P14
b18
b28
35
36
16
n3
n2
b4
P1
b5
34
13
14
1
b24
b29
37
17
b19
b2
b3
P5
b26
P11
b20
b22
P13 ……
…
b38
In questo modo si riduce
b
b
la complessità
spaziale
e
P10
P9
b
b
computazionale
rispetto
al
b
b
P3
caso
in cuib vengano
b
b
b
P8
calcolate
le
distanze
tra
b
P2
q
ogni punto
con btutti gli
b
b
b
b
altri
del grafo
b
P
12
15
n1
8
9
11
33
10
b6
b30
b31
7
b
7
32
P6(punti di bordo<< punti totali)
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
17
Passo 2 – Generazione dell’indice
spaziale e delle tabelle di lookup
1.
Salvataggio in tabelle di lookup dei poligoni adiacenti
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n1
b6
b30
b31
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
18
Passo 2 – Generazione dell’indice
spaziale e delle tabelle di lookup
P1
P2, P1.
P5, P6
3, P4, Salvataggio
P2
P1, P3, P6, P7, P8 , P10
P3
P1, P2, P4, P10, P11
P4
…………
P12
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n1
b6
b30
b31
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b21
b39
in tabelle di lookup dei poligoni adiacenti
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
19
Passo 2 – Generazione dell’indice
spaziale e delle tabelle di lookup
1.
2.
Salvataggio in tabelle di lookup dei poligoni adiacenti
Creazione e salvataggio in memoria dell’ indice spaziale
(R-tree) per i poligoni
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n1
b6
b30
b31
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
20
Passo 2 – Generazione dell’indice
spaziale e delle tabelle di lookup
1.
2.
Salvataggio in tabelle di lookup dei poligoni adiacenti
Creazione e salvataggio in memoria dell’ indice spaziale
(R-tree) per i poligoni
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n1
b6
b30
b31
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
21
Passo 2 – Generazione dell’indice
spaziale e delle tabelle di lookup
1.
2.
Salvataggio in tabelle di lookup dei poligoni adiacenti
Creazione e salvataggio in memoria dell’ indice spaziale
(R-tree) per i poligoni
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n1
b6
b30
b31
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
22
Passo 2 – Generazione dell’indice
spaziale e delle tabelle di lookup
P3
in tabelle di lookup dei poligoni adiacenti
2. 2) Creazione e salvataggio in memoria dell’ indice spaziale
NVP(P
NVP(P3) (R-tree) per i poligoni
…
……
P1
P2
NVP(P
1. 1) Salvataggio
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
n1
b6
b30
b31
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
23
Ricerca 1° Nearest Neighbor


Attraverso l’indice spaziale R-tree si ricava il primo NN
(poligono che contiene q)
Accessi al disco O(logn), dove n sono i generatori
della rete
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
b31
q
n1
b6
b30
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
24
Ricerca 1° Nearest Neighbor


Attraverso l’indice spaziale R-tree si ricava il primo NN
(poligono che contiene q)
Accessi al disco O(logn), dove n sono i generatori
della rete
P1
NVP(P1)
P2
NVP(P2)
P3
…
P12
b21
b39
NVP(P3)
……
P14
b18
b24
b28
b29
b31
q
n1
b6
b30
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
b40
P4
b23
b25
b26
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
25
Passo 3 – Filter Step

Si trovano i poligoni candidati a contenere il secondo
NN attraverso le tabelle di lookup che contengono le
informazione delle adiacenze tra poligoni
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
b31
q
n1
b6
b30
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
26
Proprietà: il numero di celle adiacenti
per ogni poligono sono in media 6
Passo 3 – Filter
Step
Proprietà
: il vicino successivo si trova

necessariamente nei poligoni adiacenti ai
poligoni contenenti i precedenti NN
Si trovano i poligoni candidati a contenere il secondo
NN attraverso le tabelle di lookup che contengono le
spazio di ricerca
informazione delle adiacenzeVincola
tra poligoni
Accessi al disco totali: O(5k+1)O(k)
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
b31
q
n1
b6
b30
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
27
Proprietà: il numero di celle adiacenti
per ogni poligono sono in media 6
Passo 3 – Filter
Step
Proprietà
: il vicino successivo si trova

necessariamente nei poligoni adiacenti ai
poligoni contenenti i precedenti NN
Si trovano i poligoni candidati a contenere il secondo
NN attraverso le tabelle di lookup che contengono le
spazio di ricerca
informazione delle adiacenzeVincola
tra poligoni
Accessi al disco totali: O(5k+1)O(k)
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b29
b31
q
n1
b6
b30
b1
n3
P1
b5
P10
P6
P9
b34
b13
b14
b15
b8
b7
b35
b36
b16
P3
b2
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b12
P8
P2
b9
b11
b10
b32
b33
P7
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
28
Passo 3 – Refinement step


Si calcolano le distanze tra l’insieme
dei candidati (punti di interesse)
trovati nel passo di filter con il punto
query per trovare il prossimo NN.
Per far questo è necessario usare 2
tipologie di distanze:
1.
2.
Query to border computation
Border to border computation
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
29
Passo 3 – Refinement step
Si calcolano le distanze tra l’insieme
dei candidati (punti di interesse)
trovati nel passo di filter con il punto
query per trovare il prossimo NN.
Per far questo è necessario usare 2
tipologie di distanze:



Query to border computation
Distanza tra il punto query e i punti di bordo del poligono
che lo contiene (trovata attraverso le distanze salvate
nelle tabelle di lookup)
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
30
Passo 3 – Refinement step
Si calcolano le distanze tra l’insieme
dei candidati (punti di interesse)
trovati nel passo di filter con il punto
query per trovare il prossimo NN.
Per far questo è necessario usare 2
tipologie di distanze:



Border to border computation
Distanze tra i bordi dei NVP, per far questo si usano le
distanze precalcolate all’inizio e salvate nelle tabelle di
lookup
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
31
Minimum possible network
distance



È la distanza minima tra q e un punto di interesse.
Proprietà: Se (P1; …; Pk) è l’insieme dei primi K
generatori più vicini a q, allora il cammino minimo
tra q e Pk può passare solo attraverso una
combinazione dei confini comuni tra i poligoni
contenenti (P1; …; Pk)
Questo cammino può passare solo attraverso
poligoni il cui generatore è già stato
precedentemente selezionato come NN di q
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
32
Minimum possible network
distance

Se (P1, P2) sono i generatori più vicini a q già etichettati, il
cammino più breve da q a P6 (il prossimo NN) può passare
solo attraverso i confini comuni tra P1/P2 e P6
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b2
P1
b5
b29
b31
b1
q
b16
b15
P6
P9
b34
b13
b12
P8
P2
b8
b7
b35
b36
Primi 2 NN di bq14
n1
b6
b30
P10
P3
n3
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b9
b11
b10
b32
b33
P7
3° NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
33
Minimum possible network
Con VN3 tutte queste
distance
singole distanze sono
già precalcolate
Es: dmpn(q, P6) = min{ d(q, b6)+d(b6, P6) ;
d(q,b7)+d(b7, P6) ; d(q, b8)+d(b8, b9)+d(b8, b9)}
P12
b21
b39
P4
b23
b25
b26
b40
P14
b18
b24
b28
b2
P1
b5
b29
b31
b1
q
b16
b15
P6
P9
b34
b13
b12
P8
P2
b8
b7
b35
b36
Primi 2 NN di bq14
n1
b6
b30
P10
P3
n3
n2
b4
b37
b17
b19
b3
P5
b27
P11
b20
b22
P13
b38
b9
b11
b10
b32
b33
P7
3° NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
34
Trovare il cammino minimo

Al passo precedente si è etichettato il
prossimo NN. Sono proposti due metodi
per definire il cammino minimo:

Network Voronoi Poligon Expansion


Generazione di sottoreti
Distance Computing Optimizazion

Versione ottimizzata del precedente in grado di
ricalcolare le distanze solo se necessario
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
35
Riassumendo….
1.
2.
3.
4.
5.
6.
7.
Precalcolo distanze, indice e tabelle
Ricerca del primo NN attraverso l’indice
Generazione dei possibili candidati per il 2° NN
Calcolo delle minimun distance tra q e i candidati
Determinazione del 2° NN e determinazione del
cammino minimo attraverso Dijkstra
Generazione dei possibili candidati per il 2° NN
………
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
36
Esempio Stradale
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
37
Esempio Stradale
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
38
Inserimento punti di interesse
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
39
Calcolo delle distanze
6,08
6,08
9,06
12,17
11,18
9,06
12,17
10,2
9,06
12,17
10,2
12,17
6,08
6,08
9,06
6,08
6,08
14,32
12,17
6,08
7,07
11,66
16,12
6,08
12,17
12,17
11
7,07
8,25
8,25
12,17
8,25
13,04
14,18
7,07
8,25
11,05
11,05
6,08 6,08
15,03
12,17
12,17
6,08
9,06
6,08
12,17
9,43
14,04
10,2
9,06
13,04
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
40
Generazione del Network
Voronoi Diagram
6,08
6,08
9,06
12,17
11,18
9,06
12,17
10,2
9,06
12,17
10,2
12,17
6,08
6,08
9,06
6,08
12,17
6,08
12,17
12,17
12,17
11
6,08
12,17
6,08
7,07
8,25
8,25
12,17
8,25
13,04
14,18
7,07
8,25
11,05
11,05
6,08 6,08
15,03
14,32
7,07
11,66
16,12
6,08
12,17
6,08
9,06
12,17
12,17
9,43
14,04
10,2
9,06
13,04
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
41
Affinamento dei Network
Voronoi Poligons
6,08
6,08
9,06
12,17
11,18
9,06
12,17
10,2
9,06
12,17
10,2
12,17
6,08
6,08
9,06
6,08
12,17
6,08
12,17
12,17
12,17
11
6,08
12,17
6,08
7,07
8,25
8,25
12,17
8,25
13,04
14,18
7,07
8,25
11,05
11,05
6,08 6,08
15,03
14,32
7,07
11,66
16,12
6,08
12,17
6,08
9,06
12,17
12,17
9,43
14,04
10,2
9,06
13,04
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
42
Pre-calcolo delle distanze
Border-to-Generator
d(P1,b1)
34,82
6,08
6,08
9,06
12,17
12,17
10,2
9,06
12,17
10,2
12,17
6,08
6,08
9,06
12,17
6,08
12,17
12,17
12,17
6,08
6,08
11
12,17
6,08
7,07
8,25
P1
8,25
12,17
8,25
13,04
14,18
7,07
8,25
11,05
11,05
6,08 6,08
15,03
14,32
7,07
11,66
16,12
6,08
12,17
9,43
9,06
12,17
12,17
13,04
14,04
10,2
9,06
6,08
b1
11,18
9,06
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
43
Precalcolo delle distanze
Border-to-Generator
d(P1,b1)
34,82
…………
………
6,08
6,08
9,06
12,17
12,17
10,2
10,2
12,17
9,06
12,17
6,08
12,17
6,08
12,17
b5
6,08
12,17
12,17
12,17
6,08
12,17
6,08
14,32
b7
8,25
P1
8,25
12,17
8,25
13,04
b8
7,07
14,18
7,07
8,25
11,05
11,05
6,08 6,08
15,03
b6
7,07
11,66
16,12
9,06
12,17
12,17
6,08
11
6,08
9,06
9,43
14,04
10,2
b4
13,04
b2
b3
9,06
6,08
b1
11,18
9,06
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
44
Precalcolo delle distanze
Query-to-Border
d(n1,b1)
28,74
…………
………
6,08
6,08
9,06
12,17
12,17
10,2
10,2
12,17
9,06
12,17
6,08
12,17
6,08
6,08
12,17
12,17
12,17
12,17
12,17
6,08
12,17
6,08
8,25
14,32
b7
8,25
13,04
b8
P1
8,25
12,17
15,03
b6
7,07
14,18
7,07
8,25
11,05
11,05
6,08 6,08
n1
b5
7,07
11,66
16,12
9,06
12,17
6,08
11
6,08
9,06
9,43
14,04
10,2
b4
13,04
b2
b3
9,06
6,08
b1
11,18
9,06
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
45
Precalcolo delle distanze
Border-to-Border
…………
………
d(b2,b1)
35,295
…………
………
6,08
6,08
9,06
12,17
12,17
10,2
10,2
12,17
9,06
12,17
6,08
12,17
6,08
12,17
b5
6,08
12,17
12,17
12,17
6,08
12,17
6,08
14,32
b7
8,25
P1
8,25
12,17
8,25
13,04
b8
7,07
14,18
7,07
8,25
11,05
11,05
6,08 6,08
15,03
b6
7,07
11,66
16,12
9,06
12,17
12,17
6,08
11
6,08
9,06
9,43
14,04
10,2
b4
13,04
b2
b3
9,06
6,08
b1
11,18
9,06
7,07
8,25
7,07
8,25
7,07
7,07
7,07
7,07
7,07
7,07
7,07
11,4
11,05
6,08
8,25
6,08 6,08
14,14
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
46
Inserimento del Punto Query
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
47
Primo Nearest-Neighbor
1-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
48
Filter-Step
(Scelta dei candidati)
1-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
49
Refinement-Step
(calcolo delle distanze)
2-NN
1-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
50
Refinement-Step
(cammino minimo)
2-NN
1-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
51
K-esimo Nearest-Neighbor
2-NN
1-NN
3-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
52
K-esimo Nearest-Neighbor
2-NN
1-NN
3-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
53
K-esimo Nearest-Neighbor
2-NN
1-NN
4-NN
3-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
54
K-esimo Nearest-Neighbor
2-NN
1-NN
4-NN
3-NN
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
55
Update Network


Modifiche alla rete comportano cambiamenti non all’intero NVD
ma solo ad alcuni poligoni e questo comporta il ricalcolo solo di
alcune distanze
Aggiunta/rimozione di link/nodi contenuti in un solo NVP



Aggiunta/rimozione di link/nodi contenuti in un più NVP


ricalcolo delle distanze rispetto ai punti di bordo
Eventuale ricalcolo della forma del NVP e delle distanze con i punti
di bordo dei NVP
Rigenerazione dei NVP interessati e di quelli adiacenti
Aggiunta/rimozione di un punto d’interesse

La modifica della rete interesserà solo il poligono che contiene il
punto d’interesse aggiunto/rimosso ed alcuni poligoni adiacenti.
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
56
VN3 vs INE

Il tempo totale di risposta di VN3 è fino ad un ordine di
grandezza in meno rispetto a INE
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
57
VN33havs
un tempo
di calcolo nullo
VN
INE
indipendentemente dalla densità

dei punti, INE peggiora di molto
Il tempo
risposta
VN3 è fino ad un ordine di
se
ho unatotale
bassadidensità
deidipunti
grandezza
di
interessein meno rispetto a INE
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
58
VN3 vs INE

VN3 ha più utilizzo cpu
a causa delle distanze
precalcolate ma ha
meno
accessi
Il tempo totale di risposta di VN3 è fino ad un
ordine
di in
memoria
grandezza in meno rispetto a INE
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
59
Overhead precalcoli


Il numero di precalcoli aumenta quando la densità
dei punti di interesse diminuisce in quanto i NVP
devono ricoprire aree più grandi
Nell’approccio Naive dove si calcolano le distanze
tra tutte le coppie di nodi sono richiesti comunque
3,2 miliardi di precalcoli!!!
Meno densi
Più densi
Overhead dei precalcoli
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
60
Conclusioni


VN3 migliora le prestazioni di INE di un fattore che
varia da 1,5 a 12 a seconda della densità dei punti di
interesse
La fase di Filter Step genera un set di candidati 4
volte più piccolo rispetto approcci tradizionali e varia
di poco a seconda della densità dei punti di interesse



Complessità spaziale degli accessi al disco O(k+log(n))
Implementato utilizzando semplici strutture dati (es:
R-tree, tabelle)
Il precalcolo richiede bassa complessità e temporale
poiché interessa aree più piccole (rispetto all’intera
rete)
Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases
61