DEIM Forum 2013 D8-3

時変重みを持つ道路網上のモバイル k NN 問合せ
藤野 友輔†

上島 紳一†† 関西大学総合情報学研究科 〒 569-1095 大阪府高槻市霊仙寺町 2-1-1
E-mail: †{k674609,ueshima}@kansai-u.ac.jp
あらまし

近年，空間ネットワーク上での空間探査を伴う問合せ処理の研究が進められている．これらの研究では，

空間索引を用いて探査空間の刈込み手法を用いた効率的な問合せ処理方法が提案されている．しかし，通常，オブジェ
クトは移動し，ネットワークは時間に依存したトラフィックにも影響を受けるため，これらの空間索引を直接適用す
ると計算量が極端に増大し，現実的な時間では実行できない．このため，本稿では，モバイルオブジェクトを対象として，空間ネットワークを再構成して絞り込む問合せ処理法を提案する．提案手法では，各オブジェクトの移動範囲を設定して，オブジェクトまでの移動コストの上下限を予め算出し，質問点に対する近傍候補を絞り込む 2 種類のセルを生成して，時変ネットワーク上のオブジェクトに対して効率的な kNN 探査を可能にする手法を提案する．提案
手法の評価として，道路ネットワークを摸して生成したネットワークへ適用して数値特性の確認を行ない，更に，数値地図を用いた現実の道路網での有効性を検証する.
キーワード

kNN 探査, 移動体, 空間分割, 空間データベース, 時変重み付きエッジ, 数値地図, 道路

A Network Reconstruction Approach for Mobile k NN Queries on
Time-dependent Road Networks
Yusuke FUJINO† and Shinichi UESHIMA†† Graduate School of Informatics, Kansai University
2-1-1,Ryouzenji, Takatsuki, Osaka, 5691095 Japan
E-mail: †{k674609,ueshima}@kansai-u.ac.jp
Abstract Recently much attention has been focused on spatial query processing schemes over road networks.
On static networks, the use of spatial indices, such as distance indices, regional adjacency indices based on spacepartitioning, provides eﬃcient processing schemes that prune search space for spatial queries, such as kNN, RkNN,
etc. On the other hand, these indices are not directly applicable to practical road networks, where their traﬃcs aretime-dependent. To cope with this problem, a new scheme for spatial query processing is proposed for mobile objects
by using network reconstruction. In our approach, assuming moving areas of mobile objects, upper/lower-boundmoving costs to objects are calculated in their areas beforehand, and two types of cells are generated as neighborhoods of mobile objects. By use of this preprocessing, an eﬃcient query processing algorithm is proposed against
kNN over time-dependent networks. Numerical simulations are also provided for investigation of this scheme on
both time-dependent road networks and digital road maps with simulated traﬃcs as practical settings.
Key words kNN, mobile object, spatial partitioning, spatial database, time-dependent network, digital road map

1. は じ め に求める問合せである [1]．しかし kNN 探査処理に必要な道路網
データは膨大であり, サーバーでの処理にて実行する端末数が近年，オンラインマップサービスの進展や高性能な携帯型端増加するとサーバー自身への負荷も増加する．そこで空間ネッ

末の普及により，位置情報を用いたサービスに注目が集まってトワーク上での空間探査を伴う問合せ処理の効率化に関する研いる．この位置情報を用いたサービスの中で，最も需要が高い

究が進められてきた [2] [3]．

問合せは，道路網から病院やレストラン等のオブジェクトに対これらの研究では空間ネットワーク上に存在するオブジェクする k 近傍探査 (kNN) と，その目的地点への所要移動時間を

トは固定されてモデル化されている場合が多く，モバイルオブジェクトへの kNN 探査において適用出来ない．これはモバイ

全てのエッジにおいて，時刻 t におけるエッジ ei の重みを返

ルオブジェクトは位置が変化するものであり，これにより同一す関数 f (ei , t) があり，各エッジはこの関数 f により，移動開の質問地点であっても近傍が変化するためである．この例を図

始時刻に対応する移動時間が重みとして定められる．ここでは，1 へ示す．そこで，モバイルオブジェクトに対して空間索引を

t = [0, 24] に対して，ei の持つ移動時間の最大値を上限値とし生成し kNN 探査を効率的に行なうための種々な手法が提案さて eimax ，最小値を下限値として eimin とする．これらは時間れている [4]．

独立な 2 つの重みである．エッジの時間依存重みの遷移の例を

本来現実世界でのネットワークでは，時刻によりトラフィッ

図 2 に示す．

クが変化するため，エッジが時変重みをもつ空間ネットワーク[定義 3] 上限移動時間と下限移動時間

である時間依存空間ネットワークとして考える必要がある．し

G 上で出発地点を s，到着地点を d とする時，各エッジのかし時間依存空間ネットワークに対し単純に既存のアルゴリズ

eimax を用い s から d への合計移動コストが最小となる経路

ムを適用させると，計算量が極端に増大し，現実的な時間ではを通った際，その合計移動コストを上限移動時間 (U T T ) とす

実行できない．

る．また各 eimin を用い，s から d への合計移動コストが最小

本稿では，現実の道路網上での問合せを想定し，時間依存となる経路を通った際，その合計移動コストを下限移動時間

空間ネットワーク上でのモバイル kNN 問合せに焦点を絞る．

(LT T ) とする．これら U T T ,LT T を以下のように定義する．

Demiryurek らは時間依存ネットワーク上での kNN 探査手法 [5]経路内の各移動コストが eimax をとった際の s から d への合計を提案した．この Demiryurek らが提案した手法に対し，本提移動コストが最小となるエッジ列をダイクストラ法にて求め，案手法を組込むことによりモバイルオブジェクトへの kNN 探

e1 , e2 , ..., ek とした時，査に対応させる．移動するオブジェクトまでの取り得る移動コ

U T T (s, d) =ストを予め算出し，その値を用い空間ネットワーク内の部分
ネットワークの再構成を行なう．この再構成されたネットワー
クにより，近傍候補を絞り込む 2 種類のセルを空間索引として生成する．これにより時間依存空間ネットワーク上のモバイル
オブジェクトに対し，生成された空間索引を用い効率的に kNN

k
∑

eimax

(1)

i=1

また，同じ様に経路内の各移動コストが eimin をとった際の合計移動コストが最小となるエッジ列を e1 , e2 , ..., ek とした時，

LT T (s, d) =

k
∑

eimin

(2)

i=1

探査を実行する手法を提案する．
更に道路ネットワークを摸して生成したネットワークへ提案となる．s から d までの合計移動コストが最小となる経路を通っ手法を適用することにより数値特性の確認を行なう．また実際た際，その合計移動コストはどの時刻においても必ず U T T (s, d)の道路網での有効性を確認するため，国土地理院発行の数値地と LT T (s, d) の間となる．この時，eimax と eimin は時間に対図上にトラフィックをモデル化してネットワークを生成する．

して独立であり，各ノードへの到着時刻に影響されない．

このネットワークに対し提案手法を適用し，定量的に評価する．

[定義 4] モバイルオブジェクト

更に，複数端末間の連携環境でのセルの生成時間と探査時間にモバイルオブジェクト Oi は自律的に移動し，移動先の状況

ついても評価し，議論する.

に合わせ振舞いを変化させる．そこで，Oi が存在する位置は固2 章では時間依存ネットワークと対象となるモバイルオブジェ

定ではなく，G 内のノード集合 V 上を移動するものと考える．

クトの性質について述べる．3 章では部分ネットワークの再構

この Oi が位置する可能性がある部分ネットワークを Ri と定成を述べ，4 章ではそれを用いた空間セル生成アルゴリズムつ義する．

いて述べる．5 章では時間依存空間ネットワーク上でのモバイ

Ri は予め定められており固定されているものとし，Oi は必

ルオブジェクトへの kNN 問合せと，近傍地点までの経路探査

ず Ri に含まれているノードのいずれかの上に存在するものとアルゴリズムについて述べる．6 章と 7 章にて数値シミュレー

する．この時，Oi の位置 (Oi .x, Oi .y) は他の Oi の位置に依存

ション実験により手法の評価と検討を行う．

せず，Ri は重なり合ってもよい．これにより，Ri はそれぞれ

2. 準

備

独立に設定することが可能である．

2. 2 空間探査問題

2. 1 空間ネットワーク[定義 5] 時間依存最小移動時間経路[定義 1] 時間依存ネットワーク

エッジの重みが時間に依存する為，G では各ノードの出発時

道路網において，交差点をノード，道路片をエッジと見なし

刻及び到着時間を考慮する必要がある．目的地までの移動コス

た有向ネットワーク G(V, E),(V :ノード集合,E ⊂ V × V :エッ

トは，各ノードへの到着時刻に応じた移動コストを用いて求めジ集合) を考える．さらに，各エッジは時間に依存した，負でていく．

ない重みを持つものとし，時間の関数により重みが定められる．

問合せの発行時刻を ts とした時，出発地点 s から到着地点 d

各ノード v は 2 次元での座標 (v.x, v.y) を持つ．また，モバまでの時間に依存する移動コスト T T (s, d, ts ) は次の式の様に

イルオブジェクト Oi と，それらの k 近傍を探査しているクエ
リ q の質問地点はこの G のノード上に存在している．

[定義 2] 時間に依存したエッジの重み算出される．

T T (s, d, ts ) =

k
∑
i=1

f (ei , ti )(3)

そこで，W C と BC を求め，Ri の再構成をおこなうことにより,Ri 内の Oi の位置推定を大規模計算に置き換える．次に述べ
る W C と BC の算出とそれを用いた部分ネットワークの再構
成処理は各々の Ri 毎に独立しており, 並列処理が可能である．

3. 2 W C と BC の算出
W C は p から Oi までの最小移動コストが一番大きくなる状(a) 12 時時点

況の値であり，また BC は p から Oi までの最小移動コストが(b) 14 時時点

一番小さくなる状況の値である．Ri に含まれる任意のノード r

図 1 近傍オブジェクトの変化
Time Dependent Edge Weightからオブジェクト Oi までの W C 及び BC は次のようになる．

35
f(ei,t)
eimax
eimin

30

BC(r, Oi ) = min{LT T (r, x)}
W C(r, Oi ) = max{U T T (r, x)}weight(sec)

25

(6)

where x ∈ Ri .

20
15

また，Ri の境界ノード集合を Bi とした時，任意の時刻 ts で

10の Ri に含まれない任意のノード n から Oi までの時間依存な

5

最短移動コスト T T (n, Oi , ts ) は次のように定義することがで
0
00:00

03:00

06:00

09:00

12:00
Time

15:00

18:00

21:00

24:00

きる．

T T (n, Oi , ts ) = min{T T (n, x, ts )図 2 時間依存エッジ重み f (ei , t)

t1 = ts , ti+1 = ti + f (ei+1 , ti ).

(4)+T T (x, Oi , ts + T T (n, x, ts ))}where x ∈ Bi .

ここでエッジ ei は，到着時刻 ti でのエッジの重みを用いて，合計移動コストが最小となる経路を辿るように展開される．これ
により s から d まで展開されたエッジ列が時間依存最小移動時
間経路となり，その際の合計移動コスト T T (s, d, ts ) が時間依存な最短移動コストとなる．

[定義 6] 時間依存モバイルオブジェクト kNN 探査の問題(7)

これにより時間に依存しない値である U T T 及び LT T を用い
ると n の BC 及び W C は次のように求めることができる．

BC(n, Oi ) = min{LT T (n, x) + BC(x, Oi )}W C(n, Oi ) = min{U T T (n, x) + W C(x, Oi )}(8)

where x ∈ Bi .

G において kNN 探査問題の結果は，q の発行時刻に大きく影響される．これは，時刻により G 上のエッジの重みと，Oi

これらにより，事前に Ri に含まれるの全てのノードに対しての位置関係が変化するためである．この q の発行時刻が結果に

W C 及び BC を求めておく事によって G 上の全てのノードの影響を与える例を図 1 に示す．

W C 及び BC を容易に求めることが可能になることが解る．そ

図 1 では，q の発行地点が同じであっても出発時刻の違いに

こで，Ri に含まれるノードの W C,BC を求めるべく Ri に含より近傍の Oi が変化している．これは，Oi の位置の変化によまれる任意のノード n1,n2 に対して G 上で全点対最短経路問

り q から Oi までの距離が変化することに加え，エッジの重み

題 [7] を解く．これにより求められた移動コストの最大値がそも変化しているためである．このため, もし q と Oi の位置が同のノードから Oi への W C となる．BC はそのノード上に Oi

じであっても，q の発行時刻が違えば近傍の Oi が同一であるが存在する場合となるので，常に 0 となる．

とは限らない．これらの要因より，モバイルオブジェクトが存在する時間依存ネットワークでは事前にオブジェクトまでの距離を求める方法は用いれない．

3. 3 再 構 成
W C と BC を用い Ri の再構成をおこない，Ri の上位層となるネットワーク R̂i を生成する．初めに Ri に含まれるノード集合と，Ri 内部から外部へ向かうエッジ集合を R̂i へと複写

3. 部分ネットワークの再構成

する．そして，Oi に対応する仮のモバイルオブジェクト Ôi を
ここでは，G の部分ネットワーク Ri の再構成について述べる．

R̂i 上の任意の位置に生成する．この Ôi から Ri に含まれる全てのノードに対して，有向エッジ ei を生成する．この時，ei は

3. 1 モバイルオブジェクトへの移動時間

宛先ノードの W C と BC の二つの値を重みとして持っているG において，Ri は固定である．これにより任意のノード p か

可変の重み付きエッジとする．

ら Oi までの最小移動コストの上限値である WorstCost(W C)

この例を図 3 に示す．図 3(a) は元となる Ri を示しており，と下限値である BestCost(BC) を定義することが可能である．

図 3(b) では，その Ri を元に再構成をおこなった上位層ネット

つまり，Oi が Ri 上のどのような位置にいても，p から Oi へ

ワーク R̂i を示している．

の最小移動コストは必ずその W C と BC の間の値となる．任意の時刻 ts での任意のノード p から Oi への W C 及び BC を

4. 二種類のセル生成

次のように定義する．

ここでは，R̂i と式 (1) 式 (2) を用いて，G 上でのモバイルオ

W C(p, Oi ) <= T T (p, Oi , ts ) <= BC(p, Oi ).

(5)(a) 部分ネットワーク Ri(b) Ri の上位層ネットワーク(a) 必 ず 一 番 近 く な る セ ル(b) 一番近くなる可能性がある

C(Oi )

セル Ĉ(Oi )図 4 二種類のセル

R̂i

図 3 部分ネットワークの再構成

この処理を各モバイルオブジェクトに対し繰り返し，一番近く

ブジェクトへの kNN 問合せを効率化するために生成する二種なる可能性があるセル Ĉ(Oi ) を生成する．これは，C(Oi ) 生成

類のセルについて述べる．

時の W C と BC ，U T T と LT T を入れ替えたものであると言え

4. 1 必ず一番近くなるセル

る．Ĉ(Oi ) は，Oi が任意の時刻で 1-NN となる可能性があるノー

G 上にオブジェクト集合 O = {O1 , O2 , O3 , ...} が与えられたドの集合である．言い換えれば，Ĉ(Oi ) 外のいかなるノードも時，Oi が必ず一番近くなる空間セル C(Oi ) をC(Oi ) = {V |W C(V, Oi ) <| j}= BC(V, Oj ), i =1-NN として Oi を持つ可能性はない．Ĉ(O1 ), Ĉ(O2 ), ..., Ĉ(On )(9)5 つのモバイルオブジェクトに対して Ĉ(Oi ) の生成を行ったと定義する．

C(Oi ) は，Oi に対応する仮のモバイルオブジェクト Ôi から
並列ダイクストラ法 [6] を展開することにより生成される．この際に生成対象となる Ôi からの展開時には，W C または U T T
を用い展開し，残りの他の Ôi からの展開には BC または LT T
を用い展開する．この時，上位層ネットワーク R̂i のノードと，その直下に存在する下位層ネットワークのノードは展開コストを共有するものとする．これにより生成対象オブジェクトの Ôi

例を図 4(b) に示す．

q の質問地点が複数の Ĉ(Oi ) 内に含まれている場合は，それら複数の Ĉ(Oi ) に属しているオブジェクト集合に対して，出発時刻に依存した移動時間を求める必要がある．

5. 時間依存モバイル kNN 問合せ処理
5. 1 時間依存 A*アルゴリズム
時間依存モバイル kNN 問合せ処理では，時間依存最小移動から展開された領域が C(Oi ) となる．
この処理を各モバイルオブジェクトに対し繰り返し，必ず一番近くなるセル C(Oi ) を生成する．C(Oi ) は，Oi が任意の時刻
で 1-NN となるノードの集合である．C(O1 ), C(O2 ), ..., C(On )時間経路とその移動コストを求める為に，A*アルゴリズムを拡張し用いる．G においての時間依存最小移動時間経路は，各ノードへの到着時刻でのエッジの重みを用いて展開していくことにより求めることができる．しかし，大規模な G 上では全ては互いに排他的である．

5 つのモバイルオブジェクトに対して C(Oi ) の生成を行ったのノードを展開するのは現実的では無く，計算領域を刈り込む必要がある．そこで，A*アルゴリズムのヒューリスティックな例を図 4(a) に示す．

q の質問地点がこの C(Oi ) 内に位置する場合は，常に所属する Oi が 1-NN となる．この場合には，高コストである時間依
存最小移動時間経路の計算を省略し，1-NN を求めることが可関数を使うことにより，アクセスする必要があるノードの刈りこみを行う．
エッジの長さがコストと考えられる通常の空間ネットワーク
では，ユーグリッド距離をヒューリスティック値として使うと能となる．

こができる．しかし，G では，全ての可能な出発時刻において，4. 2 一番近くなる可能性があるセル
G 上にオブジェクト集合 O = {O1 , O2 , O3 , ...} が与えられた
時，Oi が一番近くなる可能性がある空間セル Ĉ(Oi ) を| j}
Ĉ(Oi ) = {V |BC(V, Oi ) <= W C(V, Oj ), i =はそれぞれ他の一つ以上の Ĉ(Oi ) と重なりあう．

(10)と定義する．

決して実際の値が下回らない値をヒューリスティック値として選択することが必要である．この単純な値はユークリッド距離を全領域内での最大上限速度で割ったものである．しかし，この方法では刈り込み量は微量となり，あまり効果を望めない．
そこで，オブジェクトへの時間依存最小移動時間経路は必ずそĈ(Oi ) は，Oi に対応する仮のモバイルオブジェクト Ôi からのオブジェクトの属する Ĉ(Oi ) から出ない性質を利用する．

並列ダイクストラ法を展開することにより生成される．この際これにより分母を Ĉ(Oi ) 内のみでの最大速度とした値をに生成対象となる Ôi からの展開時には，BC または LT T を

ヒューリスティック値とすることができ，ノードの展開範囲を用い展開し，残りの他の Ôi からの展開には W C または U T T

大幅に刈り込みことができる．質問地点が宛先オブジェクトのを用い展開する．この時，上位層ネットワーク R̂i のノードと，Ĉ(Oi ) 内に位置しない場合においては，宛先オブジェクトが含その直下に存在する下位層ネットワークのノードは展開コスト

まれる Ĉ(Oi ) まで，隣接する Ĉ(Oi ) を展開していく．これらを共有するものとする．これにより生成対象オブジェクトの Ôiˆ i ) となる．
から展開された領域が C(Oの展開された Ĉ(Oi ) 内での最大速度を分母とした値をヒューリスティック値とし，出発時刻に依存した時間依存最小移動時間
経路の探査とその移動コストの計算を行う．

5. 2 時間依存モバイル kNN 問合せ処理
時間依存モバイル kNN 問合せ処理では，初めに生成した 2
種類のセル C(Oi ), Ĉ(Oi ) を用い,1 − N N を見つけ，そこから，

k − 1 個の近傍を探すように Ĉ(Oi ) を展開してゆく．
まず初めに，q の質問地点の 1-NN を識別する為に，C(Oi )または Ĉ(Oi ) を使用する．q の位置が与えられると，初めにそのノードが位置している C(Oi ) を探す．C(Oi ) 内に位置しているのであれば，その C(Oi ) に属している Oi が，この q の1-NN となる．どの C(Oi ) にも位置していなければ，位置している複数の Ĉ(Oi ) から 1-NN を探すことになる．従い，この場
合では，1 − N N を決定するために，q が位置する Ĉ(Oi ) に属している Oi に対しクエリ発行時点での位置を問合せ, それらに対して時間依存な最小移動コストを求める．この際に前述の時
間依存 A*アルゴリズムを用いる．これにより，求めた移動時間が最小となるオブジェクトが 1-NN となる．
残りの N N を見つけるには，隣接している Ĉ(Oi ) を展開していくことにより行なう．残りの N N は，既に確定した N Nが属している Ĉ(Oi ) に隣接している Ĉ(Oi ) に存在することが保証されている．そこで，隣接している Ĉ(Oi ) を展開し，属している各々の Oi のクエリ発行時点での位置を問合せる．q から
それらの地点に対して出発時刻に依存した最小移動コストを求
め, この移動コストが一番小さい Oi が次の N N となる．これを k 個満たすまで繰り返すことにより時間依存モバイル kNN
問合せ処理を行なう．
このように，C(Oi ) と Ĉ(Oi ) を用い N N の候補を絞ることにより，Oi の位置問合せと, 出発時刻に依存した最小移動コス
トを求める回数を減らし，効率的に N N を見つけることができる．これにより，計算量とアクセス数の削減を行うことが可能となる．

6. 生成データに対する数値シミュレーション評価
6. 1 対象データ
プログラムにより道路地図を摸して自動的に生成したネット
ワークを用い，本稿で述べた G におけるモバイル kNN 探索と
時間依存最小移動時間経路探索の性能評価と検討を行う．
対象データとして，モバイルオブジェクト数を固定しノード数を変化させたネットワークと，ノード数を固定しモバイルオ
ブジェクト数を変化させたネットワークを生成する．この際にモバイルオブジェクトの移動範囲は，ランダムに決定された出発地点から最短移動経路に沿って移動した際に 1.2km 以内であるノードを移動範囲としている．
また各ネットワークは，エッジの重みが固定の通常ネットワー
クと，エッジの重みが時間依存な時間依存ネットワークの二種類を生成する．それらにネットワークに対し提案手法を適用し，特性の確認を行う．
通常ネットワークではエッジの距離をエッジの重みとする．
時間依存ネットワークでは，距離を 30〜50 の間のランダムな速度で割った値を重みとして 5 つ作成し，その重みを 24 時間

ノード数が変化オブジェクト数が変化

ノード数

500〜1500 (500 単位で増加)

7500

エッジ数

ノード数× 215000

72〜60 (2 単位で増加)

オブジェクト数
エッジの重み距離または距離/30〜50 のランダムな速度

オブジェクト移動範囲

片道 1.2km 圏内

表 1 生成ネットワークの詳細周期になるよう繋ぎ合わせる事により，時間に依存したエッジの重みとする．この生成データの詳細を表 1 に示す．
本実験では，FX-8150@3600MHz の 8 コア CPU，16GB メ
インメモリといったスペックの PC 上にてプログラムを実行し，データの測定を行う．また分散処理評価の際には，CPU の 1
コアを一つの端末と見立て処理を分散させ評価を取る. 本稿で述べたアルゴリズムを実装したプログラムは C++言語にて作成したネイティブプログラムとなっており，分散処理可能な部
分のみがマルチスレッドとなっている.

6. 2 評 価 方 法
ここでは，自動的に生成された通常道路ネットワークと，時間依存ネットワークの二種類のネットワーク上にてセルの生成と kNN 探査の評価を行う．
セルの生成に関しては，部分ネットワークの再構成とそれを用いた二種類のセル生成を合わせた実行時間をセルの生成速度として評価する．また，処理の分散の効果に関しても評価を行う．セルの生成時間評価では，10 回のセル生成を繰り返し，その実行時間の中央値を評価する．また，処理の分散の評価では同じ環境にて，CPU の使用コア数を変更し評価する．

kNN 探索に関しては，質問地点となるノードをランダムに選出し，その地点から 1-NN,3-NN,5-NN の探索と，それら NN
までの最小移動時間経路の探索を行なう．この時，時間依存
ネットワーク上での探索開始時刻はランダムな時刻を設定する．
また，モバイルオブジェクトの位置は，クエリ発行時に毎回移動範囲内のノードをランダムに選出し決定するものとする．これらの処理を 30 回行い，その実行時間の中央値を評価する．

6. 3 データ特性によるセルの生成速度への影響
データの特性によるセルの生成速度への影響を評価する．通常ネットワーク並びに時間依存ネットワーク上での，ノード数に対するセルの生成時間の変化を図 5 へ示す．また，モバイル
オブジェクト数に対するセルの生成時間の変化を図 6 へ示す．
図 5 の結果からセルの生成コストは，ノード数の増加に伴い指数関数的に増加することが見て取れる．これはノード数の増加に伴いセル生成時に行うパラレルダイクストラ処理の展開数が指数関数的に増加するためである．また図 6 の結果からセルの生成コストはモバイルオブジェクト数に比例して増加することが見て取れる．これは，モバイルオブジェクトの増加に伴い，部分ネットワークの再構成と，セル生成時のパラレルダイクス
トラ処理を行う回数が比例して増加するためである．これら二つの結果から，時間依存ネットワークと通常ネットワークはほぼ同コストにてセル生成処理が可能なことが見て取れる．これは，部分ネットワークの再構成及びにセルの生成は時間依存
ネットワークであっても，時間に依存しない重みである U T Tと LT T を用い処理するためである．また，これらの結果から

CreateCell

CreateCell

25

Distributed processing CreateCell (Time-dependent Networks)

60

25

Normal Networks
Time-dependent Networks

Normal Networks
Time-dependent Networks

1 Distributed
2 Distributed
3 Distributed
5 Distributed
8 Distributed

50
20

20

40
Time(sec)

Time(sec)15

Time(sec)

15
30

10

10
20

5

5
10

0

0
0

2000

4000

6000

8000
Node

10000

12000

14000

0
0

図 5 生成ネットワークにおける

10

20

40

50

60

0

図 6 生成ネットワークにおけるノード数に対するセルの生成時間

Time(msec)

Time(msec)

10

1

1

0.1

10

0.01

0.01

0.001
20

30
MobileObject

40

50

60

図 8 時間依存ネットワークにおける

14000

1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

100

0.1

10

12000

kNN processing (Normal Networks)

20

0

10000

1000

10

30

8000
Node

ノード数対するセルの分散生成時間

1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

100

40

6000

図 7 時間依存ネットワークにおける

1000
1 Distributed
2 Distributed
3 Distributed
5 Distributed
8 Distributed

0

4000

kNN processing (Normal Networks)

60

50

2000

オブジェクト数に対するセルの生成時間

Distributed processing CreateCell (Time-dependent Networks)Time(sec)

30
MobileObject

0.001
0

図9

オブジェクト数に対するセルの分散生成時間

2000

4000

6000

8000
Node

10000

12000

14000

通常ネットワークにおけるノード数に対する kNN 探査時間

セルの生成コストは非常に大きいことが見て取れる．しかし，

0

図 10

10

20

30
MobileObject

40

50

60

通常ネットワークにおけるオブジェクト数に対する kNN 探査時間

散処理をさせないようにすることが望ましいと考えられる．

実行はセル作成時の一度のみであるため，運用時への影響は小6. 5 データ特性による kNN 探査速度への影響

さい．また，ノード情報更新時のセル再構成に関しては，比較生成されたセルを用い kNN 探査を行なった場合と，セルを的小さいコストにて再構成可能である．これは，更新があった

用いず時間依存 A*探査のみを用いて kNN 探査を行った場合とノードに接続されているノードが所属しているセルと，それにの処理時間の比較を行う．この比較により，セルの利用による

隣接しているセルに対してのみ再構成の処理を行えばよいため実行速度への影響の検証を行う．

である．

通常ネットワーク上において 1-NN,3-NN,5NN を求めた際の

6. 4 分散処理によるセルの生成速度への影響

ノード数に対する実行時間の結果を図 9 へ，モバイルオブジェ

部分ネットワークの再構成及び二種類のセル生成は，それぞ

クト数に対する実行時間の結果を図 10 へ示す．また時間依存れの領域が独立して生成することが可能であり，処理を分散さ

ネットワーク上にて 1-NN,3-NN,5NN を求めた際のノード数にせることが可能である．そこで，セルの生成処理を分散させる

対する実行時間の結果を図 11 へ，モバイルオブジェクト数にことによる，セルの生成速度への影響を評価する．

対する実行時間の結果を 12 へ示す．

時間依存ネットワーク上でのノード数に対する分散数 1,2,3,5,8

この結果から，セルを用いた場合は，セルを用いない場合にでの実行速度の変化を図 7 へ，モバイルオブジェクト数に対す

対し，全体的に低い処理コストにて，kNN 探査を行える事がる実行速度の変化を図 8 へ示す．今回通常ネットワークと時間確認できた．またセルを用いない場合では，求める NN の数に依存ネットワークでの結果はほぼ同位であったため，通常ネッ

拘わらずノード数やモバイルオブジェクト数の増加に合わせ処

トワークでの結果は省略する．これらの結果から，ノード数の理時間も増加しているが，セルを用いる場合では求める NN の増加やモバイルオブジェクト数の増加に拘わらず処理の分散化

数により変化することが見て取れる．これは，セルを用いないが有用であることが確認できる．これはモバイルオブジェクト

場合は全てのモバイルオブジェクトに対して最小移動コストを一つ一つの部分ネットワークの再構成及びセル生成の処理が完求める必要があるのに対し，セルを用いる場合は NN の候補を全に独立して処理可能なためである．

絞ることができるためである．特に 1 − N N を求める際は，候しかし処理コストが元から小さい状況では，分散処理の有効補となるオブジェクトが少ない傾向にあるため，際立って低い性は僅かしかみられない．これは，分散により削減される処理

処理コストにて実行できている．また，これらの結果からノーコストと，分散処理を行う為の処理コストの差が小さいためでドの増加時よりもモバイルオブジェクト数の増加時の方がよりあると考えられる．そのため，端末間で分散処理を行うための効果を発揮していることが確認できる．これは，モバイルオブ

処理コストが高いような状況であれば，分散処理を行うことでジェクト数が増えるほど全体に対する NN 候補となるオブジェ

処理コストが余計にかかってしまう可能性もある．これらの理

クト数の割合が小さくなるためである．

由から，セルの生成コストが大きいであろうネットワークでの

通常ネットワークに比べ，時間依存ネットワークでは時変エッ

セル生成の際は分散処理を行い，処理コストが僅かな場合は分ジ重みの影響により各々の Ĉi が大きくなる．このため重なり

kNN processing (Time-dependent Networks)

kNN processing (Time-dependent Networks)

1000

CreateCell

1000
1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

100

160
1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

100

Road Networks
Time-dependent Road Networks
140

120
10

10
Time(sec)

Time(msec)

Time(msec)

100

1

1

80

60
0.1

0.1

0.01

0.01

0.001

0.001

40

20

0

2000

図 11

4000

6000

8000
Node

10000

12000

14000

時間依存ネットワークにおける

0
0

図 12

ノード数に対する kNN 探査時間

10

20

30
MobileObject

40

50

60

時間依存ネットワークにおけるオブジェクト数に対する kNN 探査時間

0

1000

図 13

2000

3000

4000
5000
Node

6000

7000

8000

道路ネットワークにおけるノード数に対するセルの生成時間

最大平均移動速度 最小平均移動速度大きくした．これらの規則に則り作成した 4 パターンの最大平25.0m 以上

60km/h 50km/h

13.0m 以上 25.0 未満

均移動速度と最小平均移動速度の組み合わせを表 2 に示す．

60km/h 45km/h

5.5m 以上 13.0m 未満

50km/h 30km/h

これを基にしたランダムな速度でエッジの距離の割った値を3.0m 以上 5.5m 未満

40km/h 15km/h

重みとして 5 つ作成しする．その重みを 24 時間周期になるよ

幅員

表 2 幅員による平均移動速度

合うセルが多くなり候補となる NN が多くなる．その影響によう繋ぎ合わせる事により，時間に依存したエッジの重みとする．
その他評価方法及び実験環境は前述のものと同じである．

り時間依存ネットワークでは通常ネットワークに比べ，処理コ

7. 2 データ特性によるセルの生成速度への影響

ストの削減比率が小さくなっていることも確認できる．

実道路網データの特性によるセルの生成速度への影響を評価

7. 数値地図に対する数値シミュレーション評価

する．通常道路ネットワーク並びに時間依存道路ネットワーク
上でのノード数に対するセルの生成時間の変化を図 13 へ示す．

7. 1 対象データと評価方法

また，モバイルオブジェクト数に対するセルの生成時間の変化

実際の数値地図データを用い，本稿で述べた G におけるモを図 14 へ示す．

バイル kNN 探索と最小移動時間経路探索の性能評価と検討を

これら結果からセルの生成コストは，基本的にノード数また行う．対象データとして，国土道路地理院にて刊行されているはモバイルオブジェクト数のどちらか一方でも大きい時に増加「数値地図 25000 大阪」と「数値地図 25000 京都」に含まれてすることが見て取れる．しかし，必ずしもノード数やモバイル

いる道路網データ [8] のうち特徴的な 49 個のデータを用い，比オブジェクト数の増加に伴い生成コストが大きくなるとは言え較を行う．この道路網データの交差点をノード，道路片をエッない．これは，実道路網ではノード数が大きくともモバイルオ

ジとみなし利用する．

ブジェクト数が小さかったり，モバイルオブジェクト数が大き

巡回中の警察官への kNN 探査を想定し，警察官をモバイル

くともノード数が小さかったりすることが多々あるためである．

オブジェクトとする．モバイルオブジェクトは道路網データに実際に図 13, 図 14 では，生成ネットワークへの適用時の結果含まれる一つの警察関連施設につき一つ作成するものとする．

である図 5, 図 6 と異なり，激しい起伏が多々見られる．

またモバイルオブジェクトの移動範囲は実際の大阪府警察の管

7. 3 分散処理によるセルの生成速度への影響

轄範囲 [9] を参考に，警察関連施設を出発地点とし最短移動経

本提案手法は移動範囲の被覆の許容など，実世界での利用を路に沿って移動した際に 1.2km 以内であるノードを移動範囲と想定し設計している．これにより実道路網への適用時においてした．

も処理を分散させることが可能である．そこで，セルの生成処

本章では，エッジの重みが固定である通常の道路ネットワー

理を分散させることによる，実行時間への影響を評価する．

クと，エッジの重みが時間に依存する時間依存道路ネットワー

時間依存道路ネットワーク上でのノード数に対する分散数

クの二種類のネットワーク上にてセルの生成と kNN 探査の評

1,2,3,5,8 の実行速度の変化を図 15 へ，モバイルオブジェクト価を行う．通常の道路ネットワークではエッジの距離を重みと数に対する実行速度の変化を図 16 へ示す．

して使用し，時間依存道路ネットワークでは次の時間に依存すこれらの結果から，実道路網への適用時においても，処理のるエッジの重みを使用する．今回使用する数値地図データには分散化により確実に生成時間を削減できていることが確認でき

道路片の交雑状況は入っていないため，実際の道路状況を想定る．また紙面の都合上図を割愛したが，生成ネットワークへのし，道路片の幅員データから 4 パターンの最大平均移動速度と適用時と異なり，時間依存道路ネットワークでは通常道路ネッ

最小平均移動速度を設定する．幅員が大きい道路片は，制限速

トワークに比べ全体の処理コストが増加していることが見て取度が高いことから，最大平均移動速度を大きくした．また，幅れた．これは実道路網では，生成ネットワークに比べエッジの員が大きいほど混雑時の影響が小さいと考えられるため，最大繋がりが複雑なため，時間依存ネットワークにおいて細かい識

平均移動速度と最小平均移動速度の差を小さくした．幅員が小別処理が多く入るためである．

さい道路片は，制限速度が低いことから，最大平均移動速度を

7. 4 データ特性による kNN 探査速度への影響小さくした．また，幅員が小さいほど混雑時の影響が大きいと

実道路網において，生成されたセルを用い kNN 探査を行なっ考えられるため，最大平均移動速度と最小平均移動速度の差をCreateCell

Distributed processing CreateCell (Road Networks)

160

Distributed processing CreateCell (Time-dependent Road Networks)

120

120

Road Networks
Time-dependent Road Networks

1 Distributed
2 Distributed
3 Distributed
5 Distributed
8 Distributed

140
100

1 Distributed
2 Distributed
3 Distributed
5 Distributed
8 Distributed

100

120
80

80

80

Time(sec)

Time(sec)

Time(sec)

100

60

60

60
40

40

20

20

40

20

0

0
0

5

10

15

20
25
MobileObject

30

35

40

図 14 道路ネットワークにおける

0
0

10

図 15

30
MobileObject

4050

通常道路ネットワークにおけるオブジェクト数に対するセルの生成時間

0

図 16

Time(msec)

Time(msec)

1

1

0.1

0.1

0.01

0.01

0.01

0.001
0

図 17

10

20

30
MobileObject

4050

通常道路ネットワークにおける

1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

10

0.1

0.001

50

オブジェクト数に対するセルの分散生成時間

100

10

1

40

1000
1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

100

10

30
MobileObject

kNN processing (Time-dependent Road Networks)

1000
1-NN(using CELL)
1-NN
3-NN(using CELL)
3-NN
5-NN(using CELL)
5-NN

20

時間依存道路ネットワークにおけるkNN processing (Time-dependent Road Networks)

1000

100

10

オブジェクト数に対するセルの分散生成時間

kNN processing (Road Networks)Time(msec)

20

0.001
0

図 18

オブジェクト数に対する kNN 探査時間

1000

2000

3000

4000
5000
Node

6000

7000

8000

時間依存道路ネットワークにおける

0

図 19

ノード数に対する kNN 探査時間

10

20

30
MobileObject

4050

時間依存道路ネットワークにおけるオブジェクト数に対する kNN 探査時間た場合と，セルを用いず時間依存 A*探査のみを用いて kNN 探

今回ネットワークとして道路網データを用い実験を行ったが，査を行った場合との処理時間の比較を行う．この比較により，ノードと正の重みをもつエッジで構成されたネットワークであセルの利用による実行速度への影響の検証を行う．

れば，本提案手法を適用することが可能である．道路ネット

通常道路ネットワーク上において 1-NN,3-NN,5NN を求めた

ワークに限らず様々な分野のネットワーク上にて本手法を適用際のモバイルオブジェクト数に対する実行時間の結果を図 17 へすることにより，新たな可能性を見出すことができる．

示す．また，時間依存道路ネットワーク上にて 1-NN,3-NN,5NN

文を求めた際のノード数に対する実行時間の結果を図 18 へ，モ
バイルオブジェクト数に対する実行時間の結果を 19 へ示す．
この結果から，実道路網データへの適用時においても，セルを用いることの有効性が確認できた．更に両者のネットワーク
において生成ネットワークへの適用時よりも処理の削減比率が大きい．これは，実道路網は生成ネットワークに比べエッジの複雑性が増し，それにより目的地への移動コストの計算量が増加しているためである．これによりセルを用いた NN 候補の絞込みが大幅な処理コストの削減に繋がっている．

8. お わ り に
本稿では，時変重みを持つ道路網上でのモバイル kNN 問合せ処理手法の提案と評価を行なった．評価では生成したネット
ワークへの適用にて本提案手法の特性を確認し，実際の道路網
データへの適用により有用性を確認した．これにより，提案手法の有効性が見て取れた．
提案手法により生成されたセルを用いることで，kNN 探査の実行時間を大幅に削減することが可能である．セルの生成は非常に処理コストがかかることが確認された．しかし，問合せ回数が多いような状況では，セルを利用することでの探査処理
コストの削減量がセル生成コストを上回り有用である．また，セルの生成処理を分散させることにより，生成時間が大幅に削減されることが確認できている．

献[1] Zhao,G. Xuan,K. and Taniar,D.: ”Path kNN query processing in Mobile Systems”, IEEE Transactions on Industrial
Electronics,Vol.99, pp.1-8 (2011).
[2] Zhao,G. Xuan,K. Rahayu,W. Taniar,D. Safar,M. Gavrilova,M.L.
Srinivasan,B.: ”Voronoi-Based Continuous k Nearest Neighbor Search in Mobile Navigation”, IEEE Transactions on
Industrial Electronics,Vol.58, pp.2247-2257 (2011).
[3] Kambara,T. Tamaki,K. Muranaka,T. Ueshima,S.: ”Spatial
Queries Processing in Autonomous Mobile System Environment” IEEE 17th International Conference on Parallel andDistributed Systems(ICPADS), pp.770-775 (2011)[4] Li.G, Fan.P, Li.Y: ”An Eﬃcient Technique for Continuous
K-Nearest Neighbor Query Processing on Moving Objects
in a Road Network” IEEE 10th International Conference on
Computer and Information Technology(CIT 2010), pp.627634 (2010)[5] Demiryurek,U. Banaei-Kashani,F. and Shahabi,C.: ”Eﬃcient K-Nearest Neighbor Search in Time-Dependent Spatial Networks”, Proc. 21st International Conference on
Database and Expert Systems Applications(DEXA2010),
pp.432-449 (2010)[6] Graf,M. and Winter,S.: ”Network Voronoi Diagrams”,
Proc. Österreichische Zeitschrift für Vermessung und Geoinformation, Vol.91 No.3, pp.166-176 (2003).
[7] Cormen,Thomas H. Leiserson,Charles E. Rivest,Ronald L.:”Introduction to Algorithms (ﬁrst edition ed.)”, MIT Press
and McGraw-Hill, pp.558-565,pp.570-576 (1990)[8] 国土地理院, 数値地図 (空間データ基盤), http://www.gsi.go.jp/[9] 大阪府警察, 管轄区域について, http://www.police.pref.osaka.jp/