Efficient Top-$k$ Nearest Neighbors Search in Dynamic Road Networks

Top-k Nearest Neighbors $(k \text{NN})$ search is a fundamental problem in road networks, which finds the $k$ nearest objects to a query point in the network and has numerous applications in location-based services. Existing solutions mainly focus on static road networks, they fail to address the dynamic nature of real-world road networks. To fill this gap, we propose a new indexing approach that enables efficient query processing while supporting dynamic changes of objects and roads in the road networks. Unlike existing index-based methods that rely on distance indexes, our approach adopts a simple and lightweight $\boldsymbol{k} \mathbf{N N}$ index that stores only the $k$ nearest neighbors for each vertex, making it feasible to maintain the index when the objects or the road network change. To construct the index efficiently, we formulate a generalized $\boldsymbol{k} \mathbf{N} \mathbf{N}$ search problem and develop efficient algorithms by leveraging dynamic programming techniques. We also develop efficient index maintenance algorithms, these algorithms can incrementally and efficiently update the index when the objects or the road network change. We conduct extensive experiments on real-world road networks, which show that our approach outperforms existing solutions by 1-2 orders of magnitude in query processing, index construction, and index size. Furthermore, the result also demonstrates the efficiency of our methods in handling changes in road networks.