# 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
When the moving object started to move on the road network, the index update performance also directly affected the performance of subsequent \(k\)-nearest neighbor queries. The number of moving objects and the index grid threshold affect the update performance of the index. Therefore, in this section, we evaluated the impact of various parameters on the performance of the DVTG-Index update. Figure 10: Comparison of construction time and space costs between baseline algorithms and DVTG-Index. (**a**) Construction time and space costs on BJ; (**b**) Construction time and space costs on NY; (**c**) Construction time and space costs on COL; (**d**) Construction time and space costs on NW. Figure 9: Construction time and space costs overhead of DVTG-Index w.r.t. \(l\). (**a**) Construction time and space costs on BJ; (**b**) Construction time and space costs on NY; (**c**) Construction time and space costs on COL; (**d**) Construction time and space costs on NW. First, we evaluated the impact of the number of moving objects on the index update time. In the BJ dataset, select 10%, 30%, 50%, 70%, and 100% of all taxis as the number of moving objects. In datasets NY, COL, and NW, 0.5%, 1.5%, 2.5%, 3.5%, and 5% of the number of vertices are generated as the number of moving objects, respectively. Among them, the index grid threshold \(\eta\) is set to 8. As shown in Figure 11, it can be seen from the experimental results that as the number of moving objects increases, the updated overhead time also increases. The result is consistent with the principle of our design; the increase in the number of moving objects leads to the more frequent splitting and merging of the index grid during the update process, and the calculation time of the vertex distance matrix also increases accordingly. Then, we evaluated the impact of index grid threshold \(\eta\) on the index update time. Among them, in the BJ dataset, the taxi trajectory between 8:00-9:00 on February 2 was obtained, and in datasets NY, COL, and NW, 5% of the number of vertices was used as the number of moving objects. As shown in Figure 12, it can be seen from the experimental results that there is no positive or negative correlation between the index update time cost and index grid threshold \(\eta\). When the threshold is relatively small, as the moving objects change, the index grid is more likely to be split down or merged up until the number of moving objects in the grid meets the threshold range, which takes a long time to update the index. As the threshold gradually increases, the number of moving objects that can be accommodated in the grid increases, and the time for grid scaling decreases so the total updated overhead time decreases. However, when the threshold gradually increases to a certain value, the number of active vertices in a single index grid is also very high, which makes the calculation time of the vertex distance matrix in the grid increase sharply. This makes the total time cost of the index update gradually increase with the increase in the threshold. In addition, the results of different datasets show that there are corresponding optimal thresholds in different road networks to minimize the update time cost, and the optimal value of the threshold increases with the increase in the dataset. Finally, we conducted comparative experiments on the index update performance of V-Tree, G*-Tree, SILC, and the DVTG-Index. Dataset BJ takes 100% of taxis as moving objects, 5% of the number of generated vertices in datasets NY, COL, and NW as moving objects, and ZD as the moving-object distribution strategy. Figure 11: Time cost of updating DVTG-Index w.r.t. the number of moving objects. (**a**) Time cost on Bj; (**b**) Time cost on NY, COL and NW. As depicted in Figure 13, the empirical results demonstrate that the DVTG-Index exhibits the lowest and a relatively stable update time cost.