dynamically on the road network, there are two main challenges. The first is how to
express moving objects on the road network, and the second is how to find the k-nearest
moving objects.
Given a set of query points Q = (q 1 , q 2 , …, q n ) and a set of spatial object points
O(o 1 , o 2 , …, o n ) to be queried, find k objects that are closest to any point in Q. That is, the
query returns a set of k pairs of points (k different points o) consisting of point pairs (q i , o j ),
such that for any (q, o) 2 D, qʹ 2 Q, oʹ 2 O/D, both have dist. (q, o)
dist. (qʹ, oʹ).
For example, in Fig. 1c, given a set of queries Q = (q 1 , q 2 , q 3 , q 4 ), K = (k 1 , k 2 , k 3 ,
k 4 ) neighboring objects from corresponding points in Q are, respectively, queried.
The most intuitive and simple method is to find the road network distance of all the
points in Q to all the points in O and then return the pair of points with the smallest
distance value of k road networks. However, if there are many object points, then the
number of pairs of points will be large, and because of the many nodes on the road
network, the cost of calculating the distance between each point and the network is
high, so this method is very inefficient.
In fact, in the above simple method, most of the distance calculation between points
is useless. The k objects closest to the query point set must belong to the kNN of
several points in the query point set. Therefore, we only need to find the kNN of each
query point one by one, and we can get the kNN of the query point set. There are many
ways to find kNN. The most common ones are Dijkstra-based algorithms and IERbased algorithms.
4 Outlook
(1) Road network dynamic update. Road network data is dynamically changed: First,
the nodes, road segments and points of interest in the road network are dynamically changed; secondly, the weight of the road in the road network is dynamically changed; in addition, both the query point and the query object may be
dynamically changed. Under the above circumstances, how to adapt to the
dynamic update of the road network data and efficiently complete the nearest
neighbor query processing is a major challenge for the nearest neighbor query
technology in the road network environment.
(2) Consider the user’s personalized query. With the wide application of locationbased services, users often have a lot of personalized location query requirements,
most of which are based on nearest neighbor queries, such as with time constraints
or A nearest neighbor query problem with keywords.
(3) Consider the road semantics. With the application of smart sensors, users can
combine the road semantic information provided by smart devices to perform
fuzzy query. For example, the background detects the road semantics through the
smartphone in real time, so that the fuzzy query of the user can obtain more
accurate results.
634
W. Jiang et al.
express moving objects on the road network, and the second is how to find the k-nearest
moving objects.
Given a set of query points Q = (q 1 , q 2 , …, q n ) and a set of spatial object points
O(o 1 , o 2 , …, o n ) to be queried, find k objects that are closest to any point in Q. That is, the
query returns a set of k pairs of points (k different points o) consisting of point pairs (q i , o j ),
such that for any (q, o) 2 D, qʹ 2 Q, oʹ 2 O/D, both have dist. (q, o)
dist. (qʹ, oʹ).
For example, in Fig. 1c, given a set of queries Q = (q 1 , q 2 , q 3 , q 4 ), K = (k 1 , k 2 , k 3 ,
k 4 ) neighboring objects from corresponding points in Q are, respectively, queried.
The most intuitive and simple method is to find the road network distance of all the
points in Q to all the points in O and then return the pair of points with the smallest
distance value of k road networks. However, if there are many object points, then the
number of pairs of points will be large, and because of the many nodes on the road
network, the cost of calculating the distance between each point and the network is
high, so this method is very inefficient.
In fact, in the above simple method, most of the distance calculation between points
is useless. The k objects closest to the query point set must belong to the kNN of
several points in the query point set. Therefore, we only need to find the kNN of each
query point one by one, and we can get the kNN of the query point set. There are many
ways to find kNN. The most common ones are Dijkstra-based algorithms and IERbased algorithms.
4 Outlook
(1) Road network dynamic update. Road network data is dynamically changed: First,
the nodes, road segments and points of interest in the road network are dynamically changed; secondly, the weight of the road in the road network is dynamically changed; in addition, both the query point and the query object may be
dynamically changed. Under the above circumstances, how to adapt to the
dynamic update of the road network data and efficiently complete the nearest
neighbor query processing is a major challenge for the nearest neighbor query
technology in the road network environment.
(2) Consider the user’s personalized query. With the wide application of locationbased services, users often have a lot of personalized location query requirements,
most of which are based on nearest neighbor queries, such as with time constraints
or A nearest neighbor query problem with keywords.
(3) Consider the road semantics. With the application of smart sensors, users can
combine the road semantic information provided by smart devices to perform
fuzzy query. For example, the background detects the road semantics through the
smartphone in real time, so that the fuzzy query of the user can obtain more
accurate results.
634
W. Jiang et al.