Cyrus Shahabi
Lu-An Tang
Songhua Xing
Index Land Surface for
Efficient kNN Query
Gruppo 2
Riccardo Mascia
Roberto Saluto
Relatore
Roberto Saluto
Obiettivi
Necessità di trovare siti più vicini sulla
superficie terrestre soprattutto nei casi di
aree non pianeggianti
Risolvere query in 3-D chiamate Surface k
Nearest Neighbor poiché sono effettuate su
database geospaziali 3-D che tengono conto
dell’altimetria della superficie
Progettare una struttura indicizzata su
database geospaziali del mondo reale per
migliorare velocità e accuratezza delle
risposte alle query skNN
Query Surface k Nearest Neighbor
Risolvere queste query significa affrontare
tre problematiche:
1. Gestione di enormi database contenenti la
rappresentazione 3D del modello della
superficie
2. Sostenere la complessità di calcolo per la
ricerca del più breve percorso di superficie
3. Mancanza di strutture indicizzate della
superficie per un’esecuzione più rapida di
queste query
Approcci Esistenti per query skNN
I principali approcci attuali per questo tipo di
query sono:
1. Range Ranking che fornisce risposte in modo
rapido ma approssimativo
2. CH Algorithm che restituisce risposte precise
ma è lento
Concetti di base (1)
Per la tecnica
1. Distanza di superficie
(Ds) : è la lunghezza del
percorso più breve che
collega due punti sulla
superficie
2. Distanza Euclidea in 3D
(De) : è la linea retta che
collega due punti
Concetti di base (2)
3. Distanza di rete (Dn): Dato un
modello di superfice costruito
attraverso TIN (Triangolar
Irregular Network), la
distanza di rete è la
lunghezza del percorso più
breve tra due punti,
attraverso i lati dei triangoli .
TIN è una struttura dati
vettoriale basata su triangoli
con maglia irregolare , capace
di fornire un’elevata
risoluzione solo dove questa
è necessaria
Concetti di base (3)
Tra due punti sulla superficie si ha:
De ≤ Ds ≤ Dn
quindi De e Dn possono essere considerati
rispettivamente il limite inferiore e il limite
superiore per Ds
Concetti di base (4)
Dato un poliedro, il
percorso più breve tra
due punti sulla sua
superficie è definito
dall’algoritmo CH, come
la lunghezza della più
breve linea retta che
collega i due punti,
dopo aver dispiegato su
un piano tutte le sue
facce in diversi ordini
Concetti di base (5)
Un diagramma di Voronoi divide uno spazio
in celle disgiunte a seconda dei siti. Per ogni
punto della query che cade all'interno di
una cella, il punto più vicino è il generatore
della cella (il sito corrispondente a quella
cella). Il confine comune tra due celle di
Voronoi vicine è la bisettrice perpendicolare
della linea che collega i due siti
corrispondenti
Tight Surface Index
Gli autori propongono due
schemi di indicizzazione
spaziale della superficie:
Il primo è il Tight Surface
Index (TSI) che definisce
uno spazio stretto intorno
ad un sito p, nel quale ad
ogni punto è garantito di
avere p come Nearest
Neighbor per distanza di
superficie
Tight Surface Index
Definiamo Tight Cell come una zona
poligonale attorno ad un sito pi definito da
TC(pi)={q : q ϵ T, Dn(pi,q)<De (pj,q)
(∀ pj ϵ P, pj ≠ pi)}
dove pi è chiamato generatore di TC(pi), T è il
modello della superficie e P l’insieme dei siti
Proprietà: per ogni punto query q ϵ TC(pi), il
Nearest Neighbor di q, calcolato con la
distanza di superficie, è pi
Quindi il TSI è l’insieme delle Tight Cell
generate da P
TSI(P) = {TC(p1)……TC(Pm)}
Loose Surface Index
Per computare lo spazio non coperto dalle tight
cell si introduce un nuovo indice
Il Loose Surface Index (LSI) definisce uno spazio
ampio intorno ad un sito p, all’esterno del
quale ad ogni punto è garantito di non avere p
come suo vicino più prossimo per distanza di
superficie
Definiamo Loose Cell come zona poligonale
attorno ad un sito pi definito da
LC(pi)={q:q ϵT, De(pi,q)<Dn (pj,q)
(∀ pj ϵ P, pj ≠ pi)}
dove pi è chiamato generatore di LC(pi), T è il
modello della superficie e P l’insieme dei siti
Loose Surface Index
La Loose Cell di ogni sito contiene
completamente la Tight Cell
Al sito p è garantito di non essere il Nearest
Neighbor di q se q è esterno a LC(pi)
Quindi il LSI è l’insieme delle Loose Cell
generate da P.
LSI(P) = {LC(p1)……LC(Pm)}
Dato che la TSI e LSI sono generati per lo
stesso insieme di siti P, le tight cell e le loose
cell devono avere bordi in comune; più in
particolare, tutti i confini delle tight cell sono
anche i bordi delle loose cell
Loose Surface Index
Dato un sito p, i vicini di p sono definiti come
NL(p)={pi | TC(pi) ed LC(p) hanno confini in
comune}
A differenza delle tight cell, le loose cell
possono avere delle zone di sovrapposizione ,
dette aree non classificate
Loose Surface Index
Se pi è il punto più vicino di q, allora il più
breve percorso di superficie da q a pi è
all'interno della Loose Cell LC(pi).
Costruzione Naïve dell’indice
Illustriamo l’approccio di base per la
costruzione del TSI
Costruzione Naïve dell’indice
Costruzione Naïve dell’indice
I punti di transizione devono essere sui bordi
e la loro distanza di rete da p è uguale al
minimo delle sue distanze euclidee da tutti gli
altri siti
Costruzione Naïve dell’indice
Collegando tutti i punti di transizione
attraverso la superficie dei triangoli si
generano i bordi delle tight cell
Costruzione veloce dell’indice
La generazione dell’indice appena proposta è
significativamente complessa perché deve
esaminare i vertici di ogni triangolo
Si generano i diagrammi di Voronoi per i siti
nello spazio euclideo e si individuano i
triangoli che sono attraversati dal bordo delle
celle di Voronoi
Dato un qualsiasi sito p, la sua tight cell si
trova dentro la sua cella di Voronoi
Costruzione veloce dell’indice
I triangoli appena individuati saranno ora
esaminati per determinare se sono triangoli di
bordo
Se non lo sono, si cercano dei triangoli
adiacenti all’interno della cella di Voronoi per
determinarli
Nei triangoli di bordo si determineranno i
punti transizione come per l’approccio naïve
e quindi si determinerà il bordo della tight
cell
Costruzione veloce dell’indice
Per la costruzione delle Loose Cell
l’algoritmo è uguale, tranne nel caso dei
triangoli che non sono di bordo per il quale
vengono scelti i triangoli, vicini al triangolo
non di bordo, meno prossimi al sito
Surface Index R-Tree
Gli indici TSI e LSI hanno una complessità tale
da non poter essere memorizzate in strutture
ad albero classiche come gli R-Tree
Vengono allora create delle strutture ad
albero basate su R-Tree che possano
incorporare questi indici, tali strutture sono
chiamate Surface Index R-Tree
Surface Index R-Tree
Questa struttura
permette di
memorizzare nei nodi
foglia, oltre al sito,
anche i puntatori alla
lista dei vertici delle TC
e LC.
L’algoritmo oltre ai
puntatori memorizza
la lista dei siti vicini, il
cui numero è costante
e limitato per tutti i siti
(da esperimenti risulta
sempre minore di 10)
Surface Index R-Tree
Il SIR-tree è costruito una sola volta per ogni
luogo e permette le operazioni di
inserimento, cancellazione e aggiornamento
1. locate p in I, find out the loose cell
2.
3.
4.
5.
6.
7.
8.
LC(r) containing p;
p.neighbor ←LC(r)’s neighbor;
compute TC(p) and LC (p);
for each site pi in p.neighbor
update LC(pj)’s edges according
to TC(p);
update TC(pj)’s edges according
to LC(p);
insert p into I;
return I;
Algoritmo di inserimento nel SIR-Tree
Surface Index R-Tree
Surface Nearest Neighbor Query
Ricerca in profondità nel
SIR-Tree del nodo
contente il punto di
query
Restituzione del
generatore della tight
cell che contiene q,
altrimenti :
Restituzione dei
generatori delle loose
cell e attraverso il
calcolo del percorso più
breve individuazione del
vicino più prossimo
Surface Nearest Neighbor Query
Per esempio, se cerchiamo
il punto di query q1,
Lo troviamo nel SIR-Tree
nel nodo N1
Verifichiamo se é
contenuto in una delle
tight cell dei nodi figli di
N1
Lo individuiamo in TC(p2) e
restituiamo p2 come
Nearest Neighbor
Surface Nearest Neighbor Query
Se invece cerchiamo q2,
lo troviamo nel SIR-Tree
in N4
Cerchiamo se è
contenuto nelle tight cell
dei nodi figli di N4
Non trovandolo lo
cerchiamo nelle loose cell
Lo individuiamo nella
loose cell di p3
Surface Nearest Neighbor Query
Controlliamo i vicini in
NL(p3)
Controlliamo quale loose
cell dei vicini contiene q2
Lo individuiamo in LC(p6).
Calcoliamo le distanze di
superficie Ds(q2,p3) e
Ds(q2,p6)
La distanza di superficie
minore ci restituisce il
Nearest Neighbor
Ds(q2,p6)
Ds(q2,p3)
Surface K Nearest Neighbor
Query
Aggiunta delle loose cell di tutti i vicini del
sito più prossimo determinato come nella
Nearest Neighbor Query alla coda di siti
candidati
Calcoliamo le distanze superficiale di ogni
sito, tra il sito candidato e il punto di query
nell’area definita dall’unione della loose cell
del sito con l’area formata dalle loose cell dei
siti inseriti nella serie dei vicini prossimi già
determinati (G)
Il sito con distanza minima sarà indicato
come successivo vicino e inserito nella serie
G, per ogni iterazione dell’algoritmo fino al
raggiungimento dei k desiderati
Surface k Nearest Neighbor
Query
1. p←Nearest Neighbor Query(I, q, T);
2. add p to kNN set G;
3. initialize minimum heap H;
4. while(G.size < k)
5.
for each neighbor site pi of G;
6.
unfold LC(G) U LC(pi) to
compute surface distance;
7.
add pi to H;
8.
end for
9.
p←deheap H;
10.
add p to G;
11.end while;
12.return G;
Calcolo del DS per un candidato
Analisi delle Prestazioni
Si è confrontato l’algoritmo proposto con
quelli preesistenti per le kNN Query su un
database geospaziale standard fornito dal
U.S.Geological Survey su queste due superfici
Efficienza
Come si deduce dai grafici l’algoritmo
proposto è più veloce e meno oneroso in
termini di operazioni di I/O
d è la densità di siti sul modello della superficie
Accuratezza
Dai grafici si deduce che l’algoritmo proposto
anche all’aumentare di k rimane preciso al
pari del CH Algorithm
Conclusioni
Si può concludere che questo algoritmo
garantisce:
1. Risposte precise e rapide alle skNN query
2. Effettivo percorso più breve di superficie
3. Risultati incrementali