# 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.2 Index Update  
Updates to moving objects cause the number of active vertices within the vertex subgraph to change. At present, the distribution of moving objects in the city is mostly a Zipf distribution, not an even distribution; therefore, the number of active vertices in different vertex subgraphs is quite different, and the corresponding vertex distance matrix also requires higher calculation and space costs. In order to more reasonably balance the global computing load, the vertex subgraph needs to merge or split the subgraph according to the relationship between the number of active vertices of itself and the surrounding and set thresholds. In this study, the threshold value of number of active vertices \(v_{a}\) in the subgraph was set to \(\eta\). When adding a moving object, if the number of active vertices in the current vertex subgraph \(g_{j}^{i}\) is more than \(\eta\), the subgraph g is split into four subgraphs, and furthermore, the four subgraphs of g are updated to calculate the corresponding shortest distance matrix. If the number of moving objects in a certain subgraph still meets the split condition, continue to recurse the abovementioned operations, layer by layer, until the split condition is not met. When deleting a moving object, if the sum of the number of active vertices in the current vertex subgraph \(g_{j}^{i}\) and the number of active vertices in its three sibling vertex subgraphs is less than the specified threshold \(\eta\), merge them into a new vertex subgraph \(g_{f^{i}-1}^{i-1}\). If the number of active vertices of the parent subgraph \(g_{f^{i}}^{i-1}\) of \(g_{j}^{i}\) and its three sibling subgraphs is still less than \(\eta\), continue to recursively operate layer by layer until the number of active vertices in the upper subgraph \(g_{f^{i}}^{i}\) of \(g_{j}^{d}\) (\(1\leq i<d-1\)) is not less than \(\eta\) or \(i=1\). \(g_{f^{i}}^{j-1}\). Save and maintain all the active vertices in the four subgraphs, update the border vertices, and recalculate the shortest path \(SPath(v_{u},\ v_{w})\) between any border and other vertices; save the shortest distance \(SDist(v_{u},\ v_{w})\) between vertices and the vertex distance matrix \(DistM_{i}^{j}\). When the road network map is large enough, there will be a high number of moving objects that need to be updated at the same time. Therefore, we used the method of scanning subgraphs to update all the moving objects in batches, and then updated the vertex subgraphs, which greatly improved the update efficiency of the DVTG-Index. According to the description of the index update algorithm, if updating the moving object does not change the attributes of the vertices, the time complexity of updating is \(O(1)\). If the update operation changes the attributes of each vertex and changes the index structure, it needs to be discussed separately. Since the vertex subgraph needs to be recursively split or merged every time a moving object is added/deleted to balance the computational load, the time complexity of each adding/deleting a moving object is related to the recursive depth of the vertex subgraph. Therefore, it can be observed that the time complexity of the algorithm is \(O(log\ n)\). Because each operation may cause the recursion depth of the vertex subgraph to change, the time complexity can only be used as an approximation. The index update algorithm can effectively balance the global computing load; however, it also needs to consider the impact of space complexity, because splitting subgraphs increases the space usage. We tested this in the experiments in the subsequent section. With the update of the index of the change in the position of the moving object, taking the road network in Figure 7 as an example, when there are more moving objects in the grid subgraph in the lower left corner of the original road network diagram, as shown in Figure 5, the number of active vertices reaches three, which exceeds the threshold.