# A Dynamic Grid Index for C\(k\)NN Queries on Large-Scale Road Networks with Moving Objects
## 2 Related Work  
The C\(k\)NN query has been an extensively studied research topic, with numerous theories and algorithms developed to address it. The research at present aims to reduce the query-processing time on the server side and deliver rapid results to users. However, because the continuous \(k\)NN query involves numerous moving objects, object-by-object scanning considerably reduces the query-processing performance [13]. To overcome this challenge and improve query-processing efficiency, location indexing techniques have been developed and are deemed necessary. Traditional database indexing sorts the data to store and access records effectively. However, these methods are not appropriate for frequently changing the data or location of moving objects due to the high cost of updates [14]. Moving object location indexing is a challenging research field, with proposed index structures based on spatial, time, or combined spatial and time indexing technologies. The research at present is still in the preliminary stage, both domestically and abroad [15]. The spatial index can be divided into categories according to the basic unit of index structure. Representative indexes include grid, tree-like, and hybrid indexes [16]. In [17], [PERSON] et al. proposed an efficient distributed solution for \(k\)NN queries, which can handle larger amounts of moving-object data. The proposed solution included a new network-based index called BGI (block grid index). The BGI is an in-memory index based on a distributed hierarchical grid with a minimum and maximum predefined number of moving objects per block. Additionally, [PERSON] et al. [18] proposed a DGI (distributed grid index), which builds an index in the form of a hierarchical grid according to the location of objects. S-GRID (scalable grid) is also one of the very classic grid indexes that was proposed by [PERSON] et al. [19] to deal with the problem of road network indexing. Although these grid-based indexes pre-define the number of moving objects or layer the grid, as the moving objects and road networks change, the index cannot rapidly adapt or produce efficient query responses. This limits the efficiency of these indexes in large, dynamic, road network graphs. In addition, the most common tree-like indexes are R-Tree, K-D Tree, Z-Tree, and Quad-Tree indexes. Among them, R-Tree and PMR Quad-Tree [20] indexes have a good performance for indexing traditional spatial objects. In order to further improve the query efficiency of \(k\)NN, [PERSON] et al. proposed a balanced search-tree G-Tree (grid tree) index structure in 2013 [21]. Based on G-Tree, the G*-Tree index improves the query efficiency of G-Tree by dividing each node into two disjoint regions [22]. This optimization is based on a simple observation that, during querying, when a region is completely contained within the query range, other regions that do not intersect with this region can be ignored. Recently, [PERSON] et al. [23] proposed the Velocity SpatioTemporal indexing approach. The proposed structure is based on a selective velocity-partitioning method that reduces the update cost and improves the response time and query precision. [PERSON] [24] of Tsinghua University proposed a new index: V-Tree. It can support a \(k\)-nearest neighbor search based on the road network. Second, it can support the dynamic updating of moving objects. The V-Tree index's structure is optimized further, based on G-Tree, to become the \(k\)NN query for moving objects. While these methods have shown a good performance in indexing traditional spatial objects, they may face several limitations when applied to the query of moving objects in large road networks. One limitation is that these methods may not efficiently handle the continuous updates of the location's information of moving objects, resulting in high update costs and query latencies. Another limitation is that they may not consider the road network's topology, which may result in inaccurate \(k\)NN queries and longer query times.