Improving Performance of Spatial Network Queries

Spatial network queries, for example KNN or range, operate on systems where objects are constrained to locations on a network. Current spatial network query algorithms rely on forms of network traversal which have a high complexity proportional to the size of the network making, them poor for large real-world networks. In this thesis, an alternative method of approximating the results of spatial network queries with a high level of accuracy is introduced. Distances between network points are stored in an M-Tree index, a balanced tree index where metric distance determines data ordering. The M-Tree uses the chessboard metric on network points embedded in a higher dimensional space using tRNE. Using the M-Tree both KNN and range queries are computed more efficiently than network traversal. Error rates of the M-Tree are low, with accuracies of 97% possible on KNN queries and perfect accuracy with 2% extra results on range queries.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Year

2006

Author dc:creator

• Ioup, Elias

Contributors dc:contributor

• Abdelguerfi, Mahdi
• Tu, Shengru
• Chaudry, Nauman

Repository record dc:identifier

https://scholarworks.uno.edu/td/406

OAI identifier oai:identifier

oai:scholarworks.uno.edu:td-1427