Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases Mohammad R. Kolahdouzan and Cyrus Shahabi   View Paper (PDF)   Return to RESEARCH SESSION 21:SIMILARITY SEARCH AND APPLICATIONS Abstract A frequent type of query in spatial networks (e.g., road networks)is to find the K nearest neighbors (KNN) of a given query object. With these 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 spatial network databases using first order Voronoi diagram. This approach is based on partitioning a large network to small Voronoi regions, and then pre-computing distances both within and across the regions. By localizing the pre-computation within the regions, we save on both storage and computation and by performing across-the-network computation for only the border points of the neighboring regions, we avoid global pre-computation between every node-pair. Our empirical experiments with several 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, and provides a factor of four improvement in the selectivity of the filter step as compared to the index-based approaches. ©2005 Association for Computing Machinery