TY - CONF
T1 - Distance Oracles for Spatial Networks
T2 - Data Engineering, 2009. ICDE '09. IEEE 25th International Conference on
Y1 - 2009
A1 - Sankaranarayanan,J.
A1 - Samet, Hanan
KW - B-tree;distance
KW - data
KW - database
KW - databases;tree
KW - distance;hash
KW - languages;query
KW - neighbor
KW - network
KW - network;transportation
KW - networks;spatial
KW - networks;well-separated
KW - oracles;epsiv-approximate
KW - pair
KW - processing;region
KW - processing;relational
KW - search;location-based
KW - search;relational
KW - services;real-time
KW - structures;
KW - system;road
KW - table;k-nearest
KW - technique;programming
AB - The popularity of location-based services and the need to do real-time processing on them has led to an interest in performing queries on transportation networks, such as finding shortest paths and finding nearest neighbors. The challenge is that these operations involve the computation of distance along a spatial network rather than "as the crow flies." In many applications an estimate of the distance is sufficient, which can be achieved by use of an oracle. An approximate distance oracle is proposed for spatial networks that exploits the coherence between the spatial position of vertices and the network distance between them. Using this observation, a distance oracle is introduced that is able to obtain the epsiv-approximate network distance between two vertices of the spatial network. The network distance between every pair of vertices in the spatial network is efficiently represented by adapting the well-separated pair technique to spatial networks. Initially, use is made of an epsilon-approximate distance oracle of size O(n/epsiv^{d}) that is capable of retrieving the approximate network distance in O(log n) time using a B-tree. The retrieval time can be theoretically reduced further to O(1) time by proposing another epsiv-approximate distance oracle of size O(n log n/epsiv^{d}) that uses a hash table. Experimental results indicate that the proposed technique is scalable and can be applied to sufficiently large road networks. A 10%-approximate oracle (epsiv = 0.1) on a large network yielded an average error of 0.9% with 90% of the answers making an error of 2% or less and an average retrieval timeof 68 mu seconds. Finally, a strategy for the integration of the distance oracle into any relational database system as well as using it to perform a variety of spatial queries such as region search, k-nearest neighbor search, and spatial joins on spatial networks is discussed.
JA - Data Engineering, 2009. ICDE '09. IEEE 25th International Conference on
M3 - 10.1109/ICDE.2009.53
ER -