DEIM Forum 2019 D7-4

道路ネットワークのスパース性に着目した車両軌跡の圧縮索引
小出 智士†

肖川††佳治††石川† 豊田中央研究所 〒 444–0416 愛知県長久手市横道 41–1†† 名古屋大学 情報科学研究科 〒 464–8603 愛知県名古屋市千種区不老町
E-mail: †koide@mosk.tytlabs.co.jp, ††chuanx@nagoya-u.jp, †††ishikawa@i.nagoya-u.ac.jp
あらまし

本研究では道路ネットワーク G 上を走行する軌跡データに対する圧縮索引を構築する．軌跡データを Gのエッジ集合 E をアルファベット集合とする文字列と考えることで圧縮文字列索引 (FM-index) の技術が適用可能であるが，E のサイズは一般に大きいため，従来の FM-index では効率が低下する．本研究では道路ネットワーク G がスパースであることに着目し，効率の低下を抑えるような圧縮法を提案する．提案手法では，理論的には検索速度がE のサイズに依存せず，G の最大流出次数のみに依存する．また，圧縮率についても実質的には E のサイズに依存しないことを実データを用いて示す．さらに提案手法が従来の圧縮 FM-index と比較して数倍から数十倍程度高速であり，圧縮率も高いことも実験的に示す．
キーワード 軌跡データ，データ圧縮，パタンマッチングA

1. は じ め にB

E

D

車両などから収集される移動軌跡データはデータ駆動型ナビ

C

ゲーションなどで重要な役割を果たす．大規模な軌跡データに対する検索技術はそれらのアプリケーションの基礎を成すものであり，これまでに我々はネットワーク上を移動する軌跡デーF

図 1 ネットワーク上の軌跡 (T1 = ABEF, T2 = ABC, T3 = BC および T4 = AD)

タに対する検索技術を開発してきた [8], [9]．これらの検索技術
では，軌跡を道路ネットワーク G = (V, E) のエッジ ID の列(すなわちエッジ集合 E 上の文字列) とみなし，それらを文字列索引である FM-index [3] に格納することで効率的な処理を実現していた．FM-index はコンパクトなインメモリ索引であり，オリジナルの文字列と同程度のメモリ使用量でデータの格納およびパタンマッチングを実現する．メモリに格納しきれないほどのデータを索引化するためには，圧縮 FM-index [10] を用いる，もしくはパーティショニング [9] を行うなどの工夫が必要である．
本研究では車両軌跡を文字列とみなした場合の FM-index の圧縮手法を提案する．前述したように車両軌跡はエッジ集合 E上の文字列 P ∈ E ∗ として表されるが，一般に E は数万から数百万要素からなる大きな集合である (E ∗ は E をアルファベットとする任意の長さの文字列の集合)．FM-index の最もシンプルな実装では一文字あたりのサイズがおよそ log2 |E| であることに着目したデータ構造を提案する．
なお，本稿は基本的に [7] の内容に準ずるものである．また，証明などに関しては [6] を参照いただきたい．

2. 準

備

本章では提案手法のベースとなる Burrows-Wheeler Trans-form (BWT) および FM-index について簡潔に述べる．なお，
本論文では複数の車両軌跡 Pi ∈ E ∗ (1 <=i<= N ) をその反転文
r
字列 Pir および区切り文字 $ を用いて T = P1r $P2r $ · · · $PN$#のように連結する (# は文字列の最後を表す特殊文字)．本稿では図 1 に示すようなネットワーク上の 4 つの車両軌跡(T1 , · · · T4 ) を連結した文字列を例として用いる．
T = FEBA
CB $ |{z}DA $#.
| {z } $ CBA| {z } $ |{z}
P1r

P2r

P3r

(1)

P4r

り，パタン Q ∈ E ∗ を検索するのに必要な時間は |Q| · log2 |E|であるため，巨大な E に対しては効率が下がるという問題点

したがって，T のアルファベット集合 Σ は E ∪ {$, #} とがある．これに対して，様々な改良手法が提案されており，こなる．慣例に従ってアルファベット集合のサイズを σ と書く．

れらを用いることでよりコンパクトな (かつ，場合によってはなお，#, $ の辞書順は E のどの文字よりも小さいものとする

高速な検索が可能な) 索引を作ることが可能である [1], [4], [10]．

(i.e., # < $ < ∀w ∈ E)．また配列は 0 からはじまる添字を持

これらの改良手法は任意の巨大アルファベット文字列に適用可

ち，配列 A の部分文字列を A[i, j) と書き，特に A の長さ n∗能である．一方，本研究では車両軌跡 P ∈ E が道路ネットを明記したい場合に A = A[0, n) と書く．

ワーク G 上に制約されていることに着目し，従来手法よりも以下では本論文の前提となる BWT, FM-index などの概念

高い圧縮率および高速なパタンマッチングが可能であることをの定義を簡潔に行う．詳細な定義については [7] や [13] などを示す．具体的には道路ネットワーク G がスパースグラフであ参照いただきたい．

2. 1 BWTAlgorithm 1: search(Q, Tbwt ): 長さ m のパターン Q に

長さ n の文字列 T に対する Burrows-Wheeler Transform

対応する接尾辞の範囲 [sp, ep) を求める (パタンマッチング)(BWT) は T の文字列を以下で述べるルールに従って並べ替えた文字列 Tbwt である．すなわち T の接尾辞配列 SA[0, n)を用いて (1) Tbwt [i] = T [SA[i] − 1] (SA[i] =| 0 の場合)，(2)Tbwt [i] = T [n − 1] (SA[i] = 0 の場合) と定義される．
式 (1) の文字列の BWT は以下のように計算される．

Tbwt = $AAABDBBCCE$$$F#.

(2)

1w ← Q[m − 1]

2sp ← C[w]; ep ← C[w + 1]

3for i = 2, · · · , m do

4w ← Q[m − i]5sp ← C[w] + rankw (Tbwt , sp)6

ep ← C[w] + rankw (Tbwt , ep)

7

return [sp, ep)

2. 2 FM-index
FM-index は以下の特徴をもつ文字列 T に対するインメモリ索引である: (1) オリジナルの T と同程度の (もしくはそれよりコンパクトな) 索引サイズであり，(2) 高速なパタンマッチングが可能．以下ではこれらについて述べる．

a ) 索引サイズ
FM-index は文字列 T の BWT Tbwt をウェーブレット木 [11]に格納したデータ構造である．したがって，索引サイズはウェーブレット木の実装に依存する．標準的な平衡ウェーブレット木を用いればそのサイズは n lg σ + o(n) ビットである．ハフマン
木型のウェーブレット木を用いた場合，文字列 T の経験エントロピー H0 (T ) を用いて nH0 (T ) + o(n) ビットとなる．さらにウェーブレット木の内部で用いる簡潔ビットベクトルとしてRRR と呼ばれる圧縮ビットベクトルを用いた場合，FM-indexは nHk (T ) + o(n) ビットで格納できる．ここで Hk (T ) は T のk 次経験エントロピー [13] である．これは implicit compression
boosting [10] として知られている．上述したエントロピー間には Hk (T ) <= H0 (T ) <= lg σ という関係がある．
b ) パタンマッチング
次に FM-index を用いたパタンマッチングについて述べる．
ここでパタンマッチングとは与えられたクエリ文字列 Q に対して，Q を接頭辞として持つような T の接尾辞集合を求めることである．そのような接尾辞集合は辞書順で連続した範囲[sp, ep) に出現する (0 <= sp <= ep < n)．この [sp, ep) を求めることをここではパタンマッチングと呼ぶ （注 1）．
アルゴリズム 1 にパタンマッチングのアルゴリズムを示す．
ここで C[w] は w ∈ Σ よりも辞書順の小さな文字が T 中に出現した回数であり，前処理で計算しておく (配列 C の長さ

3. 提 案 手 法
3. 1 概要

提案手法は「車両軌跡がスパースグラフである道路ネットワーク上に沿って移動する文字列とみなすことができる」という性質を用いてその FM-index の圧縮率，検索速度を大幅に改善するものである．まず，スパースグラフの性質を捉えるために文字列 T の 経験遷移グラフ を導入し，それに基づいて Tbwtをより小さな経験エントロピーをもつ文字列 ϕ(Tbwt ) に変換する (相対移動ラベリング)．次に文字列 ϕ(Tbwt ) をハフマン木型のウェーブレット木に格納する．このようにして得られたデータ構造ではパタンマッチングのアルゴリズムをそのままで用いることができないため，我々は ϕ(Tbwt ) 上の検索アルゴリズムを提案する．ハフマン木型のウェーブレット木は格納する文字
列 T のエントロピーが小さいほどサイズがコンパクトになり，また rank 計算が高速になる．提案手法は Tbwt を小さなエントロピーの文字列 ϕ(Tbwt ) に変換するため高い圧縮率および高速なパタンマッチングを両立することができる．

3. 2 経験遷移グラフ
文字列 T において隣り合う 2 つの文字の遷移関係を表現す
る経験遷移グラフ GT を以下のように定義する．
定義 (経験遷移グラフ) 文字列 T の経験遷移グラフ GT =(VT , ET ) はアルファベット集合 Σ をノード集合とするような有向グラフである．辺集合 ET は以下のように定義される:

T [i]T [i + 1] = ww′ となる i が存在する場合，(w′ , w) ∈ ET であり，そうでない場合は (w′ , w) ∈/ ET ．

は高々 σ)．また rankw (Tbwt , sp) は接頭辞 Tbwt [0, sp) の w の車両軌跡の経験遷移グラフを考えると，道路ネットワーク上の出現回数であり，これは Tbwt をウェーブレット木に格納して隣接したエッジ間を移動するため，経験遷移グラフはスパースおくことで効率的に計算可能である．具体的な rank の計算複になる．平均的には各ノードは 3 から 4 の道路リンクに接続し雑性 T C は (1) ウェーブレット木として平衡型を用いた場合:ているので，グラフの平均次数も極めて小さな値になる．

O(log σ) (2) ハフマン木型を用いた場合 O(H0 (T )) である．したがってアルゴリズム 1 では rank 計算を m = |Q| 回呼び出すため，その計算量は O(m · T C) となる．

3. 3 相対移動ラベリング
相対移動ラベリングのアイデアは文字列 T の各文字を小さなアルファベットに変換することでエントロピーを小さくする，というものである．そのために経験遷移グラフ GT を用いる．ノード w′ の流出ノード集合を N (w′ ) と書くと，定義より

T [i + 1] = w′ のとき，T [i] の取り得る値は w ∈ N (w′ ) に限定（注 1）：この範囲を用いることで様々な応用的な問い合わせが可能になる．例えされる．ここで各 w ∈ N (w) に整数 {1, 2, · · · , |N (w′ )|} を割当

ば車両軌跡データへの応用としては [9] がある．なお，Q が T に出現しない場て，この整数を ϕ(w|w′ ) と書く．そして T [i] を ϕ(T [i] | T [i+1])

合は sp = ep とする．に書き換える．この書き換えをすべての 0 <= i < |T | について

$
1121BC#1Context(k=1)$ AAAB DBB CCE $$ $ F ## $$$$ AAA BBB CC D E F

21A

11D2F

1

One to one correspondencein(shaded area)$ AAAB DBB CCE $$ $ F #1 1112 211 112 11 1 1 11 1112 211 112 11 1 1 1E(a) 相対移動ラベリング(b) Tbwt のラベル付け

図 3 Rank 計算のエミュレーション (補題 1) の原理

図 2 (a) 式 (1) の文字列に対応する経験遷移グラフ: それぞれのノードは道路リンクに対応しており，エッジは 2 つの道路リンク感の遷移が T 中に出現する場合にのみ存在する．(b) 相対移動ラrankw (Tbwt , j) = rankη (ϕ(Tbwt ), j) − Zw′ w ,(3)

η := ϕ(w|w′ ) andベリング: ϕ(Tbwt ) のエントロピーは Tbwt のエントロピーよりwhereも小さくなる.

Zw′ w := rankη (ϕ(Tbwt ), C[w′ ]) − rankw (Tbwt , C[w′ ]). (4)行う (これは i = |T | − 1 から始めて後ろ向きに実行すれば可この式が成立する理由を示す前に，この式が導く帰結に能である)．GT がスパースであれば一般に |N (w′ )| は小さい

ついて述べる．この補題はパタンマッチングで必要となる

ので，変換された文字列は小さなアルファベット集合上の文字

rankw (Tbwt , j) がラベル化 BWT ϕ(T ) 上の rank 計算および列となり，したがって経験エントロピーは小さくなることが期

j に依存しない定数 Zw′ w を用いて計算できることを主張して待される．なお，上述の整数の割当は一意的ではない．この割いる．Zw′ w は事前計算しておくことができる．また rank 計算

当をエントロピーの意味で最適化する方法については 4. 章では w に対してではなくその相対移動ラベル η = ϕ(w|w′ ) に対述べる．

して行う（注 3）．この補題は任意の (w′ , w) ∈ Σ × Σ ペアに対し以下では相対移動ラベリングのアイデアを FM-index に組み込むための方法を述べる．通常の FM-index は T の BWT Tbwt
を用いる．T を相対移動ラベリングした文字列 T ′ の BWT を用いた場合，接尾辞の順序が破壊されてしまうため，パタンマッチては成立せず，(w′ , w) ∈ ET に対してのみ成立するが，これはパタンマッチングにおいては問題とならない．これは以下の理由による: (w′ , w) ∈/ ET であるならば経験遷移グラフの定義より ww′ という文字列は T に含まれないという事実より，ww′ングができない．そこで提案手法では，まず T の BWT Tbwt

が問い合わせ文字列 Q に含まれる場合は明らかにパタンマッを計算し，そのあとに相対移動ラベリングを適用する．これにチングの結果は null であることがわかるためである (具体的なよって接尾辞の順序が保たれるため，次節で述べるパタンマッ

処理としては rank をエミュレートする直前に (w′ , w) ∈ E をチアルゴリズムが可能になる．

BWT Tbwt に相対移動ラベリングを適用する際には各文字 Tbwt [j] に対して T の対応する位置 i の一文字あとの文字T [i + 1] を知っている必要がある．これは BWT の性質より容易に計算可能である．すなわち C[w] <= j < C[w + 1] となるような w である（注 2）．このように相対移動ラベリングによって変換された Tbwt を ϕ(Tbwt ) と書いて ラベル化 BWT と呼ぶことにする．

チェックしてそうでなければ null を返すようにすればよい)．
最後に上記の補題が成立する理由について述べる．Tbwt の′C[w′ ] <= j < C[w + 1] に位置する文字 w := Tbwt [j] のオリ

ジナルの文字列 T における位置 i を考える．BWT の定義より T [i + 1] = w′ が成立する (図 2b の “Context” 文字列に対′応)．したがって C[w′ ] <= j < C[w + 1] の範囲では変換された文字列 ϕ(Tbwt ) と BWT Tbwt の各文字は 一対一対応 することがわかる．これによって図 3 に示すように，(a) Tbwt におけ

最終的なデータ構造は経験遷移グラフ GT およびラベル化

る C[w′ ] から j までの文字 w の出現回数と (b) ϕ(Tbwt ) にお

BWT ϕ(Tbwt ) をウェーブレット木に格納したものの 2 つであける C[w′ ] から j までの文字 η = ϕ(w|w′ ) の出現回数が等しる． すなわち Tbwt を保持する必要はない．ウェーブレット木

いことが分かる．上記の (a) はとしては何を用いてもよいが，本研究では圧縮率を重視し，内rankw (Tbwt , j) − rankw (Tbwt , C[w′ ])部ビットベクトルとして RRR を用いたハフマン木型のウェーブレット木を採用する．

3. 4 Rank 計算のエミュレーション
パタンマッチングのためには Tbwt 上で rank 計算ができれば(5)として計算できる．同様に (b) はrankη (ϕ(Tbwt ), j) − rankη (ϕ(Tbwt ), C[w′ ]).

(6)

十分である (アルゴリズム 1)．そこで本節ではラベル化 BWTϕ(Tbwt ) を用いて rankw (Tbwt , j) をエミュレートするための手となる．最後に (a) と (b) を等号で結んで式変形すれば補題が法について述べる．以下の補題は Tbwt 上の rank と ϕ(Tbwt )得られる．

上の rank を関連付ける．
補題 1 任意の w ∈ Σ およびその流出先ノード w ∈ N (w′ )，′さらに C[w′ ] <= C[w + 1] に対して以下が成立する:= ∀j <（注 2）：C[w] は単調増加な配列であるので w は一意に決まる．

4. ラベル付けの最適化
前章で定義された相対移動ラベリングは各流出ノード（注 3）：w′ は w の「移動元」である，と考えると理解しやすい．

ICB-Huﬀ
b=63
b=31

b=6364b=31b=15FM-AP-HYB
b=63b=31b=15b=15b=1564

b=151248163264

Space (bits/symbol)

124816326416(c) Roma
0.5Space (bits/symbol)

12481632(d) MO-gen
1Space (bits/symbol)

2481632(e) Chess

14(b) Singapore-2

4(a) Singapore

41616166464

FM-GMR
b=63
b=3116256

256

b=314

Search time ( µs)b=63

ICB-WM

64

UFMI

256

CiNCT (w/o ET-graph)

256

CiNCT64

1Space (bits/symbol)

248163264

Space (bits/symbol)

図 4 実験結果．横軸は一文字あたりに要するビット数，縦軸はランダムサンプリングされたク
エリ文字列に対するパタンマッチングの処理時間．CiNCT は提案手法においてウェーブレット木と経験遷移グラフのサイズの合計を意味し，CiNCT (w/o ET-graph) は提案手法のウェーブレット木のみのサイズを意味している．

w ∈ N (w′ ) に {1, · · · , |N (w′ )|} の整数を割当てるが，どの$ および # による)．これによって，任意の問い合わせ文字列

w にどの整数を割り当てるのか，については定義されなかっQ ∈ E ∗ に対して提案手法ではパタンパッチングを O(|Q| · δ)た (この割当には |N (w′ )| の階乗の自由度がある)．本稿で時間で実行可能であることが分かる．これは GT がスパースではこの割当を変換された文字列 ϕ(Tbwt ) の経験エントロピーある場合，典型的な O(|Q| lg σ) よりも小さくなる．たとえば

H0 (ϕ(Tbwt )) が最小になるように決定する方法を議論する．経σ = 216 および δ = 4 の場合，提案手法は 4 倍高速になると期験エントロピーを基準にする理由は ϕ(Tbwt ) を格納するウェー待される．一般には，提案手法は問い合わせ文字列 Q を GT

ブレット木のサイズは H0 (ϕ(Tbwt )) に比例する項をもち（注 4），を用いてラベル化するというオーバーヘッドがあるが，これもさらに rank 計算の時間複雑性は O(H0 (ϕ(Tbwt ))) であるため高々 O(δ) であり，スパースな GT の場合は問題にならない．

である．
最適なラベル付けを与えるために，文字列 T における長さ

6. 実

験

2 の部分文字列 ww′ の頻度 nww′ を考える (bigram 頻度)．そ6. 1 実 験 条 件

して w ∈ N (w′ ) に {1, · · · , |N (w′ )|} の整数を割当てる際にはa) 比 較 手 法

この頻度が大きいほど小さい整数を割当てるようにする．この以 下 の 5 タ イ プ の FM-index と 提 案 手 法 (CiNCT:∗

割当に基づくラベル付け ϕ に関して以下の定理が成立する．

Compressed-index for Network-Constrained Trajectories) を比較する．

定理 (Bigram に基づくラベル付けの最適性) 相対移動ラベ

UFMI: ウェーブレット行列 [2] + 無圧縮簡潔ビットベク

トル [5]

リングの要件を満たす任意のラベル付け ϕ に対して

H0 (ϕ∗ (Tbwt )) <= H0 (ϕ(Tbwt )).

•(7)

5. Rank 計算のアルファベットサイズ非依存性
上述の ϕ(Tbwt ) を用いた rank 計算のエミュレーションの時•FM-GMR [4]: Rank 計算が O(log log σ) で可能 (無圧縮)•ICB-WM: ウェーブレット行列 + RRR ビットベクトル•ICB-Huﬀ: ハフマン木型ウェーブレット木 + RRR ビットベクトル•FM-AP-HYB: アルファベットパーティショニングに基づ

間複雑性 T C はアルファベットサイズ σ に依存せず，経験遷

く圧縮 FM-index (Rank 計算は O(log log σ) 時間) [1].

移グラフ GT の最大流出次数 (ここでは δ と書く) にのみ依存

なお，RRR ビットベクトルのブロックサイズパラメータはする，という性質が導かれる．
定理 (アルファベット非依存性) 式 (3) は O(δ) 時間で計算できる．
これは ϕ(Tbwt ) のアルファベットサイズが δ + 2 となるため，それを格納するウェーブレット木の高さ (本稿ではハフマン木)が最悪でも δ + 1 であることから導かれる (“+2” は特殊文字（注 4）：詳細な解析を行うと，RRR とハフマン木型ウェーブレット木を組み合わせた場合，ϕ(Tbwt ) のサイズの理論値の主要項は ∀k < logσ n に対してn · Hk (Tbwt ) ビットでありラベル付け ϕ に依存しないが，第二項はラベル付けに依存して 0.095n · H0 (ϕ(Tbwt )) ビットであることがわかる [7]．一方，ラベル付けしない Tbwt の場合，この第二項は 0.095n · H0 (Tbwt ) となる．巨大b = {15, 31, 63} を考える (デフォルトは 63).
b ) データセット
以下のデータセットを用いて実験を行った．

•Singapore [12]: シンガポールのタクシーデータセット(マップマッチング済み)．
•

Singapore-2: Singapore データセットは物理的に接続していない道路リンクが bigram を形成していることが頻繁に発生しているため，それらのギャップを最短経路で補間することで経験遷移グラフをスパースにしたもの．

•Roma: ローマのタクシーデータセット（注 5）．隠れマルコフモデルによるマップマッチングを行った．

アルファベットの文字列ではこの改善は無視できないサイズであり，実際に実験でも圧縮率で大きな改善が見られた．

（注 5）：http://crawdad.org/roma/taxi/

12M

15.5

13.0

0.9

2.4

MO-Gen

193M

17.4

13.0

2.8

8.8

Chess

20M

18.8

10.3

2.0

1.6

‡

d¯ は経験遷移グラフ GT の平均次数.

•

MO-gen: 車両軌跡のジェネレータによる人工データ（注 6）.

•Chess: チェス棋譜データの各局面をハッシュ化して文字

CiNCTFM−AP−HYBCiNCT (w/o ET-graph)

28

Roma

FM−GMRICB−Huﬀ
ICB−WM

27

4.0

ICB−Huﬀ

26

1.3

UFMI

25

14.0

2

15.5

ICB−WM

FM−GMRCiNCTFM−AP−HYB

275M

Search time ( µs)

Singapore-2UFMI4

26.83d¯ ‡1.822H0 (ϕ(Tbwt ))13.8

21H0 (T )15.520lg σ

53M

2 −1|T |SingaporeIndex size (bits / symbol)

実験に用いたデータセットの統計量

2 −2

表1Dataset

22 23 24 25 26
Avg out−degree d

22 23 24 25 26
Avg out−degree d

図 5 平均流出次数 dˆ の影響

ラフの平均次数はそれと比較してかなり小さくなっているようなデータセットである．

c) 実

装

実装は g++ (ver. 4.8.4; -O3 オプション) および，簡潔デー
タ構造のライブラリ sdsl-lite を用いた．

6. 2 結果

ICB−WMCiNCT28
ICB−Huﬀ

FM−AP−HYB

27

FM−AP−HYBUFMICiNCTFM−GMRCiNCT (w/o)

2 14 2 15 2 16 2 17 2 18
Alphabet size: σ

図6ICB−WM

26

FM−GMRICB−Huﬀ

25

表 1 にこれらのデータセットの統計量を示す．いずれのデー
タセットもアルファベット数は σ > 215 であるが，経験遷移グ

UFMI24使用した．

Search time ( µs)

http://www.ficsgames.org)．初期局面から 10 ムーブのみをIndex size (bits / symbol)
2 −22 −120
21
22

列とみなしたデータセット (Blitz, 2006–2015, 1.87M games,

2 14 2 15 2 16 2 17 2 18
Alphabet size: σ

アルファベットサイズ σ の影響

図 4 に索引サイズおよびパタンマッチングの処理時間に関する評価結果を示す．パタンマッチングの処理時間の評価は以下

文字列索引を提案した．提案手法ではネットワークのスパーのように行った．データセットから長さ 20 の文字列 Q を 1000

ス性を利用した相対移動ラベリングを用いることで，既存の回ランダムサンプリングし，これを問い合わせ文字列とした．

FM-index と比較して圧縮率，パタンマッチングの処理時間をこれらの Q に対する接尾辞の範囲 [sp, ep) を求めるために要ともに大きく改善できることを示した．

した処理時間の平均値を評価結果とした (ただし Chess データセットのみ各軌跡の長さが 10 であるため，問い合わせ文字列の長さも 10 としている)．
提案手法は比較手法と比較して小さな索引サイズと高速なパタンマッチングを両立していることが分かる．特に Singapore-2や Roma などの経験遷移グラフの平均次数 d¯ が小さなデータセットでは大きな改善が見られる．
次数 d¯ の影響を詳しく調べるために，ランダムグラフ上のランダムウォークデータセットを用いた実験結果を図 5 に示した．この実験では σ = 216 とし，|T | = 100M とした．この実験結果は小さな d¯ では提案手法が既存手法と比較して大幅に有利である一方，d¯ が大きな領域ではその優位性が失われるということを示している (これは提案手法は GT のスパース性を前提にしているので当然の結果である)．
最後にアルファベットサイズの影響をランダムウォークデー
タセットを用いて調べる．ここでは平均次数を d¯ = 4 と固定し，|T | = 800|σ| とした．図 6 に示すとおり，提案手法は σ に対して他の手法よりもよいスケーラビリティを示しており，巨大なアルファベットのケースで優位性が大きいことを示唆している．

7. ま と め
本稿では道路ネットワーク上を移動する車両軌跡に対する（注 6）：http://iapg.jade-hs.de/personen/brinkhoff/generator/

文

献[1] Jérémy Barbay, Travis Gagie, Gonzalo Navarro, and YakovNekrich. Alphabet partitioning for compressed rank/selectand applications. In Proc. ISAAC’10, pp. 315–326, 2010.
[2] Francisco Claude and Gonzalo Navarro. The wavelet matrix. In Proc. SPIRE’12, pp. 167–179, 2012.
[3] P. Ferragina and G. Manzini. Opportunistic data structureswith applications. In Proc. FOCS’00, 2000.
[4] Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao.
Rank/select operations on large alphabets: a tool for text
indexing. In Proc. SODA’06, pp. 368–373, 2006.
[5] G. Jacobson. Space eﬃcient static trees and graphs. InProc. FOCS’89, pp. 549–554, 1989.
[6] Satoshi Koide, Yukihiro Tadokoro, Chuan Xiao, and Yoshiharu Ishikawa. CiNCT: Compression and retrieval for massive vehicular trajectories via relative movement labeling.
arXiv preprint, 2017.
[7] Satoshi Koide, Yukihiro Tadokoro, Chuan Xiao, and Yoshiharu Ishikawa. CiNCT: Compression and retrieval for massive vehicular trajectories via relative movement labeling.
In ICDE, pp. 1097–1108, 2018.
[8] Satoshi Koide, Yukihiro Tadokoro, and Takayoshi Yoshimura.
SNT-index: Spatio-temporal index for vehicular trajectories on a road network based on substring matching. In
UrbanGIS, 2015.
[9] Satoshi Koide, Yukihiro Tadokoro, Takayoshi Yoshimura,
Chuan Xiao, and Yoshiharu Ishikawa. Enhanced indexing
and querying of trajectories in road networks via string algorithms. ACM Trans. Spatial Algorithms Syst., Vol. 4,
No. 1, pp. 3:1–3:41, June 2018.
[10] Veli Mäkinen and Gonzalo Navarro. Implicit compression boosting with applications to self-indexing. In Proc.
SPIRE’07, pp. 229–241, 2007.

[11] Gonzalo Navarro. Wavelet trees for all. In Proc. CPM’12,pp. 2–26, 2012.
[12] R. Song, W. Sun, B. Zheng, and Y. Zheng. PRESS: A
novel framework of trajectory compression in road networks.
PVLDB, Vol. 7, No. 9, pp. 661–672, 2014.
[13] 岡野原大輔. 高速文字列解析の世界: データ圧縮・全文検索・テキストマイニング.