New Query Processing Algorithms for Range and k-NN Search in Spatial Network Databases

摘要

In this paper, we design the architecture of disk-based data structures for spatial network databases (SNDB). Based on this architecture, we propose new query processing algorithms for range search and k nearest neighbors (k-NN) search, depending on the density of point of interests (POIs) in the spatial network. For this, we effectively combine Euclidean restriction and the network expansion techniques according to the density of POIs. In addition, our two query processing algorithms can reduce the computation time of network distance between a pair of nodes and the number of disk I/Os required for accessing nodes by using maintaining the shortest network distances of all the nodes in the spatial network. It is shown that our range query processing algorithm achieves about up to one order of magnitude better performance than the existing range query processing algorithm, such as RER and RNE. In addition, our k-NN query processing algorithm achieves about up to 170～400% performance improvements over the existing network expansion k-NN algorithm, called INE, while it shows about up to one order of magnitude better performance than the existing Euclidean restriction k-NN algorithm, called IER.