One of the most important kinds of queries in Spatial Network Databases to support Location-Based Services is the k-Nearest Neighbors (k-NN) query. In this paper, we propose a novel approach to efficiently and accurately evaluate k-NN queries in spatial network databases using network space diagram. This approach is based on partitioning a large network to small regions, and then precomputing distances both within and across the regions. Our empirical experiments with several random data sets show that our proposed solution outperforms approaches that are based on on-line distance computation by up to one order of magnitude.
