# 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
For the other three road network sets, we used the moving-object simulation generation software invented by [PERSON] [32] to realize the initial distribution and update the movement and query requests of moving objects in the road network. We temporarily set the total number of moving objects as one percent of the number of vertices, and we use the following three strategies to simulate the starting position and subsequent trajectories of the moving objects: RD (random distribution), ND (normal distribution), and ZD (Zipf distribution). ### Baseline Algorithm

We compared the DVTG-Index with three benchmark methods: V-Tree, G*-Tree, and SILC. These three methods were implemented in this experiment; the implementation of the first two methods was provided by their authors, and the implementation of SILC as completed by us. This is how it worked: we started by building an index structure for the (static) road network. Then, we created a reference index, such as the DVTG-Index, which saves a list of moving objects from the vertex to the vertex. Similar to our approach, if a vertex has some moving objects, SILC calls it a POI. Because POIs may contain multiple moving objects, POIs need to build a list of moving objects. Additionally, when looking for \(k\)NN moving objects, the algorithm will stop. SILC uses a best-first approach to compute \(k\)NN results. We also used this index to keep POIs, calculate top-\(k\)NN POIs, and add moving objects of interest points to the result set. \begin{table}
\begin{tabular}{c c} \hline
**Software and Hardware** & **Version/Model** \\ \hline Operating system & Windows 10 (1902) \\ CPU & Intel Core i7-7700 HQ \\ Memory & 8 GB \\ Hard disk & 1 TB \\ Java & Jdk1.8.2 \\ \hline \end{tabular}
\end{table} 
Table 1: The computer software/hardware configuration. \begin{table}
\begin{tabular}{c c c c} \hline
**Dataset** & **Name** & **Number of Vertices** & **Number of Sides** \\ \hline BJ & Beijing & 188,229 & 436,648 \\ NY & New York City & 264,346 & 733,846 \\ COL & Colorado & 435,666 & 1,056,066 \\ NW & Northwest USA & 1,207,945 & 2,840,208 \\ \hline \end{tabular}
\end{table} 
Table 2: Experimental software and hardware configuration table. ### DVTG-Index Experiment Situation

In this section, we conducted experiments by changing the threshold \(\eta\) of the number of moving objects in the parameter grid; we conducted performance evaluations from two aspects: the time and space overhead of the index construction and the time and space overhead of the index update. In order to exclude the influence of other factors, the results of this experiment are the average values obtained after repeated experiments. First, we evaluates the characteristics of the DVTG-Index, built a static DVTG-Index, V-Tree, G*-Tree, and SILC on the datasets BJ, NY, COL, and FLA, and compared the time cost \(t_{c}\) and space cost of building the index \(m_{c}\), as shown in Figure 8. Among them, the road network set BJ randomly selected the real distribution of taxis at 8:00, 12:00, and 17:00 on February 2, and the road network set NY used three different distribution strategies to set the starting position of the moving object. Among them, the construction time of the DVTG-Index was composed of the network construction time, vertex distance matrix calculation time, and vertex elevated graph construction time; construction space was composed of the road network set, boundary vertices and active vertex sets, vertex distance matrix, and vertex elevated graph. As shown in Figure 8a,b, 8:00 and 17:00 in Beijing are the morning and evening peak periods, respectively; therefore, there are more moving objects and increased time and space factors for the index construction. As shown in Figure 8c,d, the number of vertices and edges of the road network sets NY, COL, and NW increases sequentially.