The INE algorithm is based on the idea of the Dijkstra algorithm, which accesses
the network nodes based on their increasing distance from the source of the query. It
takes the distance from the traversed node to the query point into the priority queue,
and each time the node with the smallest distance is selected to expand its neighbor.
The IER algorithm first finds the nearest query object of k Euclidean distance [17] and
then uses the shortest path algorithm to calculate the distance of the road network from
the query point one by one. The k query objects form the initial candidate set and then
continue to find the next neighbor according to the Euclidean distance, calculate the
distance of the road network from the query point with the shortest path algorithm and
then update the candidate set. When the Euclidean distance of the query object is
greater than or equal to the current candidate set distance, the calculation is stopped,
and the distance is the Kth largest value. At the end of the search, the k query objects in
the candidate set are the k-nearest neighbors we are looking for. The shortest path
algorithm here is optional A
* algorithm [18]. The VN
3 algorithm uses the geometric
properties of spatial objects to divide a large road network into multiple small Voronoi
regions and pre-calculate the distance between them. The G-tree algorithm proposes an
index of a balanced search tree called G-tree (graph tree) [16], which is a graph tree. Its
index structure is very similar to the index structure of the R-tree, which is constructed
by recursively dividing the road map into smaller subgraphs. Each node in the G tree
corresponds to a sub-network. Similarly, it pre-calculates the minimum road distance
between some sub-networks. Then searching for the query object in the corresponding
sub-networks on the G-tree.
Existing research focuses on kNN search for static objects [19–24] or continuous
kNN search and Euclidean distance constraints [25–34]. The former does not support
dynamic updates of moving objects because updating indexes is quite expensive. The
latter cannot effectively calculate the distance on the road network. Therefore, they
cannot effectively solve this problem.
The moving object in the road network is a special kind of moving object. Compared with the moving object in free space, the moving object of the road network has
the following characteristics.
a. The motion trajectory of the moving object can only be moved within the road
network by the limitation of the road network.
b. The movement process of the moving object is subject to traffic regulations. For
example, in certain road sections, it must be moved in accordance with the specified
direction, and the control of traffic lights must be observed.
c. Both the query object and the object being queried are located in the road network,
so the distance in the query process no longer only represents the Euclidean distance, but the distance of the road network needs to be calculated.
Another important issue is that k-nearest neighbors (kNN) search for moving
objects with road network constraints, and in the case of moving objects and queries on
a given road network, find k objects that are closest to the query location. Existing
research has focused on kNN searches for static objects or continuous kNN searches
with Euclidean distance constraints. The former does not support dynamic updates of
moving objects, while the latter does not support road networks. Since objects move
A Survey of Moving Objects kNN Query …
633
the network nodes based on their increasing distance from the source of the query. It
takes the distance from the traversed node to the query point into the priority queue,
and each time the node with the smallest distance is selected to expand its neighbor.
The IER algorithm first finds the nearest query object of k Euclidean distance [17] and
then uses the shortest path algorithm to calculate the distance of the road network from
the query point one by one. The k query objects form the initial candidate set and then
continue to find the next neighbor according to the Euclidean distance, calculate the
distance of the road network from the query point with the shortest path algorithm and
then update the candidate set. When the Euclidean distance of the query object is
greater than or equal to the current candidate set distance, the calculation is stopped,
and the distance is the Kth largest value. At the end of the search, the k query objects in
the candidate set are the k-nearest neighbors we are looking for. The shortest path
algorithm here is optional A
* algorithm [18]. The VN
3 algorithm uses the geometric
properties of spatial objects to divide a large road network into multiple small Voronoi
regions and pre-calculate the distance between them. The G-tree algorithm proposes an
index of a balanced search tree called G-tree (graph tree) [16], which is a graph tree. Its
index structure is very similar to the index structure of the R-tree, which is constructed
by recursively dividing the road map into smaller subgraphs. Each node in the G tree
corresponds to a sub-network. Similarly, it pre-calculates the minimum road distance
between some sub-networks. Then searching for the query object in the corresponding
sub-networks on the G-tree.
Existing research focuses on kNN search for static objects [19–24] or continuous
kNN search and Euclidean distance constraints [25–34]. The former does not support
dynamic updates of moving objects because updating indexes is quite expensive. The
latter cannot effectively calculate the distance on the road network. Therefore, they
cannot effectively solve this problem.
The moving object in the road network is a special kind of moving object. Compared with the moving object in free space, the moving object of the road network has
the following characteristics.
a. The motion trajectory of the moving object can only be moved within the road
network by the limitation of the road network.
b. The movement process of the moving object is subject to traffic regulations. For
example, in certain road sections, it must be moved in accordance with the specified
direction, and the control of traffic lights must be observed.
c. Both the query object and the object being queried are located in the road network,
so the distance in the query process no longer only represents the Euclidean distance, but the distance of the road network needs to be calculated.
Another important issue is that k-nearest neighbors (kNN) search for moving
objects with road network constraints, and in the case of moving objects and queries on
a given road network, find k objects that are closest to the query location. Existing
research has focused on kNN searches for static objects or continuous kNN searches
with Euclidean distance constraints. The former does not support dynamic updates of
moving objects, while the latter does not support road networks. Since objects move
A Survey of Moving Objects kNN Query …
633