# 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
The constructed DVTG-Index needs to construct more vertex subgraphs and calculate more vertex distance matrices at the same time, so that the memory space occupied by the index increases sequentially and the construction overhead time also increases. In addition, different distribution strategies of moving objects also have a certain impact on time and space costs. Under the three distribution strategies of RD, ND, and ZD, the time and space costs of the constructed DVTG-Index increase in turn. With an uneven distribution, the indexed grid requires more merge-up and split-down operations, thus requiring more time and space overhead. When the index is constructed, the number of grid divisions determines the number of grids in the initial index. According to the above factors, if the grid is divided \(l\) times, the number of grids is \(4^{l}\). The number of grids determines the size of the grid area and determines how many nodes and moving objects are included in the grid; therefore, we changed the number of grid divisions \(l\) to evaluate the time and space overhead of the DVTG-Index on each dataset. To exclude the influence of other factors, in this experiment, we adopted the ZD distribution strategy, and the data shown in the chart are the average of the results of multiple experiments. As shown in Figure 9, it can be observed from the experimental results that there is no positive or negative correlation between the construction time and space costs and the number of grid divisions \(l\). As the number of grid divisions gradually increases, the time and space values overhead first decrease and then increase. This is because when the number of grid divisions is low, the number of grids is low, the area of a single index grid is large, and the number of active vertices in a single index grid is high, which makes the calculation time and space overhead of the shortest distance matrix in the grid larger. Due

Figure 8: Time and space costs of the DVTG-Index. (**a**) Time costs on BJ; (**b**) Space costs on BJ; (**c**) Time costs on NY, COL and NW; (**d**) Space costs on NY, COL and NW. to the small number of index layers, the calculation time and space overhead of the shortest distance matrix account for a large proportion of the total cost; therefore, as the grid is split, the total time and space costs of the index construction are significantly reduced. However, when the number of index layers gradually increases to a certain number, the time to split the index grid down gradually increases, and the number of shortest-distance matrices increases, which also makes its space cost increase sharply; therefore, the total time and space overhead of the index construction starts to increase as the number of index layers increases. In addition, we found that the experimental results of the time and space overhead of building indexes have similar trends in different datasets; therefore, we can use the NY dataset to evaluate the index performances in subsequent experiments. Then, we conducted comparative experiments for V-Tree, G*-Tree, SILC, and the DVTG-Index. As shown in Figure 10, it can be seen from the results in the figure that the construction time for V-Tree is significantly longer than that of the other indexes. This is because V-Tree must perform the Floyd algorithm for all subgraphs to calculate the distance matrix. Although the subgraphs in the upper layer only save the boundary points of the lower layer, the number of calculations is still very high. However, the DVTG-Index iteratively merges some useless vertex subgraphs upwards, reducing the number of boundary points and greatly optimizing the index construction. In addition, with the increase in the road network, the advantages of our method are more obvious. The real-time change in moving objects is one of the difficulties in this study. Our index associated the moving objects with the vertices of the road network index and mapped the changes in the moving objects to the update of the index, which better handled this difficulty.