論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――

RepresentationofTransportation Network andContinuous Nearest Neighbor
SearchJun FENG♥
Naoto MUKAI ♦Toyohide WATANABE ♠To achieve efficient processes of transportation network,
we propose a structure for integrating transportation
information with spatial information of road network.
Based on such representation, a method for searchingcontinuous nearest neighbors for a specific route in ITS
applications is proposed in this paper. Experiment showsthat our method outperforms the traditional methods.

2. Integrated Representation Method ofTransportation Network
For queries in ITS, it is important to identify certainclasses of attributes that may not be presented in roadmaps: for example, one-way road with attributes of links,
traffic constraints, information about turns between links,
or access conditions from one link to another [6]. Moreover,for some important route planning problems, the turn
costs are also considered [7] when we make a turn on across-point. A representation method for integrating
traffic and spatial information about road network is
proposed in this section.
A road network with nodes and links representing thecrosses and road segments can be regarded as an
un-directed graph G, G = (V, L), where V is a set ofvertices {v1, v2,..., vn}, and L is a collection of lines { l1, l2,...,lm}. Transportation network is regarded as a directed
graph G', G' = (V, A), where V is a set of vertices {v1, v2,...,
vn}, and A is a collection of arcs {a1, a2,..., ap}.

v3

v2

v2

♥

学生会員 名古屋大学大学院工学研究科博士後期課程
feng@watanabe.nuie.nagoya-u.ac.jp♦
学生会員 名古屋大学大学院情報科学研究科博士後期課
程 naoto@watanabe.nuie.nagoya-u.ac.jp♠
正会員 名古屋大学大学院情報科学研究科
watanabe@is.nagoya-u.ac.jp

1

v1

v4
(a)

a32
a24

a12

1. Introduction
In Intelligent Transportation System (ITS), a query ofcontinuous nearest neighbors (CNN) along a predefinedroute should be based on the transportation information
including transportation routes and current travel cost(e.g., travel time) on segments of road network. The
existing work for CNN search was almost presented fromthe computational geometry perspective [1, 2, 3]. Their
CNN search methods for line segments are effective. All
the works adopted the straight-line distance between
objects as a measure to compute CNN. However, in ITS
applications, objects can only move on the pre-definedroad network, so the distance between objects should be
decided by the shortest path length or least travel cost.
We have proposed a method [4] to solve CNN problem onroad network. By setting up search regions in the CNN
search process Dijkstra's path search algorithm [5] canfind shortest path lengths from the route to its CNN
effectively. However, because the travel cost is not always
in direct proportion to the path length, our method cannot
be applied to compute CNN using travel cost, directly. In
this paper, we propose a new method for CNN search,which takes the travel junctions (or traffic constraints)
and travel cost on road segments and turn corners into
consideration.
This paper is organized as follows. A representation
method of transportation network is proposed in Section 2.
Section 3 introduces a search method for CNN search on
the transportation network. Section 4 evaluates our
method and Section 5 makes a conclusion on our work.

v3

a23

a21

v1

v4

a14

(b)
Fig.1 Road segment and traffic arc

v3

v3

vk

v2

v4
v1

out3

v2

in3

in2

out4

vk

v4

in4

out2
in1

out1

v1
(1)

(2)

Fig.2 Cross node with constraint
Fig.1 depicts these two kinds of graphs. In the
un-directed graph of Fig.1 (a), road segments are
represented as lines; while in the directed graph of Fig.1(b), two-way roads are represented as a pair of arcs. One
line for a road segment in Fig.1 (a) may be corresponded
to two arcs in Fig.1 (b) for transportation segments in two
directions. In addition to the directions of traffic, there areusually traffic controls (constraints) on transportation
network: for example, the right-turn and U-turn are
forbidden on some cross-points. Fig.2 depicts such across-point in transportation network. In Fig.2 (1), thetransportation network is depicted by the node-link
method (proposed in [8]): each arc depicts a one-way roadand each node corresponds to a junction. To represent thetraffic constraints and turn costs, the cross-node vk is split
into four nodes and one road segment between vk and vi(i=1…4) is replaced by three arcs. The multiplication of
the nodes and links leads to a lower efficiency ofprocessing on the network. Furthermore, this kind ofrepresentation method ignores the spatial attributes ofmap objects, and only the routing queries are applicable

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
well on this model. Therefore, we propose a representation
method of transportation network by using super-node tointegrate traffic information (including traffic cost andtraffic constraints) and road network. Our method issimilar to that proposed in [9] in keeping traffic
information on nodes of road network. However, theinformation of traffic constraints and turn cost on thenodes was not discussed in [9].
A super-node can be defined as a node in the road
network: for example, vk in Fig.2 (2). The information on
the super-node contains the following parts:(a) Cost-arc: The arc which has vk as its final vertex iscalled in-arc, denoted as ini, and similarly the arc
which has vk as its initial vertex is called out-arc,
denoted as outj. The number of those arcs is called
as indegree (e.g., 4) and outdegree (e.g., 4),
respectively. Every outi is defined as a Cost-arc
which consists of the final vertex of this arc andthe traffic cost for traveling through this arc.
Cost-arcs of vk in Fig.2 (2) are out1 ( v1 , cos t k 1 ) out 2( v , cos t )
2
k2 

.
 out 3 ( v3 , cos t k 3 )  out 4 ( v4 , cos t k 4 ) (b)Constraint-matrix: The constraints on the
super-node can be represented with an n × m
matrix:

2 L m

out 1

L C1m 
K C2 m .
O M L Cnm in1  C11 C12
in 2  C21 C22
CM ( vk ) =
M  M
M

inn  Cn1 Cn 2

Cij equals to 1 when there is a restriction from ini tooutj; and Cij equals to 0 when there is a junction fromini to outj. Constraint-matrix for vk in Fig.2 (2) is:out 1 2 3 4CM ( v k ) =in1  1
in 2  1
in3  0
in 4  0

0
1
1
0

0
0
1
1

1

0
,
0

1

where there are restrictions on going from in1 to out1
and out4, from in2 to out1 and out2, from in3 to out2 andout3, and from in4 to out4 and out1.
If there is no restriction for any ini of the super-nodevk, Constraint-matrix of vk is filled with 0, and isregarded as NULL. Moreover, our method is able tomanipulate
the
turn
cost
by
extendingConstraint-matrix to a Turn-Cost/Constraint-matrix.
CM can be modified to a Turn-Cost/Constraint-matrix:
out 1

2

in1  TC11 TC12in 2  TC 21 TC 22
T _ CM ( v k ) =
M  M
M

in n  TC n1 TC n 2

L m
L TC1m K TC 2 m 
.
O
M 

L TC nm 

TCij (0 ≤ TCij < Max) is the turn cost from ini to outj.
When the turn cost equals to Max, TCij means that
there is restriction from ini to outj. For example,
Turn-Cost/Constraint-matrix for vk in Fig.2 (2) may belike this:

2

out 1

2

3

4

in1  Max 10
40 Max 
in2  Max Max 1030 
T _ CM ( vk ) =,
in3 10 Max Max 30 inn  1040 Max Max 

where MAX is defined as a large constant value.
The element TCij in this matrix with a value of MAX
represents a restriction from ini to outj: e.g., U-turn andright-turn are forbidden in this example, so MAX is
assigned to TCii (i = 1, 2, 3, 4), TC14, TC21, TC32 andTC43. The value of TC12 represents the cost 10 (e.g., 10
seconds) of making a left-turn on the cross-point (fromin1 to out2), while the cost of crossing the point vk fromin1 to out3 is 40.
This method is easy to integrate the traffic
information and the basic road network. In the basicroad network, the additional traffic information is
managed on every node. When the number of nodes andtraffic arcs is unchanged, the modification of the traffic
information does not injure the stability of the spatial
index structure (i.e., R-tree [10]) for road network.
Therefore, a kind of queries that refer to the spatial
information can be solved effectively by taking
advantages of the spatial index structure. Another kindof queries, which refer to traffic information, can also be
solved effectively by using proper methods. We centerin the following section on solving the second kind ofqueries with a CNN search example.

3. Continuous Nearest Neighbor Search
The transportation network used by our CNN search ismanaged in a dataset, denoted as super-node dataset,
which is generated by the super-node representation
method proposed in the previous section. The predefinedroute from a start point v1 to an end point vn is given by anarray Route(v1, vn) = (v1, v2, ..., vn-1, vn), and the target
object set {ta, tb, ... } is managed by a spatial index
structure (e.g., R-tree). The detailed discussions about theprocessing of target objects with respect to the advantagesof spatial index structure can be found in our previous
papers [4, 11]. We center on the super-node representation
method and its influence for CNN search. The super-nodedataset consists of information about road network andtraffic cost on the network. To make straightforward the
explanation, we use an abstract cost on road network,
which can be regarded as the travel time, toll of a pathand so on.

3.1

Observation of super-node dataset

We make observations of the super-node dataset in
CNN search:(a) Every vertex in the super-node dataset keeps thecost information of possible out-arcs, so the travel
cost from a vertex vi on Route(v1, vn) to thefollowing vertex vi+1 along this route is kept onvertex vi and denoted as vi.costi+1. If NN of vi+1 is
known as ti+1 with cost(vi+1, ti+1) the travel costfrom vi to its NN ti is not larger than a value
Cost-limit(vi) which is computed by:

Cost-limit(vi) = vi.costi+1 + cost(vi+1 , ti+1 )日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
Cost-limit(vi) is used to set a region for NN searchof vi (e.g., in Fig.3), and NN of vi can be found only
inside the dotted region. The region is defined as acircle with radius of Cost-limit(vi) and center of vi.
0

1

1

2

3

5

6

7

8

9

End: vn(Cost-arc, CM)
V42

2

V33

3
4

4

ti+1

Pi+1
Vi+1

5

td

ti
Pi

tb

ta

V43 V53

Vi(Cost-arc, CM)

(…)

6
7
8

te

tg

tf

Start:
v1(Cost-arc,
CM)

Fig.3 Predefined route and NN for vi
The nearest target object ti+1 of vi+1 is also thenearest on the possible paths from vi via vi+1. Inother words, ti+1 is the nearest one found on a pathfrom vi via vi.outi+1. If there is any object being
nearer to vi than ti+1, the shortest path from vi to it
does not pass by vi+1. Certainly, it is possible that
there is a path from vi to ti+1 via vj (j ≠ i+1), whichis shorter than Cost-limit(vi).
Conclusions can be driven from these observations:
The path length from vi to NN ti+1 of vi+1 canbe set as a limit for NN search of vi;
NN search of vi can be executed along theout-arcs of vi except for vi.outi+1.
Here, we give a simple proof for these conclusions:(a) ti+1 is a candidate of NN search of vi. Because vi
and vi+1 are along the same route Route(v1, vn),
there is an out-arc of vi leading to vi+1. Being NN of
vi+1, ti+1 can also be reached from vi via vi+1. So, ti+1
is possible to be NN of vi, too.
(b) Cost-limit(vi) is the shortest from vi to any object
via vi+1. If there is another object t' with a pathshorter than that of vi+1 via vi+1, then t' is also
nearer to vi+1 than ti+1. This contradicts to thepromise that ti+1 is NN of vi+1.
(b)

3.2

Reverse search method of CNN

We propose a method for CNN search along Route(v1,vn). This method begins from the end vertex of this route,and searches NN for every vertex in the reverse order ofthis route. Our method first searches tn for the end vertex
vn; and then generates a search limit for the nextcomputation vertex vn-1 using the previous result, andchecks whether there is an object nearer to vn-1 via theout-arcs of vn-1 except for vn-1.outn. These steps run in cycle
until the computation vertex is v1. The correctness of thismethod is assured by the previous observations.
NN search for every vertex can be realized by adopting
a priority queue to maintain the current frontier of thesearch. Any vertex with a higher cost from vi than thelimit value is not inserted into the queue. By expanding
the vertex on the head of queue, the algorithm ends when
the head vertex connects to a target object. An example for
NN search of vi is given in Fig. 3. NN of vi is to searched
only inside the dotted region. There are assumptions that3

every grid represents a unit of cost; right-turn and U-turnare forbidden on vi; and no restrictions are imposed onvertex v43. The search for vi begins from the following
possible out-arcs of vi: here, vi.out43. As there is no target
object connecting to v43, and the cost from vi to v43 is notlarger than Cost-limit(vi), the search expands the vertex
v43 using the width-first method. The vertex v42 connecting
to a target object ti with the lowest cost is found, and theobject ti is regarded as NN of vi.

4. Experimental Evaluation
Our prototype system was developed in Java on an SGI
O2 R5000 SC 180 entry-level desktop workstation (64 M
Bytes of main memory, 80 G Bytes of disk and 4 K Bytes
per page for disk I/O). The system manages basic roadmaps in a part of Aichi Prefecture, Japan. Evaluations are
made using the transportation network generated bysuper-node method (denoted as SN) and node-link method(denoted as NL). The basic road map is indexed by R-tree.
The targets used in our test are point objects with uniform
distribution on the road network, which is managed byanother spatial index. The number of targets is varied
from 3% to 12% of the nodes on the road network.
The size of a record of super-node (i.e., a cross node onroad network, with four (vi, cost) and 16
Constraint-matrix elements) is 72 Bytes (4 * (6 + 8) + 1 *16), which leads to 56 records per disk page. In NL
method, the record for road segment is (from-node,
to-node, weight), which is 24 Bytes (8 * 3) and leads to 170
records per disk page. The total number of nodes Nnum is42,062 and number of links Lnum is 60,349 in the basicroad map. The average traffic arcs connecting to a node isabout 2.87 (=2 Lnum / Nnum). When there is no traffic
constraint for the basic road map, in NL method, there are120,798 records (two times of the link numbers in roadmaps). As in SN method, the amount of information isrelated to the number of arcs in every node: here, thenodes with four, three, two and one out-arcs are about 24:
51: 13: 12. The total arcs managed in SN method are
120,798. When there are traffic constraints, Right-turnand U-turn are forbidden in about half of the cross andT-junction points. Then in NL method, there are about
142,423 nodes (more than three times of that in SN
method); and 135,293 arcs (more than two times of than in
SN method). The situations are depicted in Fig. 4. The
datasets generated by SN method shares the same value
in Fig.4, which is denoted simply as SN method, because
the number of objects keeps the same. On the contrary,
there are different values for different conditions of thedatasets in NL method. “Constraint” means there aretraffic constraints in the dataset.
CNN test results are given in Fig. 5. In the figure,x-axis represents the density of targets on the road
network, which is the ratio of the targets' number (Tnum)
to the nodes' number (Nnum) in basic road map; y-axis
represents the CPU time of NN search for every
computation-point on the predefined route. D represents
that CNN search is done by adopting Dijkstra's algorithm
for NN searches. When the traffic cost is set as the lengthof road segment, NN search is done inside a proper searchregion, which is a circle just like one generated in Section
3; and R represents the reverse search method proposed

日本データベース学会 Letters Vol.2, No.3

論文
DBSJ Letters Vol.2, No.3――――――――――――――――――――――――――――――――――――
in this paper. D algorithm is executed on the datasets
generated by NL method with/without constraint (thenumber of objects is depicted in Fig. 4); and R algorithm isdone on the dataset generated by SN method with/without
constraint.
150000
Number of objects

Arc
1000000
SN_methodNL

NL_Constraint

Methods

Fig.4 Numbers of arcs and nodes
managed by SN and NL methods
700
NL_D_Constraint
NL_D
SN_R
SN_R_Constraint

CPU time (ms)

600
500
400
300
200
100
0
0.06

0.09

0.12

Ratio of Tnum to Nnum

Fig.5 Average CPU time of finding one target
in CNN search
In Fig. 5, we can observe that: when the searches are on
the datasets without constraint, SN_R method is about
1.7 to 2.6 times faster than NL_D method; when there aretraffic constraints managed in the datasets, SN_R
(Constraint) method is about 5 to 14.4 times faster than
NL_D (Constraint) method. This is because:(a) In our method, NN search only expands the nodes onroad map in possible directions when there is any
traffic constraint on the node. With our reverse CNN
search method, one or more possible directions are
decreased, and the following nodes on that directionneed not to be tested. The search cost is shrunken.
(b) In NL_D method, Dijkstra’s algorithm is executed
inside a proper search region. Therefore, NN search
process includes the steps of generating searchregions, creating distance matrices for networks
inside the search regions and the path searches byusing Dijkstra’s algorithm based on the matrices. The
cost of matrix creation and path search is related to
the number of nodes and arcs in the search region.
When there are any traffic constraints, the number ofnodes and arcs is increased; and the cost is increased,accordingly. The search region can be generated only
when there are direct relations between the travel
cost and the length of road segment. So, thecomparison is only done on this assumption. In othersituations, the search region cannot be created easily
for NL_D search and our method is much faster than
NL_D method.

4

In this paper, we proposed a super-node structure for
integrating traffic information with spatial information ofroad network. Because by using this structure, traffic
information is embedded in the spatial structure created
for road network, the queries, which refer to spatial
information and traffic information, could be solved more
efficiently than other methods. Experiments on CNN
search confirmed it.

[文献]

Node
50000

0.03

5. Conclusion[1] Y.F. Tao, D. Papadias and Q.M. Shen: “Continuous Nearest
Neighbor Search”, Proc. of VLDB'02, pp. 287-298 (2002).
[2] Z.X. Song and N. Roussopoulos: “K-Nearest Neighbor Searchfor Moving Query Point'', Proc. of SSTD'01, pp. 79-96 (2001).
[3] S. Bespamyatnikh and J. Snoeyink: “Queries with Segments
in Voronoi Diagrams'', SODA (1999).
[4] J. Feng and T. Watanabe: “A Fast Method for Continuous
Nearest Target Objects Query on Road Network”, Proc. of
VSMM'02, pp. 182-191 (2002).
[5] N. Christofides: “Graph Theory: An Algorithmic Approach'',Academic Press Inc. (London) Ltd. (1975).
[6] M. F. Goodchild: “GIS and Transportation: Status andChallenges”, GeoInformatica, Vol.4, No.2, pp. 127-139 (2000).
[7] S. Winter: “Modeling Costs of Turns in Route Planning”,
GeoInformatica, No.4, pp. 345-361 (2002).
[8] J.Fawcett and P.Robinson: “Adaptive Routing for Road
Traffic”, IEEE Computer Graphics and Applications, Vol.20,
No.3, pp. 46-53 (2000).
[9] D. Papadias, J. Zhang, N. Mamoulis and Y.F. Tao: “Query
Processing in Spatial Network Databases”, Proc. of VLDB 2003,
pp. 802-813 (2003).
[10] A. Guttman: “R-Trees: A Dynamic Index Structure for
Spatial Searching”, Proc. of ACM SIGMOD'84, pp. 47-57(1984).
[11] J. Feng and T. Watanabe: “A Fast Search Method of Nearest
Target Object in Road Networks”, Journal of the ISCIE, Vol. 16,
No. 9, pp. 484-491 (2003).

Jun FENG
名古屋大学大学院工学研究科博士後期課程在学中．1994 中
国河海大学コンピュータ学院修士課程修了．地理情報システ
ム、空間データベースシステムと空間検索の研究・開発に従事．情報処理学会学生会員．日本データベース学会学生会員．

Naoto MUKAI名古屋大学大学院情報科学研究科博士後期課程在学中．2003
名古屋工業大学大学院工学研究科博士前期課程修了．地理情報システムと高度交通情報システムの研究・開発に従事．情報処理学会学生会員．日本データベース学会学生会員．

Toyohide WATANABE
名古屋大学大学院情報科学研究科教授. 1972 京都大学理学部卒業．1975 同大学工学研究科博士課程中退。工学博士．
統合化環境、分散協調環境、データベース環境、学習支援シ
ステム、文書理解に興味を持つ．情報処理学会、電子情報通信学会、日本ソフトウェア科学会、人工知能学会、システム
制御情報学会、教育システム情報学会、ACM、IEEE-CS、
AAAI、AACE 各会員。

日本データベース学会 Letters Vol.2, No.3