# 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
Therefore, the total time complexity is \(O\big{(}M^{2}+N\ \log N+KP\big{)}\), where \(N\) is the number of all vertices in the top-level index, \(M\) is the number of vertices at most in all vertex subgraphs, \(K\) is the degree of each border vertex, and \(P\) is the number of border vertices. However, in practice, the time complexity of the \(k\)NN algorithm also depends on the value of \(k\). When \(k\) is small, the time complexity of the algorithm is lower; when \(k\) is large, the time complexity of the algorithm is higher. Therefore, choosing an appropriate value for \(k\) has a great influence on the performance of the algorithm, which we tested and proved in subsequent experiments. However, the time complexity of DVTG-\(\mathcal{CNN}\) is difficult to accurately evaluate because it depends on the number of active and boundary vertices close to the query point and the relationship between the vertices. Ideally, the number of active vertices is less than the number of boundary vertices, and the number of adjacent vertices of each boundary vertex is also small. In this case, the time complexity of the algorithm can be assumed to be \(O(k)\). However, if the number of active vertices is high and the number of border vertices adjacent vertices is also high, the time complexity may be high. Therefore, the exact time complexity of this algorithm cannot be provided, and we tested it in the experiments in the subsequent section. #### 5.4.2 Space Complexity

Based on the algorithm's description, the space complexity of the DVTG-\(\mathcal{CNN}\) algorithm can be analyzed as follows:

The space required to store the vertex subgraph, including active, adjacent, and boundary vertices, can be considered as \(O(|V|)\), where \(|V|\) is the total number of vertices in the subgraph. The space required to store the moving object sets of active vertices, including the query queue \(F_{q}\), can be considered as \(O(|O|)\), where \(|O|\) is the total number of moving objects in the subgraph. The space required to store vertex sequence \(S\) and query vertex queue \(D\) can also be considered as \(O(|V|)\). In addition, the space required to store the shortest distances between vertices, which are updated during the search, can be considered as \(O\Big{(}|V|^{2}\Big{)}\). Therefore, the total space complexity of the DVTG-\(\mathcal{CNN}\) algorithm can be approximated as \(O\Big{(}|V|^{2}+|O|\Big{)}\). ## 6 Experiment Analysis

In this section, we experimentally evaluated the performance of DVTG-Index and presented the performance of our proposed DVTG-\(\mathcal{CNN}\) algorithm when dealing with the \(k\)NN and continuous \(k\)NN queries. To fully evaluate the performance of our method, we chose three advanced methods, \(G^{*}\)-Tree, V-Tree, and SILC, as benchmark algorithms to compare to our method. ### Experiment Settings

This experiment was based on the Java language program, and the IDE program used IDEA. The computer software/hardware configuration is shown in Table 1.

Additionally, we validated the performance of our query model by simulating a set of objects moving on a real road network. Therefore, we needed three types of datasets that were real road network, moving-object, and query-request datasets. This experiment selected the following three real-world road networks for the experiments: BJ (Beijing), NY (New York), COL (Colorado), and NW (Northwest USA) [30]. These networks have been widely used in previous studies, and the number of nodes in the road network ranges from hundreds of thousands to millions. The specific information is shown in Table 2.

For the BJ road network set, we used a real-world dataset, BJ T-drive, containing actual taxi trajectories in Beijing from February 2 to August 2008, which included nearly 18 million GPS trajectories for 10,350 taxis. We used existing methods to map the locations of moving objects and queries onto road networks [31].