# 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
Then, we evaluated the impact of different distribution strategies of moving objects on the performance of the \(k\)NN query using three distribution strategies to generate the number of moving objects for datasets BJ and NW, respectively. Experiment with other parameters \(k\) = 5, and the number of moving objects is 2.5% of the number of vertices in the dataset. As shown in Figure 16, we can draw the following conclusions. First, under the three distribution strategies of RD, ND, and ZD, the overhead times of the three query algorithms increases in turn. The uneven distribution of moving objects under the three distribution strategies gradually increases, and the search range gradually increases, requiring more overhead time. Secondly, the average single query time and average continuous query time of DVTG-CKNN are the shortest among the three algorithms. Especially under the ZD

Figure 14: Comparison of query times between baseline algorithms and DVTG-CKNN w.r.t. \(k\). (a) Query times on BJ; (b) Query times on NY; (c) Query times on COL; (d) Query times on NW. Figure 15: Comparison of query times between baseline algorithms and DVTG-CKNN w.r.t. the number of moving objects. (a) Query times on BJ; (b) Query times on NY; (c) Query times on COL; (d) Query times on NW. distribution strategy, the performance advantage of DVTG-C\(k\)NN is more obvious than that of the benchmark algorithm. This is because the DVTG-C\(k\)NN algorithm is based on the DVTG-Index, which is designed for unevenly distributed dynamic road networks, and balances the uneven distribution of moving objects by dynamically dividing the grid. Finally, we evaluated the impact of different consecutive query times on the performance of \(k\)NN queries. We set the number of continuous queries as 1, 3, 5, 10, and 20, and the moving objects used the ZD distribution strategy. Other experimental parameters were \(k\) = 5, 10% of all taxis as moving objects in the BJ dataset, and 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 17, the average continuous query time of DVTG-C\(k\)NN is the shortest among the three algorithms. Especially after the number of continuous queries gradually increases, the performance advantage of DVTG-C\(k\)NN compared with the baseline algorithm is more obvious. This is because the DVTG-C\(k\)NN algorithm provides traversal for subsequent continuous queries through the query vertex queue. The boundary vertices in the queue are not updated as the position of the moving object changes. Therefore, the border vertex data in the queue can still be used again in continuous queries, and the number of border vertices is greater than that of active vertices; therefore, the repeated traversal of vertices can be reduced. ## 7 Conclusions

This paper studied the problem of the continuous \(k\)-nearest neighbor query for moving objects in a road network, and proposed the DVTG-Index, a dynamic multi-layer grid index, which can index moving objects in the road network and update them in real time. Secondly, this paper provided a continuous \(k\)-nearest neighbor query method for moving objects in a road network based on the DVTG-Index. DVTG-C\(k\)NN can perform efficient and continuous \(k\)-nearest neighbor queries, and the query efficiency reaches the microsecond level, which is obviously better than the mainstream algorithm used at present for solving this problem. Finally, we conducted experiments on a real road network dataset. The experimental

Figure 8.0 Comparison of query times between baseline algorithms and DVTG-C\(k\)NN under the three distribution strategies. (**a**) Query times on BJ; (**b**) Query times on NY; (**c**) Query times on COL; (**d**) Query times on NW. Figure 8.1 Comparison of query times between baseline algorithms and DVTG-C\(k\)NN w.r.t. the number of continuous queries. (**a**) Query times on BJ; (**b**) Query times on NY; (**c**) Query times on COL; (**d**) Query times on NW.