# A Dynamic Grid Index for C\(k\)NN Queries on Large-Scale Road Networks with Moving Objects
## 5 DVTG-CNN Query Algorithm
### Continuous \(k\)-Nearest Neighbor Query
This observed performance improvement of the DVTG-Index over benchmark algorithms is attributed to the reduction in the number of updated objects by associating moving objects with active vertices, thereby effectively reducing maintenance costs. As the size of the road network dataset increases, the comparative advantage of the DVTG-Index becomes increasingly pronounced. Conversely, the update of V-Tree and SILC requires a high time cost because, in the update process, they need to frequently traverse all the boundary points in the subgraph to search for the nearest interest point of the vertex. ### Experimental Situation of the DVTG-CkNN Algorithm

The main aim of this paper was to solve the CkNN query problem; therefore, this section is the most important part of our experiment. To evaluate the CkNN query performance of our model, we compared our model with state-of-the-art methods. We evaluated our algorithm by varying the value of \(k\), the number of moving objects, the strategy of moving-object distributions, and the number of consecutive queries. First, we evaluated the effect of varying the value of \(k\) on the performance of our algorithm and other benchmark algorithms for _k_NN queries for datasets BJ, NY, COL, and NW. We changed the value of \(k\) to 1, 3, 5, 10, and 20, respectively, and recorded the overhead time required for related queries. Other experimental parameters presented continuous queries as 3, 10% of all taxis as moving objects in the BJ dataset, 2.5% of the number of vertices as the number of moving objects in the NY, COL and NW datasets, and the moving objects used the ZD distribution strategy. As shown in Figure 14, obviously, as the value of \(k\) increases, the query times of all algorithms increase; the average continuous query time of DVTG-CkNN is the shortest among the three algorithms. Taking the BJ dataset as an example, for \(k=5\), the average single query time of DVTG-CkNN is about 79 us, while the average single query time based on the G*-Tree is about 259 us and the average query time based on V-Tree is about 1132 us. It can be observed that the larger the value of \(k\), the better the performance effect of the DVTG-CkNN algorithm than other algorithms. This is because the number of moving

Figure 12: Index update time of DVTG-Index w.r.t. \(\eta\). Figure 13: Comparison of update time between baseline algorithms and DVTG-Index. objects in our index subgrid can be kept within a dynamic balance range, which reduces the complexity required to expand the search range and shortens the algorithm query time. Then, we evaluated the impact of the number of moving objects on the performance of \(k\)NN queries on BJ and COL datasets. In the BJ dataset, we selected 10%, 30%, 50%, 70%, and 100% of all taxis as moving objects, and in the COL dataset, we, respectively, generated 0.5%, 1.5%, 2.5%, 3.5%, and 5% of the number of vertices as the number of moving objects and set other experimental parameters \(k\) = 5, and the distribution strategy of moving objects adopted the ZD distribution. As shown in Figure 15, we can draw the following conclusions. Firstly, as the number of moving objects increases, the average query overhead time of the three algorithms decreases. This is because the increase in the number of moving objects increases the density of the moving objects in the search grid and reduces the range to be searched. Secondly, the average continuous query time of DVTG-CKNN is the shortest among the three algorithms; even in the case of the high number of moving objects, DVTG-CKNN still has a great advantage. As previously designed, the DVTG-CKNN algorithm is based on the DVTG-Index, which divides the large road network into grids and dynamically merges or splits them according to the number of active vertices in the grid. This keeps the moving objects in different grids in a relatively balanced range, which can significantly improve the efficiency of querying moving objects in large road networks.