# A Dynamic Grid Index for C\(k\)NN Queries on Large-Scale Road Networks with Moving Objects
## 4 Dynamic V-Tree Double-Layer Grid Index
### Update Mechanism of the DVTG-Index
#### 4.2.1 Update of Moving Objects  
The real-time update of large moving objects is a major feature in the urban road network environment, and it is also a difficulty in this research scenario. This paper introduced the concept of the active vertex; therefore, binding the moving object to the corresponding active vertex can efficiently handle the problem of updating the position of the moving object. The specific details of the update strategy are:  
First, in the road network, the motion scenes of moving objects can be summarized into the following three situations:  
* Add moving object: we added a new object \(O_{r}\) on edge \(e_{u,v}=(u,v,w)\), and \(O_{r}\) moved towards vertex \(v\), for example, a taxi driver just exited the car or just finished the last task.
* Delete a moving object: we deleted a moving object \(O_{r}\) from the edge \(e_{u,v}=(u,v,w)\), for example, the driver finished a task and left work, or the car broke down and could no longer carry passengers.
* Update the moving object: the position of the moving object \(O_{r}\) changed, which was the most common situation. We further subdivided it into two cases according to the variation in moving objects. The first case was that \(O_{r}\) was still on the edge \(e_{u,v}\); however, the distance from the active vertex \(v\) changed. In this case, we only needed to change the \(\delta\) attribute in \(O_{r}=(t,(u,v),\ \delta)\), and the time complexity was only O(1); the second case was that the side where \(O_{r}\) was located changed, for example, \(O_{r}\) moved from side \((u,v)\) to side \((v,w)\). At this time, we only needed to combine the operations of (1) and (2), delete \(O_{r}\) from edge \(u\), and add \(O_{r}\) on edge \((v,w)\), that is, the cross-edge movement of the moving object was realized.  
From the analysis above, we only needed to consider the operations of adding and deleting moving objects.  
Add moving object: add moving object \(O_{r}\) to edge \(e_{u,v}=(u,v,w)\). At present, there are two cases according to the state of the vertex. (1) If \(v\) is an active vertex, you only need to add \(O_{r}\) to the moving object collection \(Q_{v}\) maintained by \(v\); (2) if \(v\) is not an active vertex and \(Q_{v}\) is an empty set, we first mark \(v\) as an active vertex, and at the same time add \(O_{r}\) to the moving object collection \(Q_{v}\) maintained by \(v\). Then, judge whether the number of moving objects in the vertex subgraph where \(v\) is currently located is within the threshold range. If it is within the range, the vertex subgraph does not need to be split or merged. Then, calculate the shortest distance from this point to other boundary vertices in the vertex subgraph and update the shortest distance matrix. If not within the threshold range, iteratively split or merge vertex subgraphs, and then calculate the shortest distance matrix of the new vertex subgraph.  
Remove moving objects: remove \(O_{r}\) from edge \(e_{u,v}=(u,v,w)\). At this point, two situations still need to be considered: (1) if the number of moving objects contained in the moving object set \(Q_{v}\) maintained by vertex \(v\) is more than 1, then it is only needed to delete \(O_{r}\) from \(Q_{v}\); (2) if there is only one moving object \(O_{r}\) in \(Q_{v}\), then we also delete \(O_{r}\) from \(Q_{v}\) first, because \(Q_{v}\) is empty at this time, that is, no moving object moves to \(v\)then \(v\) becomes a normal vertex. Then, it is also judged whether the number of moving objects in the vertex subgraph where \(v\) is currently located is within the threshold range, and corresponding merging and splitting operations are performed.