# 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  
According to the above points, we associated the query point with the vertices of the vertex subgraph, and the query between objects was converted into the query between vertices. In order to better explain the query algorithm, we first need to define some concepts. **Definition 12**. : _Vertex Queue \(S\). We defined vertex queue \(S\) as:_  
\[S=\{q\}\cup\bigg{\{}v\in V\bigg{|} \begin{array}{c}\text{$v$ is a boundary or active vertex}\\ \text{in the vertex subgraph where $q$ resides}\end{array} \bigg{\}}. \tag{8}\]  
During the search process, the vertices in the processed vertex subgraph are continuously added to \(S\) until the algorithm terminates or the graph \(G\) is traversed. We can express this process as follows:  
\[S_{t+1}=S_{t}\cup\{v\in V|v\text{ is a vertex in the processed subgraph at iteration }t\}. \tag{9}\]  
where \(S_{t+1}\) denotes the state of the vertex queue at iteration \(t\). Figure 7: The schematic diagram of index update instructions. Since graph \(G\) is a directed and weighted graph, all road networks can be connected through boundary vertices. The \(S\) queue represents the scope of the search map at present. During the search process, the vertices in the processed vertex subgraph are continuously added to \(S\) until the algorithm terminates or the graph \(G\) is traversed. **Definition 13**. : _Query Queue \(F_{q}\). The query queue \(F_{q}\) stores the \(n\) moving objects closest to the query point \(q\), that is, the final result of the \(k\)-nearest neighbor query. In \(F_{q}\), the road network distance between the moving object \(O_{n}\) that is farthest from \(q\) and \(q\) is denoted by \(\zeta\). Therefore, we can mathematically represent \(F_{q}\) as follows:_  
\[F_{q}=\{O_{i}|i=1,2,\ldots,n\}. \tag{10}\]  
_where \(O_{i}\) is the \(i\)-th moving object in the queue \(F_{q}\). The distance between each moving object \(O_{i}\) and query point \(q\) is denoted by \(SDist(O_{i},\,q)\). Let \(\zeta\) be the maximum distance between any moving object \(O_{i}\) and \(q\). Therefore, we can express \(\zeta\) as:_  
\[\zeta=\max(SDist(O_{i},\,q)). \tag{11}\]  
When the algorithm ends, the distances from other mobile objects \(O_{n}\) to the query point \(q\) are greater than \(\zeta\), that is:  
\[SDist\big{(}\,O_{n}\,^{\prime},q\big{)}\geq\zeta,\forall\,O_{n}\,^{\prime}\
otin F _{q}. \tag{12}\]  
**Definition 14**. : _Query Vertex Queue \(D\). The query vertex queue \(D\) stores the vertices that have been determined to have the shortest distance to the query point. Queue \(D\) is initially created as an empty set. The vertices are added to \(D\) during the search process as their shortest distances are determined. Mathematically, we can define \(D\) as:_  
\[D=\{v|v\text{ is a vertex that has been determined to have the shortest distance to }q\}. \tag{13}\]  
Queue \(D\) is convenient for subsequent continuous queries, because the boundary vertices are not updated as the position of the moving object changes. Therefore, the border vertex data in the queue can still be used again in continuous queries, and the number of border vertices is higher than that of active vertices; therefore, the repeated traversal of vertices can be reduced. Then, we detailed the steps of the first \(k\)-nearest neighbor query algorithm:  
When the system received a \(k\)-nearest neighbor query request \((q,k)\), it first associated query point q with its nearest vertex v; if \(v\) is not an active or boundary vertex of the vertex subgraph, it means that vertex \(v\) is not in the vertex set of the vertex subgraph, and the distance from vertex v to other vertices in the vertex subgraph is not calculated. Therefore, we needed to activate \(v\) as an active vertex first, add it to the vertex set of the vertex subgraph, update the index, and obtain the shortest distance between \(v\) and any boundary vertex in the vertex subgraph and the active vertex. If \(v\) itself is an active or boundary vertex in a vertex subgraph, no additional operations are required.