k-Nearest Neighbors Queries in Time-Dependent Road Networks

Abstract

In this article, we study the problem of processing k-nearest neighbors (kNN) queries in road networks considering traffi?c conditions, in particular the case where the speed of moving objects is time-dependent. For instance, given that the user is at a given location at certain time, the query returns the k points of interest (e.g., gas stations) that can be reached in the minimum amount of time. Previous works have proposed solutions to answer kNN queries in road networks where the moving speed in each road is constant. Obviously, these solutions cannot be simply applied to the problem we are interested in. Our approach uses the well-known A∗ search algorithm by applying incremental network expansion and pruning unpromising vertices. We discuss the design and correctness of our algorithm and present experimental results that show the effi?ciency and eff?ectiveness of our solution.