移動オブジェクトデータベースに関する研究動向石川 佳治
筑波大学大学院システム情報工学研究科
筑波大学計算科学研究センター
ishikawa@cs.tsukuba.ac.jp

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引• 問合せ処理• 我々の研究1

背景：位置ベースのサービス• はじまり（US）– 911サービス• FCC（Federal Communications Commission）• 携帯キャリアに話者の位置特定機能を義務付け（1996年）– GPSを一般に開放：5～50メートルの精度• 応用例– Mobile Resource Management (MRM)• 車両管理，交通管理– Location-aware Content Delivery• 道路情報，近隣情報– Digital Battlefield• 「10分以内にこの地域に到達できるヘリは？」2

背景：移動体通信• ユーザとセルの対応を管理：(key, cell-id)• 2種類の基本処理– point query：電話の際に発生• 「キー123-456-789 をもつ移動オブジェクトの現在位置（セル）を求めよ」– point update：移動の際に発生• 「キー123-456-789の移動オブジェクトの位置（セル）を更新せよ」– 分散・複製・キャッシュ管理がキーポイント• 一種の移動オブジェクトデータベース3

移動オブジェクトデータベース（１）• Moving Objects Database (MOD)• 多様な問合せ– 空間データベースの拡張• 範囲問合せ（range query）：指定された範囲内のオブジェクトを検索– 「（10分以内に）つくば市を通過する移動オブジェクトを検索」• 最近傍問合せ（nearest neighbor query ）：指定された点に最も近いオブジェクトを検索• k-最近傍問合せ（k-nearest neighbor query）：近いものから k 個• 結合問合せ（join query）– 「今後領域がオーバラップする移動オブジェクトのペアを列挙せよ」– 「10分以内に10kmの距離に接近する飛行機のペアを列挙せよ」• closest-pair query– 「最接近時点での距離が近い順に k 個のオブジェクトのペアを示せ」• 類似検索（similarity query）– 「オブジェクト o と類似した移動軌跡を持つオブジェクトは?」4

移動オブジェクトデータベース（２）• 多様な問合せ（続き）– 時間の扱いによる分類• past query– 「先月○○停留所で5分以上遅れたバスの件数は?」• set-oriented present query– 「ここから1km以内にタクシーをすべて求めよ」• future query– 「10分後のトラック#5の位置を予測せよ」• set-oriented future query– 「20分以内に目的地に到達するトラックをすべて求めよ」– アドホックな問合せ/連続的問合せ• trigger– 「目的領域にヘリが到達したらメッセージを私まで送信せよ」• incremental range/nearest neighbor query– 前回の検索結果を適宜更新

5関連する研究領域• 時空間データベース– 空間データベースの延長上– オブジェクトを点，移動軌跡をベクトルなどでモデリング– 問合せ処理，索引，統計処理，データマイニング• モバイルデータベース– モバイル環境＋データベース• ユビキタスデータベース• センサデータベース• 時系列データベース
6

MODの応用（１）• 時空間情報の検索– 「移動経路で2キロ以内に1泊1万円以内のホテルがあったら通知せよ」– location dependent query• 交通管理– 「A地点に最も早く到達できるタクシーは?」– 「B地点への到達時間は?」• モバイルEコマース• Mobile workforce management– 「春日3-2-1の近くにいるサービスクルーは誰?」• Digital battlefield– 「領域X内に味方の戦車は何台いるか?」

7

MODの応用（２）• 位置とコンテクストに応じた情報提示• 航空管理– 「将来衝突の可能性がある飛行機のペアがあるか?」• 移動体通信のサポート• モバイル環境の支援– mobile ad-hoc network (MANET)：位置情報を補うことによる効率化• 商用ベースの応用– Mobitrac http://www.mobitrac.com/– Qualcomm http://www.qualcomm.com/– @Road http://www.atroad.com/main.html
8

研究課題• データモデル• 索引手法• 問合せ処理• 位置ベースの情報サービス• 時空間データマイニング

9

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引• 問合せ処理• 我々の研究10研究事例：DOMINOプロジェクト• Databases fOr MovINg Objects• Wolfsonら（U. Illinois）• 特徴– オブジェクトの現在，過去，未来の位置を追跡– 出発地・目的地情報を利用– 動的属性– 複雑な問合せ– DBMS上に実装– あいまい性を考慮
11

研究事例：CHOROCHRONOSプロジェクト• 欧州の研究者を中心としたプロジェクト– 1996.8～2000.7– 移動オブジェクトデータベースを含む時空間データベースに関する研究• 研究課題– オントロジー– モデルと言語：データ型，問合せ言語– インタフェース– 問合せ処理– 索引手法，格納手法– アーキテクチャ

12

CHOROCHRONOSの概要•

時空間データのオントロジー– 時空間オントロジーと時空間DBの関連•

時空間DBMSのためのモデルと言語– 時空間情報のためのデータ型– モデルと問合せ言語– 時空間データベースの設計手法•時空間データベースのインタフェース– GUI技術– 可視化• 問合せ処理– 効率的な問合せ評価– 最適化処理• 格納構造，索引手法
13

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引• 問合せ処理• 我々の研究14

MODのデータモデル：分類• 表現方式– 点データ，および点データの集まり– 移動軌跡（polyline）– 抽象データ型– 制約データモデル• 問合せ対象– 過去の移動情報• 遡及的な問合せ・分析– 現在および今後の移動情報• リアルタイムの応答• 予測に基づく処理– 連続的問合せ• あいまい性・不正確さの表現

15

移動情報の表現方式：点データ• 位置を (l, t) のペアで管理– l: 位置（座標値またはセルIDなど）– t: 時刻– DBMSによる管理が容易• 問題点– 内挿，外挿（予測）が難しい• 移動軌跡の情報が欠落

16

移動情報の表現方式：移動軌跡データ• 移動軌跡（trajectory)を直接的に表現– 線分（line segment）をつないだ 多角線（折れ線，polyline）の表現が一般的– 例：(x1, y1, t1), (x2, y2, t2), ...
– 移動速度も（近似的に）表現可能– 点データに比べ情報量大• 問題点– 特別のアルゴリズム・データ構造が求められる– データ量17抽象データ型のアプローチ（１）• Gütingらによる• CHOROCHRONOSプロジェクトの一環• 時空間データのためのデータ型を開発– 移動する点，領域のためのデータ型– それらデータ型に基づく問合せ言語• アプローチ– 時間の関数として時空間データを表現– リレーショナルモデルおよびSQLに埋め込み– 抽象化のレベル
18抽象データ型のアプローチ（２）• Moving Entities– 時刻をパラメータとする関数でモデル化
Moving point
mpoint = time → point

Moving region
mregion = time → region

オペレーションの例：
inside: mpoint ×mregion → mbool (a “moving boolean”)

19抽象データ型のアプローチ（３）• 抽象のレベル：moving pointを例に– time → point の関数– 3次元空間の多角線– 抽象的– 連続的– 無限の表現– 概念レベルのモデル– 具象的– 離散的– 有限の表現– 実装レベルのモデル

20

抽象データ型のアプローチ（４）routes (airline: string, id: string, flight: mpoint)–「500km未満の距離のJALのフライトは?」• SELECT airline, id
FROM routes
WHERE airline = "JAL" AND length(trajectory(flight)) >5000– 「500メートル以内に接近するフライトのペアを求めよ」• SELECT p.airline, p.id, q.airline, q.id
FROM routes p, routes q
WHERE val(initial(atmin(distance(p.flignt, q.flight)))) <0.521

制約データモデルの利用（１）• 制約論理式で表現– 制約データベース（constraint database）の枠組
みを利用– 一般に線形制約（linear constraint）を利用• 計算量の面で有利• 理論的背景が存在，多次元でも成立• 計算量は一般に大• 例：移動軌跡の表現–x = [2, –1, 0]T t + [−40, 23, 30] T ∧ 0 ≤ t ≤ 21
∨ x = [0, – 1, –5] T t + [2, 23, 135] T ∧ 21 ≤ t < 22
∨ x = [0.5, 0, –1] T t + [–9, 1, 47] T ∧ 22 ≤ t

22

制約データモデルの利用（２）• 問合せの例：時刻 τ1 から τ2 の間につくば市の領域内に入った移動オブジェクトは?
– {y | O(y) ∧ ∃ (τ1 ≤ t ≤ τ2 ∧ ∃ x (T(y, t, x) ∧ ϕ (x))∧ ∃ t'(t' < t ∧ ∀ t'' (t' < t'' < t →¬ ∃ x (T(y, t'', x) ∧ ϕ(x)))))}– O(y)：y が移動オブジェクトであることを表す述語– T(y, t, x)：時刻 t におけるオブジェクト y の位置がx であることを表す述語– ϕ (x)：x がつくば市の領域内にあるとき真になる述語• 線形制約では書けないので，外部述語として表現• 問合せ処理時には呼び出すだけ23

制約データモデルの利用（３）• 問合せ処理– 問合せの制約式とある移動オブジェクト o に対する制約式を ∧ でつないだ論理式を構築– その論理式に充足解があれば o は問合せを満たす– 線形計画法を利用• 1オブジェクトに対し多項式時間の処理• 限量子の除去（quantifier elimination）：∀, ∃ を取り除く– MOD中のすべての移動オブジェクトへの適用はコスト大• 線形制約でなければさらに計算量大24制約データモデルの利用（４）• DEDALE– 制約データモデルに基づく時空間データベース– INRIAで開発– 線形制約を採用– トポロジカルな問合せを処理可能– 最適化に関する研究

25

時制論理の利用（１）• Future Temporal Logic (FTL)– DOMINOで利用：現在の情報をもとに未来を推論• 述語の例– f until g• g が真であるか，g が真となる直前まで f が真であるときに真となる– nexttime f• 次の時点で f が真となる– eventually f (= true until f )• f は将来的に真になる– always f (= ¬ eventually ¬ f )• 現在かつ将来において f は真26

時制論理の利用（２）• 述語の例（続き）– eventually_within_c(g)• 以降の c 単位時間の間に g は真となる– eventually_after_c(g)• 少なくとも c 単位時間の後には g は真となる– always_for_c(g)• 以降の c 単位時間の間 g はつねに真– g until_within_c h• 以降の c 単位時間の間に h が真でその直前まで g が真であるような状況がある• 他に空間述語（DISTANCE(o, P)など）も提供
27

時制論理の利用（３）• 以降の5単位時間の間に，ポリゴンP内に入るタクシーをすべて検索– RETRIEVE oWHERE o.type = "Taxi" ANDeventually_within_5 INSIDE(o, P)• 以降の5単位時間の間にポリゴンP内に入り，しかも3単位時間以上はP内に存在しているオブジェクトをすべて検索– RETRIEVE o
WHERE eventually_within5 (INSIDE(o, P)
AND always_for_3 INSIDE(o, P))
28

時制論理の利用（４）• 以降の3単位時間の間に，ポリゴンPの中に入り2単位時間以上存在し，少なくとも6単位時間後にはポリゴンO内にあるオブジェクトをすべて検索せよ– RETRIEVE o
WHERE eventually_within_3[INSIDE(o, P) AND
always_for_2 (INSIDE(o, P) AND
eventually_after_6 INSIDE(o, O))]29

あいまい性・不確かさの扱い• 位置情報にはあいまい性が存在– あいまい性を減らすにはコストが発生（例：データ取得頻度の増加）– ある程度の不正確さを許容してもよい– may / must のセマンティクス，確率（存在確率，信頼確率）の提示• コストの考慮– 更新コストと不正確さのコストのトレードオフ– 要求と対象に合った更新ポリシー30

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引• 問合せ処理• 我々の研究31

MODの索引：分類• 支援するデータモデル– 点データ– 移動軌跡• 問合せ対象– 過去の移動情報– 現在および今後の移動情報– 連続的問合せ• 更新の有無• データ構造– 木構造：R-木，四分木（quad-tree）の拡張– その他（空間分割，ハッシュなど）

32空間索引の利用（１）• 例：R-木– 多次元空間の点（x, y, t）で点を表現– 移動軌跡（polyline）の索引にも拡張可能– 頻繁な更新には向かない

33

空間索引の利用（２）• R-木に基づくアプローチ– 初期のアプローチ– 時間をもう一つの次元と見る– 3D R-tree，RT-tree，2+3 R-tree• バイテンポラルなR-木– valid time と transaction time を扱うR-木• Time-parameterized R-tree (TPR-tree)– 後述– TPR*-tree という拡張あり• Trajectory bundle– 過去の移動軌跡（polyline）の検索に利用
34

空間索引の利用（３）• 四分木に基づくアプローチ– MOF-tree• 時間的に連続した画像を扱うquad-tree– MOF+-tree• MOF-treeの拡張– Multiversion linear quadtree• 画像の時間的なシーケンスを格納• multiversion B-tree と linear region quadtree の組合せ

– Overlapping linear quadtree• linear region quadtree の拡張

35

DOMINOの索引（１）• アプローチ– 動的属性を幾何的に表現– 空間索引の利用• 複数の表現形式– 値と時刻による表現（value-time space）• 問合せ処理は効率的• 更新はあまり効率的でない– 切片と傾きによる表現（intercept-slope space）• いわゆるハフ（Hough）変換• 問合せ処理はあまり効率的でない• 更新処理は効率的
36

DOMINOの索引（２）– 1次元空間の移動オブジェクト– 時刻 10 において範囲 [5, 10] に含まれるオブジェクトは?
slopevalue• 範囲問合せの例

O1
O4
O2

10

O2
O35

問合せQ
10

O1

1time

value-time spaceにおける表現

0.5
intercept

O3

510

問合せQ

O4

slope-intercept spaceにおける表現

d 次元空間の直線 ⇒ 2d 次元空間の点37

問合せの種類• タイプ1：時刻 t において与えられた矩形と交わるオブジェクトを検索• タイプ2：時区間 [t1, t2] において与えられた矩形と交わるオブジェクトを検索• タイプ3：時区間 [t1, t2] において与えられた移動矩形と交わるオブジェクトを検索38

TPR-木（１）• Time-Parameterized R-tree– R-木の拡張• 移動する点データを 時刻をパラメータとする矩形で包囲– 現在（now）を基点とする– 包囲矩形は時間とともに拡大（or 縮小）・移動• 包囲矩形が小さくなるよう木を構築– 位置・速度が「近い」オブジェクトをグルーピング– 木の更新の際に再調整• アルゴリズム– 検索：R-木がベース– 構築・更新：大幅な拡張

39

TPR-木（２）• velocity bounding rectangle (VBR)– R-木の範囲矩形（bounding rectangle）に対応– 位置と速度により移動オブジェクトをグルーピン
グ• できるだけ包囲矩形の「サイズ」を小さくしたい• アプローチ：[now, H] の時区間における包囲矩形の面積 now+ Hを最小化∫ A(t )dtnow– H: 将来の修正時刻
40

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引• 問合せ処理• 我々の研究41

MODにおける最近傍探索（１）• 1-NN (nearest neighbor) に対するアプローチ– ボロノイ図を利用– いつまで検索結果が保証できるかも答える– 制約• 最大速度を仮定• 1-NNに限定• ボロノイ図の構築が必要• 連続的な k-NN 問合せ– オブジェクトが q から q' に移動– 前回の問合せ結果をもとに，できるだけコストの低い問合せをしたい– 例：q に対する 2-NN が a，4-NN が b のとき，2 dist(q, q') ≤ dist(q, b)- dist(q, a) ならば，q' の 2-NN は q の4-NNより近くにある

42

MODにおける最近傍探索（２）• Time-parameterized NN query– 移動オブジェクトは一定速度で一方向に進む– 1-NNとその有効期限，次の1-NNを連続的に提示– TPR-木を用いる拡張あり– 問合せ結果• 1-NN： i• 有効時間：2• 次の1-NN：j– influence timeを用いた処理• 現在のNN（i ）に対し，各オブジェクトがいつNNに置き換わるか• influence time最小のオブジェクトが次のNN

43

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引
移動ユーザのための適応型周辺情報提供手法• 問合せ処理• 時空間データマイニング• 我々の研究– 移動オブジェクトに対する適応的情報提供– 大量の移動軌跡からの移動統計量抽出法– 移動ヒストグラムの構築・管理手法

44

移動オブジェクトに対する適応的情報提供
利用者の移動経路（履歴情報・予測情報）を利用

A・例：移動する各地点において周辺にあるコンビニを探したい
・移動状況（経路，速度）を考慮した適応型の情報提供をしたい
・アプローチ：楕円状の距離関数を利用
履歴情報
予測情報
45

手法の概要
出発地
検索要求
パラメータ
目的地

：検索対象データ
：位置情報

出発地

周辺情報提供システム

目的地• 移動位置・状況に応じて周辺状況を検索・表示• 楕円体距離を利用：
距離関数の形状を適応的に調整
46

プロトタイプシステム

現在位置

問合せ中心

検索されたデータ

地図および検索結果を表示

・
プロトタイプシステムは ＡｒｃＶｉｅｗ上に実現

検索パラメータ設定

検索結果表示47

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引
移動ユーザのための適応型周辺情報提供手法• 問合せ処理• 時空間データマイニング• 我々の研究– 移動オブジェクトに対する適応的情報提供– 大量の移動軌跡からの移動統計量抽出法– 移動ヒストグラムの構築・管理手法

48

大量の移動軌跡からの移動統計量抽出法• 目的– 大量の移動オブジェクトの移動情報を要約– 移動分析（mobility analysis），移動予測シミュレーショ
ン• アプローチ：– 空間的なマルコフ遷移確率の推定• 対象空間をセルの集合に分割• 移動軌跡データをもとにセル間の遷移確率を導出– 制約充足問題（CSP）として定式化– 空間索引の利用• R-木に移動軌跡データが蓄積• 空間索引の効率的な探索49

移動状況データ（1）オブジェクトAの移動状況

0

12→2→0→0

オブジェクトBの移動状況
3→3→1→1

23

オブジェクトCの移動状況
0→2→2→350

移動状況データ（2）

02
8
10

1
3
911

4
612
14

5
713
15

オブジェクトAの移動状況
11→9→3→1

オブジェクトBの移動状況
14→12→6→4

オブジェクトCの移動状況
2→8→11→14

51

マルコフ遷移確率（１）• 例：セルc0 から c1 へ単位時間で移動したオブジェクトが，単位時間後に c2 に存在する確率は？
c0c1AAc2
At =τ

t =τ+1t =τ+2

• 2次の遷移確率 Pr(c2|c0, c1)• n次のマルコフ遷移確率 Pr(cn|c0, …, cn-1) への拡張は容易
52

マルコフ遷移確率（２）• 移動分析（交通工学）における古典的手法• 特殊な相関ルール– 遷移確率が信頼度（confidence）に対応– 順序が存在• 適用分野– 移動経路の推定• 移動オブジェクトの将来の移動先を推定– 移動状況のシミュレーション• 時刻 t = τ における移動状況が与えられたとき，t = τ+ 1, τ + 2, … における変化を推定する
53

確率の定式化• 対象データ：t = 0 から t = T の移動軌跡• n次のマルコフ遷移確率の定義
T −1n|
Ι∑ i=0 objs(ci , t + i) |Pr(cn | c0 ,Κ , cn−1 ) = Tt =−01n−1|Ι∑ i=0 objs(ci , t + i) |t =0– objs(ci, t)：時刻 t で ci にいたオブジェクトの集合– 分母：時刻 t (0 ≤ t ≤ T − 1) においてセル c0 にいて， t +1 では c1 にいて，…，時刻 t + n − 1 では cn − 1 にいたオ
ブジェクトの数– 分子：分母に含まれ，かつ，時刻 t + n で cn に移動したオブジェクトの数54

移動軌跡の表現：(d +1)-次元のR-木
xx

root
b１

５６３

Ba４c２０ 1

A０ 1

23

4562

37 8(=T)45678(=T)

roota

サンプリングに基づく表現
12b3c45655

制約充足問題（CSP）に基づく処理
例：Pr(c2|c0, c1) の推定xステップ１：単位時間の間に c0 から c0に移動したオブジェ
クトをカウントcell
c2 ステップ２：各単位
時間においてcell c0 , c1, c2 と移動した
c1 オブジェクトをカウント
cell ステップ３：確率のc0 計算

Qcount = 1

Pr(c2|c0, c1) = ―――――

Scount = 2０12345678 (= T )56

R-木を用いたカウント処理• アイデア：問題を制約充足問題（constraint satisfactionproblem, CSP）として定式化• 制約を満たすオブジェクトは，ある τ について以下の制約をすべて満たす– t = τ においてセル c0 にいた– t = τ + 1 においてセル c1 にいた–…
– t = τ + n においてセル cn にいた• n + 1 個のすべての制約条件を満たすオブジェクトを探索• R-木による空間制約充足解の探索手法（Papadias,VLDB98）を拡張
57

問合せ処理の例
x木のレベル root
a=2

セル c2
brootroot

c
セル c1
枝刈り

木のレベル=1

ターゲット
c1 → c1 → c2
c1 → c2 → c2

枝刈り

t1

セル c22

セル c1
枝刈り

木のレベル
=0

c1 → c1 → c2
以下のようにと移動した移動するオブオブジェクトがジェクトはない見つかった！
c1 → c1 → c2
カウントするc1 → c2 → c2

セル c2
セル c1

バックトラック

58

概要• 移動オブジェクトデータベース（MOD）とは• 研究事例：DOMINOプロジェクト• MODのデータモデル• MODの索引
移動ユーザのための適応型周辺情報提供手法• 問合せ処理• 我々の研究– 移動オブジェクトに対する適応的情報提供– 大量の移動軌跡からの移動統計量抽出法– 移動ヒストグラムの構築・管理手法
59

移動ヒストグラム（mobility histogram）• 移動パターンをコンパクトに要約する一種のヒストグラム• 与えられた移動パターンに対し，予測される出現数（選択率）を返す• マルコフ連鎖モデルを用いた移動パターンの表現• 表現– 論理レベル：データキューブ– 物理レベル：木構造
60

マルコフ連鎖モデル
遷移シーケンス

2(1)→3(1)→1(1)

遷移シーケンス

9(2)→12(2)→ 6(2)マルコフ連鎖モデルの概念（2次のマルコフ連鎖）
ステップ0のセル

ステップ1のセル

ステップ2のセル

61

論理的なヒストグラム

物理的なヒストグラム• n次元のマルコフ連鎖をn+1次元• 四分木（quadtree）とk-d-木を統合のデータキューブで表現した構造：各ノードにカウント保持• 0～3はグリッドセルの番号• 適応的に木を拡張・縮退– セルの粒度は細分化可能• 例：0→1→0という遷移の総数を矢印のキューブセルに格納

25336

110013821
01 10空間分割
レベル 100
114351
01 10
1つの枝が
11
1ステップに
53 00 10011293 対応110053801 10
空間分割
1100
レベル 201 1029900
2005/10/111001

38

1162

ヒストグラムの論理構造のイメージ
ｎ 次のマルコフ連鎖 → n+1次元のデータキューブ
Sumは各次元の値ごとの和を表す
1→1→0に対応する
step0

step1

step20

10 10

12

3223

3

空間を4分割した時の遷移
63移動ヒストグラムの物理構造• メモリを効率的に利用– データキューブの管理法の場合• 複数個のデータキューブが必要• セル数が多くなる（32×32のセルで2次のマルコフ遷移
すると，10億個のキューブセルが必要）• 出現しないシーケンスのセルの値は0– 出現したところだけにメモリを割り当てる• 木構造で表現– 木の各ノードは0個以上4個以下の子ノード– 各ノードにカウンタ
64

移動ヒストグラムの利用
分析・予測
要求

移動軌跡
データのストリーム…

ヒストグラム管理モジュール
インクリメンタルな更新

分析・予測結果の提示
移動分析・予測モジュール
予測・分析に利用

移動ヒストグラム65