論文――――――――――――――――――――――――――――――――――――
索引付けされた移動軌跡データからの効率的な移動統計量抽出法の評価

DBSJ Letters Vol.2,No.2

1. はじめに
今日では空間情報利用の拡大や，モバイルユーザを対象としたデータベース技術が重要となってきており，時空間データベースに関Evaluation of a Mobility Statistics Extractionする研究が盛んに進められている[2]．時空間データベースからのScheme for Indexed Spatio-Temporal Datasets

する統計量は，問合せ処理の効率化のみならず，蓄積された移動状

塚本 祐一1 石川 佳治2 北川 博之3

空間データの利用拡大により，移動分析のための統計量を効率よく

Yuichi TSUKAMOTO
Hiroyuki KITAGAWA

Yoshiharu ISHIKAWA

統計情報の抽出に関する研究はその一つである．
時空間データに関況データをもとに移動分析を行う際においても有用である[4]．時抽出することが今後より重要となると考えられる．
以上の背景をもとに，我々は時空間データベースから移動オブジ
ェクトの移動状況に関する統計情報を抽出する手法の研究を進めている[5‑7]．移動に関する統計量として，本研究ではマルコフ連

空間情報利用の急速な進展および携帯機器などの普及から，時鎖（Markov chain）モデルに基づく移動統計量を対象としている．

空間データベースの研究分野では，移動するオブジェクトやユー

時空間データ分析におけるマルコフ連鎖モデルは，ある地域からザの移動状況を，データベースに蓄積し効率よく管理するための別の地域へある期間内にどの程度の人口が移動したといったよう研究が盛んに進められている．セルの集合に分割された空間上をな，人や物の時空間的な移動傾向を把握するために用いられる[4]．

時間の経過につれてオブジェクトが移動する状況を捉えるため

この統計情報により，ある時点である位置にいるオブジェクトが次の統計量として，マルコフ連鎖モデルが存在する．我々は，蓄積の時点でどこに移る可能性が高いといった予測が可能となる．

された移動情報データからマルコフ連鎖モデルに基づき移動統本研究では特に，移動オブジェクトの移動軌跡が空間索引R‑木に計量を高速に抽出し，対話的な移動状況の分析を支援するための蓄積されている状況を想定し，R‑木から効率的にマルコフ連鎖の遷手法について研究を進めており，移動オブジェクトの移動軌跡デ移確率を推定する手法を開発している．
本稿では提案手法の実装とータが空間索引R‑木に蓄積されている際に，マルコフ連鎖の遷移実験を行い，その有効性を示す．

確率を効率的に求めるための手法を開発している．本稿では実験に基づく提案手法の有効性の評価を行う．

2. マルコフ過程モデルに基づく移動統計量

With the recent progress of spatial information technologies

図1に示すように，空間がセルに分割されているとする．各セル

and mobile computing technologies, spatio-temporal databases

は矩形でなくてはならないが，サイズは必ずしも均一でなくてよい

which store information on moving objects including vehiclesとする．各セルにはセル番号が付けられていて，番号によりセルをand mobile users have gained a lot of research interests. Here特定できるものとする．図1は，時刻 t =τでセル c0 にいたオブ

we focus on a mobility statistics value called the Markov

ジェクト A が，次の時刻 t =τ+1 でセル c1 に，そして t =τ+2transition probability, which is based on a cell-basedの時点でセル c2 に移動した状況を示している．

organization of a target space and the Markov chain model. We
have proposed an algorithm to extract mobility statistics fromindexed spatio-temporal datasets for the interactive analysis ofhuge collections of moving object trajectories. The proposedalgorithm efficiently computes the specified Markov transition
probabilities with the help of a spatial index R-tree. In thispaper, we evaluate the effectiveness of proposed method based

図１ マルコフ過程モデルの概念

on an experiment.
Aのように，セル c0 に現在いるオブジェクトが次の時点でセル c1に移動する確率 Pr(c1￨c0) を時空間データベース中のデータを用
1 学生会員

筑波大学大学院システム情報工学研究科
yuichi@kde.is.tsukuba.ac.jp
2 正会員 筑波大学電子・情報工学系
ishikawa@is.tsukuba.ac.jp
3 正会員 筑波大学電子・情報工学系
kitagawa@is.tsukuba.ac.jp

1

いて予測したいとすると，以下のように計算できる．
T −1∑ | objs(c , t ) ∩ objs(c , t + 1) |Pr( c1 | c0 ) = t =00

1(1)

T −1

∑ | objs(c , t ) |t =00

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

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

obj(ci,t) は，時刻 t にセル ci の領域に含まれているオブジェ間上の点で表される場合，d +1 次元空間のR‑木を構築し，各時刻 tクトの集合を返す関数である．各時点 t = 0,…,T ‑1 で c0 にいたに対する o の情報を [x1,…,xd,t] という d +1 次元ベクトルとオブジェクトの総数を分母とし，そのようなオブジェクトのうち，o のオブジェクトIDとペアでR‑木に挿入すると索引が構築表現し，次の時点でc1に移ったオブジェクトの総数を分子として計算する．

できる．こうすることで，点による表現に対して時刻 t において確率 Pr(c1￨c0) は，現在の状態（セルc0 ）に依存して次の状態セル c に含まれている移動オブジェクトのIDを検索することが可（セルc1）を予測するという意味で，1次のマルコフ過程の遷移確能となる．

率に相当する．これを一般化すると，n 次のマルコフ過程による遷移確率，すなわち，単位時間ごとに c0,c1,…,cn‑1 とセルを移動したオブジェクトが次の時点でセルcnを訪れる確率 Pr(c ￨c ,…,cn )n0

4.1 問題の定式化と表され，その推測値は以下の一般形になる．
T −1∑ | I objs(c , t + i ) |Pr( cn | c0 ,K, cn −1 ) = Tt =−01ni =0i(2)∑ | I objs(c , t + i ) |t =0n −1i =04. 素朴な遷移確率推定アルゴリズム‑1

時空間索引を用いて，式(2)に示した n 次のマルコフ遷移確率の推定を行うことを考える．ただし，特定のセルの組合せ c0,…,cnに対する遷移確率の推定ではなく，以下のように問題を一般化する．

i

遷移確率の推定問題

なお，ここでは移動オブジェクトの移動が定常的（stationary）なn + 1 個のセルの集合 C0 = {c0,1,…,c0,￨c0￨},…,Cn =過程に従い，時刻によって遷移確率が変化しないと仮定している.

{cn,1,…,cn,￨cn￨}が与えられたとき，任意のセルの組合せマルコフ遷移確率を効率的に求めることがでれば，移動オブジェクトが次の時点でどのセルに移動する可能性が高いかという，一種の経路予測を行うことが可能となる．
ある時刻における移動オブジェクト集合の移動状況データがまとめて与えられたとき，以降における移動状況をシミュレーションすることも可能となる．

(c0,c1,…,cn)∈C0×…×Cn に対し，Pr(cn￨c0,…,cn‑1) の値が未定義でなければその値を出力する.

□4.2 素朴なアルゴリズム
素朴な方式として，特定のセルの組合せ c0,…,cn についてPr(cn￨c0,…,cn‑1) の推定を行うことを考える.この確率は以下の2つの集合 S, Q を求めることで計算できる．

3. 空間索引による索引付け
以下では，移動軌跡を点の集合として離散的に表現する場合の，本研究のアルゴリズムが想定する索引付け方式について述べる．
線分を用いて移動軌跡を表現する場合の索引付け方式については，[5]でその方法を述べている．

(1) ある時刻 t = τ(τ= 0,1,…,T ‑ n) においてセル c0 にいて，かつ，t =τ+1 においてセル c1 にいて,…,かつ t =τ+n‑1
においてセル cn‑1 にいたオブジェクトの集合 S(2) S に含まれるオブジェクトのうち，t = τ+n においてセル cnにいたオブジェクトの集合 Q
先の推定問題に対する素朴なアルゴリズムはこのアイデアをもと例として，1次元空間でのオブジェクトの移動の例を考える．図2に導ける．各時刻 t について，R‑木を繰り返し検索することで，は，オブジェクト A, B が時刻 t = 0 から t = T (= 8) まで x 軸

各時刻について上記の集合 S, Q を決定し，それを集計することで上を移動する様子を示している．
移動経路は曲線で表現されている．

求める確率を決定する．この方式は，アルゴリズムは比較的単純で実際の移動軌跡はこのように複雑であるが，計算機上での表現にはあるが，R‑木の検索数が T に比例するという性質があり[5‑7]，移何らかの近似が必要である．図2に示した経路上の点は，各時刻に動軌跡を索引付けする時間が長くなれば長くなるほど，検索コストおいて移動軌跡をサンプリングしたものである.この近似により，が高くなるという問題点がある．

各オブジェクトの経路は時刻と位置のペアの列で表現できる.このような表現手法を点による表現と呼ぶ．
GPS により一定期間ごとに移動オブジェクトの位置を検出する場合は，このような表現をすることが自然である．

5. 効率的な遷移確率推定アルゴリズム
次に効率的なアルゴリズムについて述べる．
このアプローチでは，Pr(cn￨c0,…,cn‑1) の推定を以下の3ステップで行う.
(1) 単位時間ごとに c0,…,cn‑1 に存在したオブジェクトの総数をR‑木を用いてカウント(2) 単位時間ごとに c0,…,cn に存在したオブジェクトの総数をR‑
木を用いてカウント(3) ステップ2のカウント数÷ステップ1のカウント数により図2 点による移動軌跡の表現
点による表現を用いる場合，移動オブジェクト o のある時刻 t=τ(τ=0,1,…,T ) における位置が [x1,…,xd] という d 次元空2Pr(cn￨c0,…,cn‑1) を計算
R‑木の探索はステップ(1), (2)でそれぞれ1回ずつ，合計2回しか行われないため，先の素朴な手法に比べ効率的な処理が達成できる．

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

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

各ステップでオブジェクトの集計処理を行う関数は，R‑木を用いその結果，定常状態では平均して100件強の移動オブジェクトが地た空間的制約の充足解の探索手法[3]を拡張したものである．この図上を移動することとなった．本実験では，このようにして生成さアプローチでは，R‑木上をルートからリーフ方向に時間的な制約をれる多数の移動オブジェクトの移動状況を，1分刻みで T = 1000 分満たす解を探していく．その際，より効率的にR‑木を探索するための期間に対して生成した．この結果，（オブジェクトID，時刻，xにバックトラックや枝刈り条件によって解候補の絞込みを行い，充座標，y座標）という形式のデータが124,752件生成された．これら

足解をもれなく探索する．セルに対する空間的制約も，解候補の絞のデータを3次元のR‑木に登録した．
ここで問合せとして用いた，マルコフ遷移確率の推定込みに役立つ．
詳しいアルゴリズムについては、DBSJ Letters 論文[6]でも述べ問合せについて述べる．図に示すように，一部の空間をランダムにているため省略する．詳細については論文[5‑7]を参照していただ

選び，一定サイズのセルに分割し，遷移確率の推定に要した計算時きたい．

間を計測し比較する．図4では，ランダムに3×3の空間を選んだ時のセル領域と，導かれる遷移確率の例を示したものである．この場
合は1次のマルコフ遷移確率の値を示している．

6. 実験
本節では，移動オブジェクトのシミュレーションデータを用いて，素朴な遷移確率推定アルゴリズムと提案手法との処理時間の比較を行う．

6.1 実験用データ
実験ではBrinkoffにより作成された移動オブジェクトデータ生成ソフトウェア[1]を用いる．これは実際の市街地の道路ネットワーク上を自動車などが移動する際の移動の状況をシミュレーションするシステムであり，これによって生成された移動データを実験において使用する．今回扱うデータは，このシステムで提供されているドイツOldenburg市の中心部（約2.5×2.8km）の道路ネットワークにおいて，パラメータを適宜設定して生成したものである．図
図4 マルコフ遷移確率の例

3にこのシステムのインタフェース画面を示す．地図上に見える丸い点が移動オブジェクトを示している．

6.2 実験結果
図5は，空間を30×30のセルに分割し，ランダムに3×3のセルを選んだ時の1次の遷移確率（81通りの組み合わせ）の推定時間の比較を示す．縦軸には計算時間を示す．横軸は実験用データとして用意したT=1000分うち，何分までのデータに対して確率推定を行うかを示している．T=1000の時は，用意したデータをすべて使用してい図3 データ作成ソフトウェア

10.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.10

素朴
提案手法

T=
100
T=
200
T=300
T=400
T=500
T=
600
T=700
T=
800
T=
900
T=1000

計算時間（秒）る．

対象時間（分）移動データ生成では，初期移動オブジェクトの個数を5件とし，1分ごとに5件ずつ移動オブジェクトが地図上にランダムに生成・配図5 3×3のセルによる1次のマルコフ遷移確率置されるものとした．
各移動オブジェクトには目的地が設定されて図5から分かるように，提案手法の方が素朴な手法よりも，約4倍近おり，目的地に達した場合は地図上から削除される．また，移動オ

い速度を示している．

ブジェクトが地図領域の外に出た場合にも地図上から削除される．

3

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

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

基づく移動統計量を推定するためのアルゴリズムを実装し，有効性を示すための実験を行った．空間索引の内部情報を利用し，計数処

素朴提案手法理の効率化を図った点が特徴となっている．今後の課題として，更に詳しい実験や，1) データベース中のデータの分布に合わせたセルの適合的な分割，2) 非定常なマルコフ過程への拡張などが挙げられる．

T=
100
T=
200
T=
300
T=
400
T=500
T=
600
T=
700
T=
80
0
T=
900
T=
1000

計算時間（秒）87
6543210

対象時間（分）[謝辞]
本研究の一部は，日本学術振興会科学研究費基盤研究(B)(12480067)，若手研究(B)(14780316)，および文部科学省科学研

図6 3×3のセルによる2次のマルコフ遷移確率究費特定領域研究(14019009)，
財団法人セコム科学振興財団研究奨励金による．

120

計算時間

10080

素朴

[文献]

提案手法

[1] Brinkhoff, “A Framework for Generating Network Based

60Moving Objects”, GeoInfomatica, 6(2), pp. 153-180, 2002.

40[2] C.S. Jensen (ed.), “Special Issue: Indexing of Moving Objects”,

IEEE Data Engineering Bulletin, 25(2), Jun. 2002.

20[3] D. Papadias, N. Mamoulis, and Vasilis Delis,“Algorithms for000090

10
T=

T=800

対象時間

T=700
T=060
T=050
T=40

0
T=030
T=

20
T=

T=1000

図7 3×3のセルによる3次のマルコフ遷移確率
図4,5,6が示すように,素朴なアルゴリズムに比べて効率的な遷移確率推定アルゴリズムの方が良い結果であることがわかる.
次に,効率的なアルゴリズムが不利な状況の例を示す.これは,空間を20×20のセルに分割し,ランダムに3×3のセルを選んだ時の2次の遷移確率（729通りの組み合わせ）の推定時間の比較である.

Example,Volume II: Categorical and Directional Data”, John
Wiley & Sons, 1989.
[5] 石川, 塚本, 北川, 索引付けされた移動軌跡データからの移動統計量の抽出法について, 第14回データ工学ワークショップ(DEWS 2003), 2003年3月.
[6] 塚本, 石川, 北川, 索引付けされた移動軌跡データからの効率的な移動統計量抽出法，日本データベース学会Letters Vol.2,

25No.1，2003年5月．

素朴提案手法20

計算時間（秒）

Querying by Spatial Structure”, Proc. of VLDB, 1998.
[4] G.J.G. Upton and B. Fingleton, “Spatial Data Analysis by[7] 塚本, 石川, 北川, 索引付けされた移動軌跡データからの移動

15

統計量の抽出法の評価，情報処理学会研究報告，

102003-DBS-131-30, 2003年7月

50

T=
100
T=
200
T=
300T=
400
T=
500
T=
600
T=
700
T=
800
T=
900
T=1000

塚本 祐一 Yuichi TSUKAMOTO
対象時間（分）

図8 3×3のセルによる2次のマルコフ遷移確率

筑波大学大学院システム情報工学研究科在学中．
2002年筑波大学第三学群情報学類卒業．時空間データベースの研究に従事．日本デー
タベース学会学生会員．

この原因としては，セルの分割が粗いため，枝刈りをしても解候補

石川 佳治 Yoshiharu ISHIKAWAをあまり絞り込むことができなかったというのが原因の1つとして筑波大学電子・情報工学系講師. 1994年筑波大学大学院博士課程工考えられる.

学研究科単位取得退学．博士（工学）．空間データベース，文書デ

今回の実験の詳細な分析で分かったことは，構築されたR‑木の形ータベース，情報検索などに興味を持つ．ACM，IEEE‑CS，情報処理が性能に大きな影響を及ぼすことである．今回の実装で用いたR‑学会，電子情報通信学会，日本データベース学会，各会員．

木の挿入アルゴリズムよりもさらに良いもの（例：R*‑木）を使用

北川 博之 Hiroyuki KITAGAWA

すれば、さらに計算時間は短縮できると考えられる．また，入力デ

筑波大学電子・情報工学系教授．1980年東京大学大学院理学系研究ータに応じた適当なセルの分割が重要であることも分かった．

科修了．理学博士（東京大学）．異種情報源統合，文書データベー
ス，WWWの高度利用等の研究に従事．著者「データベースシステム」

7. まとめ
本稿では，時空間データベースの情報からマルコフ過程モデルに

4（昭晃堂），「Unnormalized Relational Data Model」(共著，Springer‑Verlag)等．ACM，IEEE‑CS，日本データベース学会，情報処理学会，電子情報通信学会，日本ソフトウェア科学会，各会員．

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