# A Dynamic Grid Index for C\(k\)NN Queries on Large-Scale Road Networks with Moving Objects
###### Abstract  
As the Internet of Things devices are deployed on a large scale, location-based services are being increasingly utilized. Among these services, \(k\)NN (\(k\)-nearest neighbor) queries based on road network constraints have gained importance. This study focuses on the CkNN (continuous \(k\)-nearest neighbor) queries for non-uniformly distributed moving objects with large-scale dynamic road network constraints, where CkNN objects are continuously and periodically queried based on their motion evolution. The present C\(k\)NN high-concurrency query under the constraints of a super-large road network faces problems, such as high computational cost and low query efficiency. The aim of this study is to ensure high concurrency nearest neighbor query requests while shortening the query response time and reducing global computation costs. To address this issue, we propose the DVTG-Index (Dynamic V-Tree Double-Layer Grid Index), which intelligently adjusts the index granularity by continuously merging and splitting subgraphs as the objects move, thereby filtering unnecessary vertices. Based on DVTG-Index, we further propose the DVTG-CKNN algorithm to calculate the initial \(k\)NN query and utilize the existing results to speed up the CkNN query. Finally, extensive experiments on real road networks confirm the superior performance of our proposed method, which has significant practical applications in large-scale dynamic road network constraints with non-uniformly distributed moving objects.  
k +
Footnote †: journal: Medical  
in the road network on the performance of neighbor queries. In practical scenarios, the distribution of moving objects in urban environments tends to follow a Zipf distribution; yet, most of the existing studies have not effectively optimized this situation [12].  
To address these challenges, this paper presents a novel index, the DVTG-Index (Dynamic V-Tree Double-Layer Grid Index), and a new algorithm, the DVTG-CRNN. The DVTG-Index introduces two new vertex types, supports dynamic updates of moving objects, facilitates the allocation of computing resources, and facilitates efficient \(k\)NN queries. The index initially partitions the entire graph recursively into several grid subgraphs based on the quadtree structure, and subsequently constructs a new grid index to manage these subgraphs. Active vertices associate moving objects with their corresponding network vertices on the road network, and boundary vertices enable the querying of the distance from a point to other vertices in the grid, enhancing computational efficiency.  
Our contributions are as follows:  
(1) We introduce the DVTG-Index, a scalable, efficient, and adaptable index that accommodates road network datasets and allows for adaptive grid merging and splitting for different regions to obtain the appropriate index granularity and low maintenance cost.  
(2) We propose a robust update strategy that supports the dynamic update of moving objects by associating them with vertices to achieve real-time updates of moving objects. This approach better supports the handling of large mobile objects on large-scale road networks for mobile updates.  
(3) Building on the DVTG-Index, we design a novel \(k\)NN search method that leverages the index's capabilities to compute \(k\)-nearest objects.  
(4) We conduct extensive experiments on four real datasets to evaluate our approach's efficacy. Our experimental results demonstrate that our approach significantly outperforms existing baseline methods.  
This paper is structured as follows: Section 1 presents an overview of the problem, while Section 2 reviews the relevant literature. Section 3 introduces the method overview and relevant definitions in this work. Section 4 details the DVTG-Index's structure and Section 5 outlines an efficient \(k\)NN search algorithm. Section 6 presents our experimental results. Section 7 concludes the paper.