# A Dynamic Grid Index for C\(k\)NN Queries on Large-Scale Road Networks with Moving Objects
## 5 DVTG-CNN Query Algorithm
### The First \(k\)-Nearest Neighbor Query
The boundary and active vertices in this vertex subgraph are then added to vertex sequence \(S\). Then, initialize query queue \(F_{q}\) to be empty, and traverse all vertices in \(S\), find the vertex \(v_{1}\) closest to vertex v, and start processing vertex \(v_{1}\) (the first vertex to be processed is the query vertex \(v\) itself, because the weight of the road is a positive number and \(SDist(v,v)=0\); therefore, there is no need to consider the vertex itself). If \(v_{1}\) is the active vertex, add \(v_{1}\)'s moving object set \(Q_{v}\) to \(F_{q}\), and the distance from the moving object \(O_{n}\) in the set to the query point \(q\) is \(SDist(v_{1},v)+\delta\); if \(v_{1}\) is a border vertex, it is necessary to expand the search area and traverse all adjacent border vertices \(u\) of \(v_{1}\). If \(u\) is in vertex queue \(S\) and \(SDist(u,v_{1})+SDist(v_{1},v)<SDist(u,v)\), update \(SDist(u,v)=SDist(u,v_{1})+SDist(v_{1},v)\). If \(u\) is not in vertex queue \(S\) or query vertex queue \(D\), add \(u\) to \(S\). At this point, the processing of vertex \(v_{1}\) is completed, and then \(v_{1}\) is deleted from \(S\) and added to query vertex queue \(D\). Then, traverse all the nodes in \(S\) again, and continue to process the subsequent vertex closest to query vertex \(v\) until the algorithm ends early or \(S\) is empty (if the algorithm ends early, it means that there are \(k\) or more moving objects in the query queue, and if \(S\) is empty, it means that all the connected graphs have been searched). If the number of moving objects in \(F_{q}\) is greater than \(k\), more than \(k\) moving objects have been found (because the number of moving objects contained in each active vertex is different, the number of moving objects saved in \(F_{q}\) will not be exactly \(k\) every time), then sort them according to the road network distance from the query point. Whenever the subsequent vertex \(v_{n}\) is processed, a judgment is made: if \(SDist(v,v_{n})\geq\zeta\), the algorithm ends early. Because the Dijkstra-style algorithm searches for vertices in the order of near to far, if \(SDist(v,v_{n})>\zeta\), the distance from the subsequent active vertex \(u\) containing the object moving to the query vertex \(SDist(v,u)\) must be greater than or equal to \(SDist(v,v_{n})\); therefore, the distance between the object \(O_{n}\) moving towards \(u\) and the query point must be greater than or equal to \(SDist(v,u)\), and thus greater than \(\zeta\). From this, it can be determined that \(k\) moving objects in \(F_{q}\) are the \(k\) moving objects closest to \(q\). If \(SDist(v,v_{n})<\zeta\) and the processed node is an active vertex, the moving object \(O_{n}\) in this point may still be closer to the query point than the moving object in \(F_{q}\); then, we need to compare \(O_{n}\) with the moving object in \(F_{q}\) and update it. The pseudocode of the first \(k\)-nearest neighbor algorithm is shown in Algorithm 1. ```
Input: \(q\&\) // Find the \(k\) closest moving objects to the query point \(q\) Output: \(F_{q}\) // Returns the \(k\)-nearest neighbor query queue
``` \(function\)\(kNN(q,k)\)  Associate \(q\) with vertex \(v\) nearby  add \(v\) into \(G_{V}\);  add \(v\) into \(S\); \(F_{q}\leftarrow\varnothing\), \(\zeta\leftarrow\infty\); \(D\leftarrow\varnothing\); while\(S\
eq\varnothing\)do  Dist \(\leftarrow\infty\); for each vertex \(u\) in \(S\)do  if\(SDist(v,u)<\) Dist then  Dist \(\leftarrow\)\(SDist(u,v)\); if\(|F_{q}|=k\) and \(\zeta\leq\) Dist then break; if\(u\) is in \(\mathcal{A}\) then  add \(u.Q_{u}\) into \(F_{q}\) \(\zeta\leftarrow min\{\zeta\), \(max\{SDist(O_{n},v)\}\}\) else for each vertex \(w\) in \(u^{\prime}s\) neighbors do  if\(w\in S\) and \(SDist(v,w)\)\(>\)\(SDist(v,u)+SDist(u,w)\)then  SDist(\(v,w)=SDist(v,u)+SDist(u,w)\) else if\(w\
otin D\)then  add \(w\) into \(S\) remove \(u\) from \(S\) add \(u\) into \(D\) return\(F_{q}\) ```
**Algorithm 1**The first \(k\)-nearest neighbor query