K nearest neighbor search in navigation systems

Article type: Research Article

Authors: Safar, Maytham

Affiliations: Computer Engineering Department, Kuwait University, P.O. Box 5969, Safat 13060, Kuwait. Tel.: +965 4987962; Fax: +965 4839461; Mobile: +965 9361062; E-mail: maytham@eng.kuniv.edu.kw

Abstract: A frequent type of query in a car navigation system is to find the k nearest neighbors (kNN) of a given query object (e.g., car) using the actual road network maps. With road networks (spatial networks), the distances between objects depend on their network connectivity and it is computationally expensive to compute the distances (e.g., shortest paths) between objects. In this paper, we propose a novel approach to efficiently and accurately evaluate kNN queries in a mobile information system that uses spatial network databases. The approach uses first order Voronoi diagram and Dijkstra's algorithm. This approach is based on partitioning a large network to small Voronoi regions, and then pre-computing distances across the regions. By performing across the network computation for only the border points of the neighboring regions, we avoid global pre-computation between every object-pair. Our empirical experiments with real-world data sets show that our proposed solution outperforms approaches that are based on on-line distance computation by up to one order of magnitude. In addition, our approach has better response times than approaches that are based on pre-computation.

Keywords: Navigation system, GPS, shortest path, network distance, Dijsktra's Algorithm, GIS queries, spatial network

Journal: Mobile Information Systems, vol. 1, no. 3, pp. 207-224, 2005