# 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  
Since the boundary vertices are only related to the road network itself, as long as the grid division does not change, the properties of the vertices as boundary vertices will not change. As the position of the moving object changes, only the active vertices are changed. Additionally, the number of boundary vertices is far greater than that of active vertices. Therefore, when query request \(q\) has already performed the first \(k\)-nearest neighbor query operation, we can simplify the continuous \(k\)-nearest neighbor query based on the query vertex queue \(D\). Perform the query from the range that was searched the previous time, and continue to expand it on the basis of this queue, instead of starting from scratch. The specific steps of the continuous \(k\)-nearest neighbor query algorithm are as follows. We first associated query point q with the nearest vertex v, similar to the first \(k\)-nearest neighbor value. Then, traverse the vertices in query vertex queue \(D\) saved after the initial \(k\)-nearest neighbor query operation; if the vertex \(v\) in it was the active vertex at the time of the last query and is still the active vertex at this time, add the moving objects in the moving object sequence \(Q_{v}\) maintained by \(v\) to the new \(F_{q}\). If \(v\) is no longer the active vertex, proceed to the subsequent node. If \(v\) is a boundary vertex, traverse the adjacent vertices of \(v\) to determine whether there is a new active vertex u or a boundary vertex that does not belong to \(D\). If so, add it to \(S\). If it is an active vertex, judge whether the active vertex is less than the distance from the last vertex in \(D\) to query vertex v, which is the furthest distance from the query point among the confirmed nodes. If it is less than, then update \(v\)'s mobile object sequence \(Q_{v}\) to \(F_{q}\), delete u from S, and insert it into \(D\). If the number of moving objects in \(F_{q}\) exceeds \(k\), and the distance from the processed vertex in \(D\) to \(v\) is greater than the distance \(\zeta\) from the moving object farthest from the query point in \(F_{q}\) to the query point, the algorithm is terminated early. If the algorithm still cannot end after traversing all the nodes in \(D\), continue to follow the operation of the initial \(k\)-nearest neighbor algorithm to traverse query range sequence \(S\) and continue to expand the search range. The pseudocode of the continuous \(k\)-nearest neighbor query algorithm is shown in Algorithm 2. ``` Input: \(O_{v}\), \(v\) // Find the \(k\) closest moving objects to the query point \(q\) Output: \(F_{q}\) // Returns the \(k\)-nearest neighbor query queue \(function\)\(\mathcal{C}\)\(\mathcal{k}\)\(\mathcal{N



The act of updating the vertex subgraph and deriving distances can be viewed as an operation for each active vertex with a time complexity of \(O(N)\), where \(N\) is the number of all vertices indexed at the top level. However, the time complexity of calculating the distance of each vertex to other vertices is \(O\big{(}M^{2}\big{)}\); however, since the shortest distance between vertices was obtained by distributed computing in our method, \(M\) should be the largest number of vertices in all vertex subgraphs. Then, the time complexity of enqueuing the vertex is \(O(1)\). The time complexity of the operation of traversing the vertex queue is \(O(N)\), where \(N\) is the number of vertices in the vertex queue. The time complexity of finding vertex v is \(O(log\ N)\), and the minimum heap is used for searching. For the processing of vertex \(v\), if it is an active vertex, the time complexity of adding its moving object set to the query queue is \(O(1)\); if it is a border vertex, the time complexity of traversing all its adjacent border vertices is \(O(K)\), where \(K\) is the degree of each border vertex.