DEIM Forum 2016 H7-1

文字列索引によるネットワーク制約下の車両軌跡の索引化
小出 智士†

田所 幸浩†

吉村 貴克†† 株式会社 豊田中央研究所 〒 480–1192 愛知県長久手市横道
E-mail: †{koide,tadokoro,yoshimura}@mosk.tytlabs.co.jp
あらまし GPS ロガーなどを通じて大量に収集される車両の軌跡データを，走行経路および走行時間帯を考慮して適切に管理することは，車両から収集されるデータを利用したアプリケーションのための基盤として重要である．本論
文では蓄積された車両軌跡データに対する，完全経路クエリと呼ばれる時空間検索を行うためのデータ構造を提案する．提案手法は車両が基本的には道路上のみを走行することに着目し，軌跡をグラフ辺を文字とする文字列として扱うことで文字列パターンマッチの問題に帰着させる．さらに車両軌跡データに含まれる時間情報を取り扱うために逆
接尾辞配列を用いて，時刻情報を格納する B+ 木 と文字列索引である FM-index を統合する方法を提案する．提案手法の有効性を示すために実データを用いた比較評価を行い，特に経路クエリ長が大きな場合に従来法と比較して高速に解を得られることを確認した．
キーワード

時空間索引，ネットワーク制約軌跡，完全経路クエリ，逆接尾辞配列，FM-index

1. は じ め に

T0

近年，自動車などの移動体から収集されるデータの量および種類が爆発的に増大してきており，それらのデータを活用したアプリケーション開発への期待が高まっている．そのような応用の例としては例えば，車両軌跡データを用いてタクシードラ

a

b

c

T1

T2

イバーの経路選択行動を学習するようなスマートナビゲーショ
ン [19] や，低コストのセンサ (車載カメラなど) のデータを統合することで地図を作成する技術 [7] などが挙げられる．このような技術の開発においては収集・蓄積された大量の車両軌跡

d

e

f

T3

データに対して，欲しいデータを必要に応じて高速に検索し，

図 1 6 つの道路リンク E = {eab , ebc , ebd , ece , ede , eef } からなる道

取り出すことができるよう適切に管理されていることが重要で

路ネットワーク上を移動する 4 つの軌跡 (T0 ∼ T3 ) の例

ある．車両軌跡データの検索に特有の問題として，時空間コン
テキスト (車両の走行経路および走行時間帯) を考慮した検索が必要になるという点がある．

に着目する．これは時刻 s から t の間にクエリ経路パターン Pで走行した車両 (の ID) をすべて列挙する，という問い合わせ

空間索引の多くはユークリッド空間内の点として表現されるである (厳密な定義については後述する) ．ただし，クエリ経路

位置情報に対して構築される．車両軌跡データにおいても通常，

パターン P は辺集合 E 上の記号列である．後に 3. 1 節で詳し

位置情報は GPS ロガーなどから得られる緯度経度の座標列とく見るように，この完全経路クエリを素朴な方法で解こうとすして収集される．しかしながら，自動車は基本的には道路ネッ

ると，経路クエリ長 |P | に比例したディスクアクセス (B+ 木トワーク上のみを走行することに着目すれば，位置情報は (道の探索) およびデータの結合 (join) が発生し，特に |P | が大き

路ネットワークを有向グラフ G = (V, E) と考えた場合の) グ

な場合について高速に解くことができない，という問題がある．

ラフ辺の列として表現することができる．このような軌跡の表

ネットワーク制約軌跡は E の要素を文字とする (時刻付き

現はネットワーク制約軌跡と呼ばれる．図 1 に道路ネットワーの) 文字列であるとみなすことができる．従って軌跡に対する

ク上を移動するネットワーク制約軌跡の例を示す．例えば，軌検索は，ある種の文書検索の問題とみなすことができる．我々

跡 T0 は eab → ebc → ece → eef のように走行している．車両

はネットワーク制約軌跡に対する索引を全文索引を利用して構の位置を緯度経度ではなく，道路リンクの列として取り扱うこ成することを試みる．しかしながら全文索引は記号列 (道路リとは多くのアプリケーション (ナビゲーションなど) にとってンク列) の検索を実現するものであり，それに付随する時間的

最も自然なものであると考えられる．以上のことから，我々はな検索条件を考慮できない．そこで我々の提案手法では全文索ネットワーク制約軌跡に対する索引化・検索の問題について考引として FM-index を用い，時刻などの情報は B+ 木に格納える．

する，というハイブリッド構造を採用する (図 2 に提案手法の本論文では時空間コンテキストを考慮可能なクエリの中で，最もシンプルである 完全経路クエリ (Strict Path Query; SPQ)

概要を示す) ．FM-index は与えられたパターン P に対応する

㌶㊧䝕䞊䝍䠄⦋ᗘ⤒ᗘ䠈᫬้䠅a䝬䝑䝥䝬䝑䝏䞁䜾

ᩥᏐิ໬䛥䜜䛯㌶㊧b䠄᫬้᝟ሗ䠅

P

䠄఩⨨᝟ሗ䠅

&DͲŝŶĚĞǆ

䠄᥋ᑿ㎡᝟ሗ䠅cdнͲƚƌĞĞ

ef

図 3 図 1 のネットワークにおける P = ebd → ede の完全経路クエ
リ．P の最終ノードでの時刻について制約する．

図 2 提案する索引構造の概要

接尾辞配列上の範囲を高速に返すことができるが，時間に関する情報を保持できないため，時刻を含めたクエリを実行できな

2. 2 完全経路クエリ

い．そこで逆接尾辞配列を用いて，空間パターンを索引化する

ここでは完全経路クエリの厳密な定式化を行う．1 章で述べ

FM-index と時刻などを索引化する B+ 木を対応付けることでたように，完全経路クエリは定性的には時刻 s から t の間にク

完全経路クエリを処理する方法を提案する．この結果，ディス

エリ経路パターン P で走行した車両 (の ID) をすべて列挙す

クアクセスのコストが経路クエリの長さ |P | に依存しない方法

る，という問い合わせである．

を実現することができ，高速化を達成することができる．
本論文の構成は以下のとおりである．2 章では軌跡の表現および問題設定を述べる．3 章ではネットワーク制約軌跡に関する索引，および文字列検索に関する関連研究を述べる．4 章では提案手法を説明する．5 章では実際のプローブカーデータを用いた評価実験の結果を示す．6 章および 7 章では手法および結果に関する議論および結論を述べる．なお，本研究についての詳細は [9] を参照されたい．

定義 1. D 個の軌跡の集合 T = {Td | 0 <= d < D} を考える．問い合わせ経路 P は長さ m の E 上の配列とする:

P := p0 p1 · · · pm−1 . 本論文では完全経路クエリ (Strict Path
Query) を以下のように定義する：
SP Q(P, s, t) := {d | ∃i, j : Td .e[i, j) = P ∧outs<= Td .t [j − 1] < t}.

(1)

すなわち，完全経路クエリ SP Q(P, s, t) は部分的に P とい2. 問 題 設 定うパターンで走行し，かつ P の最後のリンク pm−1 を通過し終えた時刻が s と t の間に含まれるような T の軌跡を抽出す

2. 1 軌跡表現の定義
本論文では道路ネットワークを有向グラフ G = (V, E) として表す．ここでは道路ネットワークは時間とともに変化しないと仮定する．道路ネットワーク上の車両の位置情報は 4 要素からなるようなクエリである．
再 び 図 1 の 例 に 戻って 説 明 す る ．ク エ リ 経 路 パ タ ー ン

P = ebd → ede および [s, t) = [18, 25) の場合，SP Q(P, s, t)

るタプル (d, e, tin , tout ) として表現されるものとする．ただし，は道路リンク ede を出た時刻，すなわち交差点ノード e での時

d は軌跡 ID, e ∈ E は通過した道路リンク，tin , tout は軌跡 d が刻が [18, 25) の間にある軌跡に対応する (図 3)．なお，時刻の道路リンク e に入った時刻および出た時刻である．ネットワー
n −1

out
d
ク制約軌跡は上記の位置情報の列 Td := {(d, ei , tin
i , ti )}i=0として定義される．軌跡 Td の道路リンク列のみを取り出すた
めに，Td .e := e0 e1 · · · end −1 のような表記を用いる．また，車両はネットワーク上を連続的に動くものとする．従って ei と

ei+1 は隣接した道路リンクであるものとし，また tout
= tin
i
i+1

制約の仕方としては P 全体が [s, t) に含まれる，すなわち Pの最終ノードのみではなく，最初のノード (先の例ではノードb) の時刻も制約する，というクエリも考えられる．実際，関連研究 [10] ではそのようなクエリのみを考えている．4. 6 節で示
すように，我々の方法は簡単な拡張によってそのようなクエリにも対応できることを強調しておく（注 1）．

である．
先に述べたように本論文では軌跡を文字列として扱う．従って道路リンク集合 E には辞書順が定義されているとする．実際には，この順序の設定には特に制約はなく，任意の順序を用いてよい．
また，配列 A に対して，i 番目の要素を A[i] と表し，A[i, j)
を i 番目から j−1 番目までの部分配列とする．従って，上で述べたネットワーク制約軌跡に対しては Td .e[i, j) = ei ei+1 · · · ej−1となる．また本論文を通して，配列などの添字は 0 から始まるものとする．

3. 関 連 研 究
3. 1 ネットワーク制約軌跡の索引付け
ネットワーク制約軌跡に対する索引構造の研究としては FNR-

tree [5] がある．これは道路リンクごとに車両が該当の道路リンク上に存在した時間区間を R 木で管理するという索引構造である．ここでは時空間矩形クエリを対象にしており，完全経路ク（注 1）：ただし両者の結果は非常に似通っている場合がほとんどであるため，厳密に時間幅を限定したい場合を除いてはあまりメリットはなく，より高速に解くことができる我々の定義 (1) で十分である．

エリのような経路に関するクエリは明示的には考慮されなかっ|T | log σ + o(|T |) ビットであり，元のテキストと同程度のサイ

た．Vieira らによって提案された索引構造 [17] は FNR-tree とズで元のテキストと索引の両方を格納できる．このサイズは類似の構造を用いるが，対象とするクエリの範囲が拡張されてデータ圧縮することで，同等の検索機能を持ったまま，さらにいる．具体的には，フレキシブルパターンクエリ (FPQ) と呼小さくすることができることが知られている [8], [12]．接尾辞

ばれる完全経路クエリを含むクエリを定義し，FPQ に対する配列および FM-index を含む文字列索引の話題については，例

IJP (Index-Join Pattern) アルゴリズムが提案された．しかし，

えば [20] が詳しい．

IJP アルゴリズムは文書検索に対する転置インデックスと類似のアルゴリズムであり，クエリ長 |P | に比例するディスクアク

3. 3 XML ドキュメントに対するパス検索

セスおよびマージが発生し，完全経路クエリに対しては高速で

経路およびそれに付随する属性を検索する関連技術として（注 2）あるとは言えない．

XML ドキュメントに対するパス検索の技術が挙げられる．例

Krogh らは完全経路クエリを初めて明示的に定義し，その索

えば Yoshikawa らによる XRel [18] では RDB を用いて XML

引構造を提案した [10]．この論文では大別して二種類のアルゴ

文書を索引化し，パス検索を実現している．その構造は非常にリズムが提示されている．一つは完全経路クエリに対して厳密

柔軟であり，様々な属性とパスを同時に取り扱うことができる．

な結果を返す，IJP アルゴリズムに類似のアルゴリズムである．

また原理的には (XML パスを車両経路と読み替えることで) 完

従って，クエリ長 |P | に比例するディスクアクセスおよびマー

全経路クエリに対しても適用可能である．しかしながら XRel

ジ操作が発生する．もう一つは近似アルゴリズムであり，ディでは文書内に存在するパスの全ての接頭辞を格納するため，極スクアクセスが |P | に依存しない検索を実現する．しかし，こめて多種類の接頭辞が出現し得る車両経路データに対して適用の方法は軌跡に対するハッシュ関数を定義する方法であり，検することはあまり効率的でないと考えられる．

索結果にはハッシュの衝突に起因する誤検出が含まれる可能性

一方で XML 文書のような構造化文書に対するデータ構造はがある．本研究では Krogh らの手法では実現できない，ディ(例えば加速度や画像など，時間以外の要素を含む) 本研究で対スクアクセスが |P | に非依存，かつ厳密な結果を返すことがで象とするデータよりも複雑な属性で構成される現実の車両デーきる手法を提案する．

タの格納や検索などを考慮する場合に役立つ可能性があることを強調しておく．

3. 2 文字列索引
文字列におけるパタンマッチングは多くの既存研究がある．
ここでは本研究で用いる接尾辞配列および FM-index に関連す

4. 提 案 手 法
4. 1 前 処 理

る話題について述べる．
接尾辞配列は文字列処理にとって重要なデータ構造であり，通常，位置情報データは GPS ロガーなどから得られる

文字列 T の接尾辞を辞書式順序で並び替えたときの接尾辞の

緯度経度座標として与えられるため，これを適切に前処理

ソート前の順序 (添字) として定義される．接尾辞を並び替え

し，ネットワーク制約軌跡表現を得る必要がある．本研究でたことで，以下のよく知られた重要な性質が得られる：任意のは，隠れマルコフモデルに基づくマップマッチング手法 [14]部分文字列パターン P が T に出現する位置は接尾辞配列 SAを用いて緯度経度を道路リンクの列に変換した．これによ上の連続した範囲 SA[sp, ep) として与えられる．

り，緯度経度座標 (x1 , y1 ), (x2 , y2 ), · · · に対応する道路リン

FM-index は Ferragina らによって提案された全文索引であク列 e1 , e2 , · · · が得られる．この際，ei と ei+1 が隣接した

り，圧縮された文字列上での高速なパタンマッチを可能にす

道路リンクでない，ということが起こり得る．これは主に緯る [4]．これは Tbwt [j] = T [SA[j] − 1] で定義される Burrows-

度経度座標の時刻の間隔が大きい時に発生する．これを修Wheeler 変換 [2] をウェーブレット木 [6]（注 3）に格納すること正する方法としては例えば，半教師付き学習の枠組みを用いで得られるデータ構造である．この索引構造を用いると与えて (ei , ei+1 ) → (ei , ei+1/n , ei+2/n , ei+(n−1)/n , ei+1 ) のようにられたパターン P に対して，上で述べた文字列 T に出現すギャップを埋める方法がある [11]．本研究ではマップマッチン

る P の対応する接尾辞配列上の範囲を文字列長 |T | に依存

グアルゴリズム [14] の仮定に基づき，このようなギャップを最しない O(|P | log σ) の時間で求めることができる．ここで σ

短経路で補間した．

はアルファベット集合のサイズであり，我々の問題設定におい時刻に関しては軌跡の経路に沿って GPS の点が射影されたては道路リンク集合のサイズ |E| となる．また空間複雑性は点の距離を用いて線形補間することで，tin および tout を得た．

（注 2）：文書検索における転置インデックスでは典型的にはポスティングリスト
が文書 ID 順に並んでいるため，高速なマージが可能である [13]．一方で IJP
アルゴリズムでは時刻に関する B+木の索引で絞り込んだ複数のリストをマー

4. 2 移動パターンの索引化
ネットワーク制約軌跡の集合 T = {Td | 0 <= d < D} を考ジするため，ソートが必要になる点も非効率である．

える．ここでは空間的な移動パターンのみの索引化について述（注 3）：本研究で取り扱うアルファベット集合は道路リンク集合 E であり，通常

べる．軌跡 d の移動パターン Td .e に対して，順序を反転させ|E| は数万〜数百万である．これは自然言語の場合よりもかなり大きい．今回は大きなアルファベット集合に対しても適用可能なポインタのないウェーブレット

た配列を Rd := reverse(Td .e) とする．既に述べたように，こ木 [3] を用いた．

れは道路リンク集合 E 上の文字列 (文書) とみなすことがで

きる．そして得られた文書集合 {Rd } を特殊文字 $ を用いて

表 1 軌跡 ID，時刻情報，逆接尾辞配列などを格納するテーブルの構

結合した文字列を 軌跡文字列 Y := R0 $R1 $ · · · $RD−1 $ と定造．(e, tout ) のペアに対して B+ 索引を構築する．格納された義する．ただし，$ は道路リンク集合 E に含まれるどの道路

4 つの軌跡は図 1 の例に対応する．

リンクよりも辞書式順序が小さいものとする．図 1 の例では

i

d

e

tin

tout

ISA[i]

Y = eef ece ebc eab $eef ede ebd eab $eef ede ebd $eef ede $ となる．こ

0

0

eef

18

23

13

の軌跡文字列に対して FM-index を構築する．このようにして

1

0

ece

12

18

9

構築された索引を提案手法における空間索引と位置づける．

2

0

ebc

9

12

6

3

0

eab

5

9

5

4

— $

—

—

3

5

1

eef

19

22

16

6

1

ede

13

19

12

このとき，P を反転させた文字列 Prev := reverse(P ) に対応

7

1

ebd

10

13

8

する接尾辞配列上の範囲を [sp′ , ep′ ) とすると SA[sp′ , ep′ ) は

8

1

eab

6

10

4

元の軌跡文字列 Y 上で Prev が出現する位置のリストを過不足

9

— $

—

—

2

なく表している．このことより以下の補題が成り立つ．

10 2

eef

16

19

15

11 2

ede

11

16

11

補 題 1. 軌 跡 文 字 列 Y に 対 し て 長 さ m の ク エ リ 経 路 パ

12 2

ebd

8

11

7

ターン P を反転させた Prev に対応する接尾辞配列上の範13 — $——

1

囲を R(Prev ) := [sp′ , ep′ ) とする．このとき，j ∈ R(Prev ) と

14 3

eef

9

15

14

Y [SA[j], SA[j] + m) = Prev は同値である．

15 3

ede

15

21

10

—

—

0

3. 2 節で述べたように，この FM-index は与えられたパター
ン P に対応する接尾辞配列上の範囲 [sp, ep) を高速に返すことができる．軌跡文字列 Y の接尾辞配列を SA[0, |Y |) とする．

16 — $

こ こ で ，接 尾 辞 配 列 SA の 逆 関 数 で あ る 逆 接 尾 辞 配 列

ISA を考える．すなわち，任意の 0 <= j <= |Y | に対して
ISA[SA[j]] = j である．このとき，補題 1 を j = ISA[i],る．従って，表 1 の e-列は Y に一致する．
このテーブルの道路リンク e と道路リンクを出た時刻 tout のSA[j] = i を用いて書き換えることで以下が成り立つ．

二つの列のペア (e, tout ) に対して，B+ 木 を用いて索引化して

命 題 1. 軌 跡 文 字 列 Y に 対 し て 長 さ m の ク エ リ 経 路 パ

おく．このような構造化はネットワーク制約軌跡のための索引

ターン P を反転させた Prev に対応する接尾辞配列上の範化の手法として FNR-tree [5] や Vieira らの研究 [17]，Krogh

囲 R(Prev ) := [sp′ , ep′ ) とする．このとき，ISA[i] ∈ R(Prev )らの研究 [10] で用いられているものと本質的には同じである．

と Y [i, i + m) = Prev は同値である．
この命題が示唆するのは，もし Prev に対応する範囲 R(Prev )を予め知っており (これは FM-index で高速に求められる) ，そ′の上で位置 i の ISA[i] を sp′ <= ISA[i] < ep のようにチェッ

クすれば，位置 i が Prev にマッチするかどうか (したがって
逆順で見た時に P にマッチするかどうか) を一つのスカラー値に関する不等式で判定できるということである．提案手法のキーとなるアイデアは，この ISA[i] の値を時刻や軌跡 ID を格納するディスク上のデータベースに格納するということである．これにより走行した経路パターンとそれ以外のデータが紐付けられ，高速な検索が可能になる．以下の節ではこれらについて詳細に説明する．

4. 3 時刻情報の索引化
議論を簡単にするために，時刻その他の情報は表 1 のようなテーブルに格納されているものとする．このテーブルには図 1で用いたものと同じ 4 つの軌跡に対応するデータが格納されている．各行は 2. 1 節で定義したタプル (d, e, tin , tout ) に対応しており，軌跡 ID d, 道路リンク ID e, 時刻 tin , tout の他に i,

ただし，既存研究では逆接尾辞配列 ISA の値は格納されていない（注 5）．

Vieira らが提案した IJP アルゴリズムでは，はじめにパター
ン P = p0 p1 · · · pm−1 に含まれる各 pj に対して，道路リンク

ID e が pj に一致する軌跡 ID のリストを (必要があれば時刻
tout に関する条件を考慮して) m = |P | 個のリストを抽出する．
これは (e, tout ) 上に構築された索引によって比較的高速に実行できる．その後，転置インデックスにおける文書検索と同様の方法で |P | 個のリストの共通部分を取ることで解を得る．この方法では B+ 木 の探索回数が最大で |P | となるので，大きな|P | を持つクエリでは明らかに非効率である．また |P | 個の各リストは軌跡 ID 順にソートされていないため，リストの結合にも大きなコストがかかってしまうという問題がある．

4. 4 完全経路クエリのためのアルゴリズム
本研究ではテーブルに追加された逆接尾辞配列の値を用いて効率的な探索を行う．完全経路クエリ SP Q(P, s, t) を考える．まず P の反転文字列 Prev に対して，4. 2 節で構築した軌跡文字列 Y の FM-index を用いて接尾辞配列上の範囲

ISA[i] の列を持っている．ここで i は軌跡文字列 Y 中の位置に対応し，ISA[i] は Y の逆接尾辞配列（注 4） の i 番目の値であ（注 5）：Krogh らの方法 [10] では ISA の代わりに軌跡から計算されるハッシュ
値を格納することで近似的な検索を可能にする．提案手法はこのハッシュ値の（注 4）：この例では，道路リンク集合 E 上の順序をリンク添字の辞書式順序で定フィールドを逆接尾辞配列に取り替えることで厳密な検索を実現するものとみな義している．例えば ebc < ede である．

すことができる．

R(Prev ) = [sp′ , ep′ ) を求める．次に 4. 3 節で定義したテーブ
ルに対して，•

道路リンク ID e がクエリ経路パターン P の最後の道路

セグメント pm−1 と一致し，•

out
時刻 tout が s << t を満たし，
=t

•

′
sp′ <
= ISA[i] < ep を満たす

また，以下の性質はアルゴリズムの手続きより自明である．
性質 2. (ディスクアクセス) 提案アルゴリズムは任意の経路パターン P および時間幅 [s, t) に対して，(e, tout ) を索引化する

B+ 木を一度だけ探索する．
この性質は 4. 3 節で述べた IJP アルゴリズムが |P | 回の探ような行の軌跡 ID を取り出す．最初の二つの e および tout に索を必要とすることと対照的である．また，Krogh らによる近関する条件は前節で説明した B+ 木 の索引によって高速に実似検索アルゴリズム [10] は (|P | に依存しない) 二度の B+ 木

行可能である．それらのデータの中で最後の条件を満たすものの探索で 近似的な結果 を返すものである．一方，提案手法はが SP Q(P, s, t) の解である．この最後の条件は後述するよう•厳密な結果，に，空間的な経路パターンのマッチングに対応している．この•|P | に依存しない B+ 木 の探索回数，

方法を表 1 (tbl とする) に対する SQL として表現すると以下のように非常にシンプルになる：を両立することができる．
性質 3. (時間複雑性) 提案手法の時間複雑性は O(|P | log |E| +out
SELECT d FROM tbl WHERE e = pm−1 AND s << t AND= t′ <′sp = ISA < ep ;log |Y | + |U |) である．ただし U は性質 1 の中で定義したもの

次節でこの方法が正しいことを示すが，ここでは表 1 の例

ここで |P | log |E| の項は FM-index の検索に対応し，これはを用いて説明する．2. 2 節で用いた P = ebd → ede およびメモリ内で実行されるため極めて高速であるため，実験の章で見[s, t) = [18, 25) の例について再度考えてみる．まず，Prev にるように，実践的には所要時間の |P |-依存性は生じない．なお，

′

′

である．

対応する接尾辞配列上の範囲は [sp , ep ) = [11, 13) となる (具log |Y | + |U | は B+ 木に関する時間複雑性である．一方で，IJP体的な計算は省略する) ．次に P の最後の要素である ede をアルゴリズムの時間複雑性はおおよそ O(|P | log |Y | + |P | · |U |)

走行し，かつ tout が [18, 25) に含まれる要素を取り出す．そのである．ただし，|P | log |Y | の項は B+ 木の |P | 回の探索に対結果，i = 6 行目および，i = 15 行目が抽出される．i = 6 の応し，|P | · |U | の項はマージに対応する．

とき，ISA[6] = 12 ∈ [11, 13) なので，この行 (軌跡 ID d = 1)
はアルゴリズムによって抽出される．一方，i = 15 のとき，

4. 6 その他のクエリの取り扱い

ISA[15] = 10 ∈/ [11, 13) なので，この行 (軌跡 ID d = 3) は提案した索引構造を用いて，これまでに扱ってきた完全経路

アルゴリズムによって抽出されない．すなわち，d = 1 のみがクエリとは別のクエリも取り扱うことが可能である．例えば，

SP Q(P, s, t) の解として抽出されることになる．実際，d = 3

Krogh らによって提案されたオリジナルの完全経路クエリの定の軌跡は ede を [18, 25) に通過するものの，ebd → ede という義は以下のように本論文のものとわずかに異なる [10]：経路を走行していない．また，軌跡 ID d = 2 は ebd → ede のように走行しているものの，ede を出た時刻が 16 ∈/ [18, 25) な

SP Q′ (P, s, t) := {d | ∃i, j : Td .e[i, j) = P ∧
in
out
s<
= Td .t [i] ∧ Td .t [j − 1] < t}. (2)のでやはりマッチしていない．したがって，提案アルゴリズム
は正しい結果を返していることがわかる．

4. 5 提案手法の性質
本節では提案手法が持ついくつかの性質を示す．はじめに，
アルゴリズムの正しさを示す．

すなわち，本論文の定義 (1) では P の最後の道路リンクを出た時刻のみを制約するのに対して，Krogh らによる定義 (2) では P 全体を出入りした時刻を制約する．式 (2) の時刻の条件
は式 (1) よりも厳しいため，SP Q′ (P, s, t) ⊂ SP Q(P, s, t) が成立することがわかる．従って，まず SP Q(P, s, t) を提案手法

性質 1. (結果の厳密性) 4. 4 節で示したアルゴリズムは厳密なによって求めておき，次に道路リンク p0 を時刻 [s, t) 内に通SP Q(P, s, t) の解を返す．

過した軌跡 ID を求め，最後にそれらを適切に結合 (join) する

Proof. 4. 4 節で示したテーブルに対する三つの検索条件のうち，最初の二つにマッチする集合を U とする．条件の設定の仕方
から，SP Q(P, s, t) は明らかに U に包含される．U に含まれる軌跡のうちで SP Q(P, s, t) に含まれないものがあるとするならば，それは pm−1 以前に走行した経路パターンが p0 p1 · · · pm−2にマッチしないような軌跡である．そのような false positives′を取り除くために sp′ <= ISA[i] < ep の条件を用いている．実際，この条件にマッチすることは命題 1 より Y [i, i + m) = Prev′と等価なので，U に対して sp′ <= ISA[i] < ep でフィルタリ

ングしたものは SP Q(P, s, t) と等しいことが言える．

ことで SP Q′ (P, s, t) を求めることができる．この方法では p0に関する処理においても B+ 木を探索する必要があるため，合計 2 回の B+ 木の検索が発生し，我々の完全経路クエリのアル
ゴリズムよりも約二倍遅くなる．
また，二つの経路 P1 , P2 およびワイルドカードを表す経路P∗ に対して P1 P∗ P2 にマッチする経路の検索なども IJP アル
ゴリズムの考え方と提案手法の考え方を組み合わせることで実現可能である．

5. 3 結果

軌跡集合 T から長さ |P | = 2, 5, 10, 20 の走行パターンをランダムサンプリングし，500 個のクエリ走行パターン P を作成した．時間制約 [s, t) に関しては 2014-02-01 0:00 から，7 日間，30 日間の 2 パターンのクエリに関して実験を行った．図

5 は 500 個のランダム軌跡クエリに対する平均応答時間を示している．横軸にはクエリ走行パターンの長さ |P | をとっている．
本論文における完全経路クエリの定義は Krogh らによるオリジ
ナルの定義と異なるため，4. 6 節で述べた，提案手法を応用した方法によってオリジナルの完全経路クエリに要した所要時間も同時に示している (図 5 内 “Proposed (Original definition)”)．
我々の完全経路クエリの定義による結果は “Proposed (Our
図 4 マップマッチングに利用した地図 (ローマ市内，リンク数 56653)．
色はデータの分布を示している．

definition)” として図 5 に示した．
図 5 からは，提案手法においては |P | が増加しても所要時間が増加しないのに対し，IJP アルゴリズムでは |P | に従っ

4. 7 索引の構築
最後に，提案した索引の構築方法について説明する．まず，

4. 1 節の方法に従って，車両軌跡データを前処理する．得られたネットワーク制約軌跡に対して軌跡文字列 Y を構成し，接尾辞配列 SA を例えば [15] の方法を用いて計算する．この接尾辞配列を用いて FM-index を構築することができる．同時にSA から逆接尾辞配列 ISA を定義通りに計算し，表 1 のように B+ 木を構築することで提案した索引を構築することができる．

て処理時間がほぼ線形に増加することがわかる (図 5 中 “IJP

(Original definition)”)．この IJP アルゴリズムの結果は 3. 1
節で述べたように，各 pi ∈ P に対して B+ 木 を |P | 回探索する必要があることに起因する．また，この増加量の傾きは 4. 5
節で述べたように，log |Y | + |U | に比例するので，データが大きくなると提案手法との差はより大きくなると考えられる．
一方で提案手法のクエリ処理時間は |P | と共に増加することはないが，このことは以下のように説明できる．提案手法の時間
複雑性は O(|P | log |E| + log |Y | + |U |) であったが，|P | log |E|の項は FM-index の検索 (接尾辞配列上の範囲 [sp′ , ep′ ) を求めるアルゴリズム) にかかるものである．これはメモリ上で処

5. 実

験

5. 1 データセット
イタリアのローマ市内を走行したプローブカーデータ [1] を200

クシープローブの 2014 年 2 月の走行履歴であり，GPS のサンQuer y Interval: [s ,t)
7days
30days

プリングレートは平均 7 秒である．このデータを 4. 1 節で述べ

Method用いて実験を行った．このデータセットにはおよそ 320 台のタ

た隠れマルコフモデルによるマップマッチングの方法を用いてには 130,000 を超える数の軌跡が含まれており，軌跡文字列の長さはおよそ 12,000,000 となった．なお，道路ネットワーク
としては 56653 本の有向エッジからなる OpenStreetMap（注 6）のデータを用いた (図 4)．

5. 2 実装提案手法および IJP アルゴリズム (Krogh らの厳密手法と同

Average query time (ms )

前処理し，ネットワーク制約軌跡の集合 T を得た．このデータ

150

IJ P (Original definition)
P ropos ed (Original definition)
P ropos ed (Our definition)

100

50

等のもの) による比較を行う．すべての手法は C++ によって実装し，g++ version 4.6.3 (-O3 オプション) によりコンパイルを行った．ただし，ディスク上の B+ 木 としては sqlite3 を用いた．すべての実験結果は Intel Xeon W5590 CPU (3.33 GHz,8 コア)，8 GB のメモリを搭載した Ubuntu Linux (12.04) 上で実行した．

0
5

10

15

20

Q uery length: |P |
図 5 完全経路クエリに対する所要時間 (ミリ秒, 500 クエリの平均)（注 6）：www.openstreetmap.org

Average query time (ms)などの技術を用いることで，より大きなデータセットも取り扱うことができると考えられる．
0.10

6. 2 クエリ最適化
前節において，提案手法は既存技術と比較して高速に完全経0.05

路クエリを処理することを見たが，ここではクエリ最適化について簡単に議論を行う．例えば 4. 4 節で述べた 3 つのフィルタ

0.00
5

10

15

20

Query length: |P|
図 6

out
リング条件のうち，時刻に関する条件 s << t および逆接=t′
尾辞配列に関する条件 sp′ <= ISA[i] < ep の適用順序を逆にすることが考えられる．ISA に対してインデックスを作成し軌跡文字列 Y に関する FM-index に対して接尾辞配列上の範ておけばこの順序でも高速にフィルタリング可能である．高速囲を求めるのに要した時間 (ミリ秒, 500 クエリの平均)

out′化のためには s << t および sp′ <=t= ISA[i] < ep の条件のうちで，ヒットするレコードの件数がより少なくなると見積木の探索にもれるものを最初に用いてフィルタリングすればよい．後者のかかる時間と比較してほとんど無視できる程度のものである．

条件の件数は ep′ − sp′ であり，前者の件数は時間幅 t − s に

このことを示すために，FM-index の検索に実際に要した処理

比例するため，これらの件数をおおよそ見積もることが可能で時間を図 6 に示す．この結果より，FM-index の検索に要するあり，これによりクエリ最適化を実現できる．

理されるために，ディスクアクセスの発生する B+

時間は |P | に比例して大きくなるものの，高々数十マイクロ秒程度であり，全体の処理時間よりも二桁以上小さいことがわ

6. 3 データ構造の最適化: 道路 ID e-列の除去

かる．

実は逆接尾辞配列の情報を保持しておけば，表 1 における e

また，同じ提案索引構造を用いた場合でも，本研究における完の列をデータベースに格納する必要がないということが言える．

全経路クエリの定義式 (1) と既存研究 [10] での定義式 (2) では

この理由は以下のとおりである．まず，命題 1 より任意の道路

所要時間がおよそ二倍ほど異なる (それぞれ図 5 内 “Proposed

リンク a ∈ E に対して Y [i] = a と C[a] <= ISA[i] < C[a + 1]

(Our definition)” および “Proposed (Original definition)” には同値であることがわかる．ただし，C[a] は a よりも辞書

対応)．これは既に 4. 6 節で述べたとおり，オリジナルのクエ順が小さい道路リンクが軌跡文字列 Y において出現した

リを提案手法を用いて解く場合には二回の B+ 木の探索が必要回数である．つまり表 1 のある行が a にマッチすることはになるためである．しかしながら，処理時間が |P | に依存しな

C[a] <= ISA[i] < C[a + 1] を調べればよいので e を格納しておい，という性質は同様である．

く必要はないことがわかる（注 7）．すなわち (ISA, tout ) の組に

さらに，図 5 からは時刻制約 [s, t) の期間が長くなると，既存手法，提案手法の両方において所要時間は増加するという傾対して B+ 木 を構築すれば本論文で提案したアルゴリズムを実行するのに十分であることが言える．

向が見てとれる．これは期間 [s, t) が長くなるに従って，返さ逆に e-列が除去された後の表 1 のある行を見た時に対応するれる結果の数 (もしくは 4. 5 節で述べた |U | のサイズ) が多く

道路 ID を ISA[i] から復元するには，上で述べた配列 C を二なることによるものと考えられる．6. 2 節において，この点に分探索すればよい．もしくは [16] で提案されている簡潔ビット

ついて議論を行う．

ベクトルを用いてこの探索を実現することも考えられる．

6. 議

論

6. 4 索引の更新
提案手法は過去の履歴データに対する索引化を対象としてお本節では前節での数値実験などを踏まえ，索引サイズ，クエ

り，データの動的な更新はサポートしていない．一つの解決法

リ最適化，データ構造の最適化，索引の更新の 4 つの観点からとして索引をある時間幅ごとに逐次的に構築することが考えら

提案手法について議論をする．

れる．これによってすべてのデータを構築し直す必要がなくな
る．より動的なデータの取り扱いは今後の課題である．

6. 1 索引のサイズ
FM-index はメモリ上に構築されることを前提とした索引で7. お わ り にあるため，そのサイズはコンパクトであることが望ましい．今
回は圧縮手法を用いていないが，そのサイズは 33 MB であっ

本論文ではネットワーク上を移動する車両の軌跡に対する完た．従って数十ギガバイトのメモリを搭載した計算機を用いる

全経路クエリに対する効率的な応答を可能にする索引構造の提ことで今回のデータセットよりも数百倍大きなものに関しても案を行った．提案手法では，車両軌跡 (道路リンクの列) を文容易に扱うことができる．一般に，データ分布 (文字の出現分

字列とみなし，全文索引である FM-index と時刻の索引である

布) には図 4 に示すように偏りがあるため，索引の圧縮 [8], [12]（注 7）：また，ISA は一意であるので主キーとしても用いることができる．

B+ 木を逆接尾辞配列を用いて統合した．その結果，B+ 木の探索回数がクエリ経路長 |P | に依存しない，かつ厳密な結果を保証する手法であることを示された．また，実データを用いた実験において，提案手法が実際に既存手法よりも高速であることを示した．
提案手法はディスク上に格納する方法には強い制約を持たな
い．つまり基本的な B+ 木 による索引が利用可能であれば基本的にはどのようなデータベースシステム上にも逆接尾辞配列のフィールドを追加することで実装することができることも大きな利点の一つである．このことは提案手法の高い拡張性を意味しており，今後は車両走行の時空間パターンとそれ以外の車
載センサなどを合わせたデータマイニングへの応用などが期待
される．

文

献

[1] L. Bracciale, M. Bonola, P. Loreti, G. Bianchi, R. Amici,
and A. Rabuﬃ. CRAWDAD data set roma/taxi (v. 201407-17). Downloaded from http://crawdad.org/roma/taxi/,
July 2014.
[2] M. Burrows and D. J. Wheeler. A block-sorting losslessdata compression algorithm. In Technical Report 124. Digital Equipment Corporation, 1994.
[3] F. Claude and G. Navarro. Practical rank/select queries
over arbitrary sequences. In In Proc. 15th SPIRE, LNCS
5280, pages 176–187, 2008.
[4] P. Ferragina and G. Manzini. Opportunistic data structureswith applications. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS ’00,
pages 390–, 2000.
[5] E. Frentzos. Indexing objects moving on fixed networks.
Proc. of the 8th Intl. Symp. on Spatial and Temporal
Databases (SSTD), pages 289–305, 2003.
[6] R. Grossi, A. Gupta, and J. S. Vitter. High-order entropycompressed text indexes. In Proceedings of the Fourteenth
Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA ’03, pages 841–850, Philadelphia, PA, USA, 2003.
Society for Industrial and Applied Mathematics.
[7] C. Guo, J. Meguro, Y. Kojima, and T. Naito. Automaticlane-level map generation for advanced driver assistance systems using low-cost sensors. In Robotics and Automation(ICRA), 2014 IEEE International Conference on, pages
3975–3982, 2014.
[8] J. Kärkkäinen and S. J. Puglisi. Fixed block compression
boosting in fm-index. In Proceedings of String Processing and Information Retrieval (SPIRE ’11), pages 174–184,
2011.
[9] S. Koide, Y. Tadokoro, and T. Yoshimura. Snt-index:
Spatio-temporal index for vehicular trajectories on a road
network based on substring matching. In Proceedings of the
1st ACM SIGSPATIAL International Workshop on Smart
Cities and Urban Analytics, UrbanGIS’15, New York, NY,
USA, 2015. ACM.
[10] B. Krogh, N. Pelekis, Y. Theodoridis, and K. Torp. Pathbased queries on trajectory data. In Proceedings of the
22Nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL’14, pages 341–350, New York, NY, USA, 2014. ACM.
[11] M. Li, A. Ahmed, and A. J. Smola. Inferring movement
trajectories from gps snippets. In Proceedings of the Eighth
ACM International Conference on Web Search and Data
Mining, WSDM ’15, pages 325–334, New York, NY, USA,2015. ACM.

[12] V. Mäkinen and G. Navarro. Implicit compression boostingwith applications to self-indexing. In Proceedings of String
Processing and Information Retrieval (SPIRE ’07), pages
229–241, 2007.
[13] C. D. Manning and P. Raghavan. 情報検索の基礎. 共立出版,
2012.
[14] P. Newson and J. Krumm. Hidden markov map matching
through noise and sparseness. In Proceedings of the 17th
ACM SIGSPATIAL International Conference on Advancesin Geographic Information Systems, GIS ’09, pages 336–
343. ACM, 2009.
[15] G. Nong, S. Zhang, and W. H. Chan. Two eﬃcient algorithms for linear time suﬃx array construction. IEEE
Trans. Comput., (10):1471–1484, 2011.
[16] D. Okanohara and K. Sadakane.
Practical entropycompressed rank/select dictionary. In Proceedings of the
Meeting on Algorithm Engineering & Expermiments, pages
60–70, Philadelphia, PA, USA, 2007. Society for Industrial
and Applied Mathematics.
[17] M. R. Vieira, E. Frı́as-Martı́nez, P. Bakalov, V. Frı́asMartı́nez, and V. J. Tsotras. Querying spatio-temporal patterns in mobile phone-call databases. In Mobile Data Management (MDM), 2010 Eleventh International Conferenceon, pages 239–248, 2010.
[18] M. Yoshikawa and T. Amagasa. Xrel: A path-based approach to storage and retrieval of xml documents using relational databases. ACM Trans. Internet Technol., 1(1):110–
141, Aug. 2001.
[19] J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, andY. Huang. T-drive: Driving directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information
Systems, GIS ’10, pages 99–108, New York, NY, USA, 2010.
ACM.
[20] 岡野原大輔. 高速文字列解析の世界: データ圧縮・全文検索・テ
キストマイニング. 岩波書店, 2012.