Index Land Surface for Efficient kNN Query

Gruppo 2Riccardo MasciaRoberto Saluto

RelatoreRoberto Saluto

Cyrus Shahabi Lu-An Tang Songhua Xing

ObiettiviNecessità di trovare siti più vicini sulla superficie terrestre soprattutto nei casi di aree non pianeggiantiRisolvere query in 3-D chiamate Surface k Nearest Neighbor poiché sono effettuate su database geospaziali 3-D che tengono conto dell’altimetria della superficieProgettare 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 daTC(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 sitiProprietà: per ogni punto query q ϵ TC(pi), il Nearest Neighbor di q, calcolato con la distanza di superficie, è piQuindi il TSI è l’insieme delle Tight Cell generate da PTSI(P) = {TC(p1)……TC(Pm)}

Loose Surface IndexPer computare lo spazio non coperto dalle tight cell si introduce un nuovo indiceIl 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 superficieDefiniamo 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 IndexDato 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’indiceCollegando 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 triangoloSi generano i diagrammi di Voronoi per i siti nello spazio euclideo e si individuano i triangoli che sono attraversati dal bordo delle celle di VoronoiDato 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 bordoSe non lo sono, si cercano dei triangoli adiacenti all’interno della cella di Voronoi per determinarliNei 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-TreeVengono 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-TreeQuesta 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 LC(r) containing p;

2. p.neighbor ←LC(r)’s neighbor;3. compute TC(p) and LC (p);4. for each site pi in p.neighbor5. update LC(pj)’s edges

according to TC(p);6. update TC(pj)’s edges

according to LC(p);7. insert p into I;8. return I;

Algoritmo di inserimento nel SIR-Tree

Surface Index R-Tree

Surface Nearest Neighbor QueryRicerca in profondità

nel SIR-Tree del nodo contente il punto di queryRestituzione 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 N1Lo 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 N4Non 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 q2Lo 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 candidatiCalcoliamo 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 for9. 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 query2. Effettivo percorso più breve di superficie 3. Risultati incrementali