FIT（情報科学技術フォーラム）2002

D-18
移動軌跡データモデルと領域に基づく問合せ処理
Query Processing for Topological Relation between Trajectory and Regions
柳沢 豊 †
Yutaka Yanagisawa1.

赤埴 淳一 †Junichi Akahani

はじめに

近年，GPS などの位置取得デバイスにより継続的に取得されたユーザの移動軌跡データを分析することで，ユーザの行動の特徴を抽出しようとする研究が進んでいる．たとえば，オフィス内を移動する多くのユーザの移動軌跡を分析すれば，オフィスの構造を最適化するための情報を得られると考えられる．同様に，車の移動軌跡データから交通渋滞の予測や，道路の新設の必要性などを検討する手がかりが得られる．
こうした分析を行うには，移動軌跡データの特徴を記述するための方法が必要になる．従来より，時空間上の図形るデータを扱えるデータベースである時空間データ
ベース [1] では，図形の特徴を記述するための方法が提案されている [2]．しかし，移動軌跡データのような複雑な形状をもつ，向きのある線分の特徴を記述し検索する方法についての議論は十分ではない．
そこで本論文では，文献 [2] で述べられている線分と領域との位相幾何学的関係を記述する方法を拡張し，有向線分と領域との間にできる位相幾何学的な関係を利用して，移動軌跡データの特徴を記述する方法を提案する．
さらに，この記述を用いて指定された移動軌跡データを検索するためのインデックス手法を提案し，手法の評価について述べる．

2.

 


λ1

λ4

λ1λ3



λ2 λ2

図 1: 移動軌跡データ
λ



λ1


図 2: 有向線分と領域との関係の例
移動軌跡は向きがある線分なので，従来の記法では関係の記述が不十分である．そこで本論文では，両端（始点と終点）が区別できるように，始点 ∂0 λ と終点 ∂1 λを用いて関係記述を拡張する．このようにすると，移動軌跡 λ と領域 R との位相幾何学的な関係は，∂0 λ, ∂1 λ,λ◦ と ∂R, R◦ , R− の共通部分の有無を表す 3 × 3 行列で記述できる．例えば図 2 のような関係 T (R, λ) は，次の行列として記述できる．
∂R ∩ ∂0 λ ∂R ∩ ∂1 λ ∂R ∩ λ◦
 R ◦ ∩ ∂ 0 λ R ◦ ∩ ∂ 1 λ R ◦ ∩ λ◦ R − ∩ ∂ 0 λ R − ∩ ∂ 1 λ R − ∩ λ◦

移動軌跡データ

移動軌跡 λ とは．質点が時間軸に沿って移動していった軌跡であり，空間 R2 上にプロットすると，向きと有限の長さをもつ曲線（あるいは直線）になる（図 1 左)．
しかし，実際にデータが取得される際には位置取得デバ
イスの性質上，移動軌跡データ λ̇ は時系列に沿って離散的に取得された座標情報の列になる（図 1 右)．空間上に描画された領域との位相幾何学的な関係を考える上では，移動軌跡データが離散的な数列のままでは扱いにくい．そのため，本論文では移動軌跡データを，離散的な座標データを連続化する方法として一般的に用いられる方法である折れ線近似 (Piecewise Linear Approximate)を用いて連続な有向線分にしておく．その上で，空間 R2上での向きと有限の長さをもつ線分 λ と境界のある連続な領域 R との位相幾何学的な関係について論じる．

3.

小暮 潔 ‡Kiyoshi Kogure

¬∅
= ∅∅

¬∅ ¬∅∅ ¬∅ ∅ ¬∅可能な行列の種類は 26 通り存在する．ここで，関係行列 TA (R, λA ) と TB (R, λB ) (ただし ∂1 λA = ∂0 λB )の間の演算である CONNECT 演算 TA • TB を次のように定義する．

A11 A12A13
A11=  A12A13

領域と移動軌跡との関係記述

空間 R2 上にある，端点のあるひとつの連続な線分 λと境界のある連続なひとつの領域 R との関係を記述する方法として，線分の両端 ∂λ，線分の内部 λ◦ = λ − ∂λと，領域 R の境界 ∂R，領域の内部 R◦ = R − ∂R，および R の外部 R− = R2 − R の共通部分の有無を 3 × 2行列として表す方法が提案されている [2]．

A21A22A23 
A31B11A32  •  B12A33
B13

B21
B22B23

A21 + A31 + B11 + B31
A22 + A32 + B12 + B32 
A23 + A33 + B13 + B33

B21B22B23
B31
B32 B33

この演算の導入により，26 通りの関係は図 4 に示す
基本的な 7 つの関係と CONNECT 演算の組み合わせで† 日本電信電話株式会社 NTT コミュニケーション科学基礎研究所‡ ATR メディア情報科学研究所

35

FIT（情報科学技術フォーラム）2002λλλ
図 4: 7 つの基本的な関係
図 3: CONNECT 演算の例

  

すべて表現することができる．例えば，図 3 の (c) のような関係 T (λc , R1 ) は，図 4 の各関係を表す行列式をそれぞれ EA , EB , . . . , EG とすると，CONNECT 演算を使って T (λc , R1 ) = EB • ED と記述できる．
領域が複数個ある場合の代表的な例として，図 2(B)のように，移動軌跡が片方の領域から出発してもう一方の領域へ入って終わる関係を考える．このような複数個の領域と移動軌跡 λ の関係は，移動軌跡 λ を適当に複数の移動軌跡の列 hλ1 , λ2 , . . .i に分割して，それぞれのλi が領域 Rj ともつ関係の列 T として表すことができる．例えば図 2(B) のケースでは，λ1 を λ2 , λ3 に分割し (ただし ∂1 λ2 = ∂0 λ3 )，hT (λ2 , R1 ), T (λ3 , R2 )i =hEB • ED , EE • EC i と記述できる．これは直感的には「λ1 を λ2 , λ3 に分割すると，λ2 と R1 の間の関係がEB • ED であり，λ3 と R2 の間の関係が EE • EC になる」という意味である．
図 2(B) のように複数の領域を順番に通過する軌跡を探すクエリは，複数の領域を通過する移動軌跡を探すもっとも基本的なクエリであり，本論文ではこれを PATHQuery と呼ぶ．

4.



図 5: グリッドを用いたインデックス

5.

評価

実験のために，グラウンドのような道路のない平面上を自由に歩く人間の移動軌跡に近い移動軌跡データを，シミュレーションによって作成した．このデータに対してインデックス付けおよび検索の実験を行った．データ
として 1000 個の座標データを含む，平均長が 50 km 前後の移動軌跡データ 1000 本を用意した．グリッドの一辺の長さを 5km に固定してインデックスを作成した．そして，ランダムに選んだ 2 つのグリッドを領域 R1 , R2とする PATH Query について，グリッドリンクを使う場合と使わない場合での検索速度の比較を行った．検索速度は，選ばれた 2 つのグリッド間の直線距離に反比例する．これは，グリッドが近いほどそれら双方を通過する移動軌跡の数（＝計算対象）が増えるためである．比較の結果，グリッドリンクを用いると用いない場合に比べて，平均 6.45 倍，グリッドが隣接する場合で 10.38倍高速に検索することができた．

グリッドリンクを用いたインデックス

以下では PATH Query を効率的に計算するためのインデックスの作成手法について述べる．線分を扱うデー
タベースでは，グリッドを使って線分をグリッドごとに分割し，インデックスをつける方法が一般的である [1]．
グリッドによるインデックスを用いると，特定の領域を通過する線分を探すクエリに対して，まずその領域を含むグリッドを探し，そのグリッド内を通る線についてだ
け指定された領域を通るかどうかを判別すればよいため，検索効率が大幅に向上する．
一方，PATH Query のような複数の領域を指定した順序で通過する移動軌跡を探すときには，領域を通過するかどうかのチェックに加え，通過する順序についてのチェックが必要になる．このチェックのコストを下げるた
めに，本論文では図 5 のように，各移動軌跡ごとにそれが通過するグリッドの順序を予め記録しておく，グリッドリンクと呼ぶ方法を導入する．これを用いると，複数の領域を指定された順序で通過する PATH Query を計算するときには，最初の領域を含むグリッドをまず探し，次にグリッドを通過する各移動軌跡のグリッドリンクをたどり，2 番目以降に通過する領域を含むグリッドを順番に通過しているかどうかを調べればよい．これにより通過順序のチェックが簡単化され，PATH Query の検索効率の向上を図ることができる．

6.

まとめ

本論文では，移動軌跡データを空間上の有向線分としてモデリングし，空間上の複数の領域と線分との間にできる関係を行列式を用いて記述することで，移動軌跡の特徴を一意に記述する方法について述べた．また，指定された条件を満たす移動軌跡データを探すためのインデックスの作成方法についても述べた．今後は実際に GPSなどで取得したデータに対して提案方式を適用し，評価を行う予定である．

参考文献[1] H.D. Chon, D. Agrawal, and Amr El Abbadi:
Query Processing for Moving Objects with SpaceTime Grid Storage Model, In Proc. of MDM2002,
pp.121–129 (2002).
[2] M. Egenhofer, E. Clementini, and P. di Felice:
Topological Relations between Regions with Holes,
Intl. Journal of Geographical Information Systems,Vol. 8, No. 2, pp.129–142(1994).

36