2 Problem Description
The road network can be expressed as an undirected graph with weights G = (V, E),
where V = (v 1 , v 2 , …, v n ) represents the set of nodes in the road network, and E represents the set of edges which connects two nodes. Each edge e can be represented as e
(v i , v j , w), where v i and v j represent the start node and the end node of the edge,
respectively, and w is represented as the distance or transit time between the two nodes.
Figure 1 shows the road network of the section of the Dalian city section, and
Fig. 2 shows the road network structure of the network section of the area. In Fig. 2,
①, ②…, respectively, represent the corresponding nodes V 1 , V 2 …. In Fig. 3, 1 , 2 …
respectively, represent the moving objects m 1 , m 2 … on the road network; in this
example, taxis, q 1 , q 2 , q 3 and q 4 are at the query point, and the query requester sends a
taxi request at the place. This type of query is an NN query. At this time, the query
result of q 1 is R = {m 11 }. If you want to query the nearest three taxis, it is a kNN query.
k = 3, the query result is R = {m 11 , m 12 , m 13 }.
Fig. 1. Regional road network of Dalian
630
W. Jiang et al.