DEIM Forum 2014 E4-6

パーティクル表現を用いた曖昧位置情報に対する空間問合せ処理
早矢仕 新†

杉浦 健人†

董ていてい†

石川 佳治†,††† 名古屋大学大学院情報科学研究科†† 国立情報学研究所
E-mail: {hayashi,sugiura,dongtt}@db.ss.is.nagoya-u.ac.jp, ishikawa@is.nagoya-u.ac.jp
あらまし

ロボット分野では自律移動ロボットに関する研究が進み，近年ではオブジェクトの自己位置推定手法に確率的な手法が用いられている．特にモンテカルロ位置推定と呼ばれる，パーティクルフィルタをベースにしたアルゴ
リズムが一般的となっている．モンテカルロ位置推定では，位置情報の推定にモンテカルロ法を用いるため，推定した位置情報がパーティクル集合で表現された確率分布となる．本研究では，このようなパーティクル集合で表現された確率分布の時系列データを対象とした時空間問合せ手法について述べる．また，効率的な問合せ処理のためのデー
タ構造と，データ構造を利用した問合せ処理について述べる．
キーワード

曖昧な位置情報, 空間問合せ, 索引構造
本研究では，図 2 で示したような，パーティクル集合で表現

1. は じ め にされた曖昧な位置情報の時系列データに対して，時刻，領域，

近年，ロボット分野では，自律的な移動ロボットの屋内外の確率の閾値を条件とした時空間問合せを扱う．

安全な移動を実現するために，自己位置推定に関する研究が進

時空間問合せの索引に関する研究として，[4] [5] [6] が挙げらめられている．この自己位置推定では，ロボットがある空間にれる．[4] では，2 次元座標軸と時間軸の 3 次元について R-木 [7]おいて，自身がどこに位置するのかをセンサデータを元に推を構築する手法を提案している．[5] や [6] では，タイムスタン

定する．近年では，センサデータの誤差を考慮した確率的な手

プ毎に R-木を構築するアプローチを用いている．これらは空法が用いられるようになり，中でもモンテカルロ位置推定と呼間索引に R-木を用いているため，パーティクル集合に対して，ばれる手法が用いられてきている [1] [2]．このモンテカルロ位

最小包囲矩形（MBR）を構築することで，本研究に適用する置推定では，ロボットの位置情報の推定にパーティクルフィルことは可能である．

タ [3] が用いられる．パーティクルフィルタはパーティクル集

しかし，範囲問合せについて，確率分布を包含する MBR を合で表現された確率分布を対象に，尤度の高いパーティクル付

索引として用いる場合，フィルタリングの効果が薄いという問近にリサンプリングすることで，より適切な確率分布を計算す

題がある．これは MBR 内の分布の密度情報が無いために，図る手法である．そのため，ロボットの位置情報は図 1 のように，3 で示したようなパーティクルの密度に偏りがある場合，パーパーティクル集合として表現されるという特徴がある．

ティクルの密な部分が問合せ領域に含まれていない場合でも，候補として含めてしまうためである．

q
図 1 位置情報のパーティクル表現

従って，ロボットの移動軌跡はパーティクル集合の時系列デー
タで表すことができる．その例として，テーブル形式で表したのが図 2 である．オブジェクト ID，時刻，パーティクル集合が組として結び付けられている．
オブジェクトID

図 3 パーティクルの密度の偏り

この問題に対する索引の研究として [8] [9] [10] が挙げられる．

時刻

パーティクル集合k= { 10,20 , … , 8,18 }

これらの研究では，MBR 内部の分布情報を索引に持たせることで，フィルタリングの効果を向上させている．[8] では，PCR

k+1= { 12,24 , … , 11,22 }（probabilistically constrained region）と呼ばれる，確率の値

k+2= { 14,27 , … , 14,25 }に応じた境界を持つ矩形領域を用いている．そして，PCR を

k+3= { 17,25 , … , 18,27 }キーとする R-木ベースの索引構造 U-木を提案している．[9] で

図 2 パーティクル集合の時系列データの例

は曖昧な領域の MBR を kd-木 [11] を用いて分割することで，MBR 内の分布情報を持たせるアプローチをとっている．分割

された MBR をキーとした R-木ベースの索引 UI-木を提案している．[10] では，U-Quadtree と呼ばれる，空間全体を四分

2

1

木 [12] で分割し，各セルにパーティクルの分布情報を持たせた

21

20
19

3

索引を提案している．
4

しかし，これらの索引は空間データに対する範囲問合せを対5象としているため，時間軸を考慮した構造にはなっていない．

17

18

16

15

11

そこで，本研究では U-Quadtree をベースに拡張を行い，時空7間問合せに対応するための索引を提案する．

6¥
8

2. 曖昧な位置情報

14

9

10

12

オブジェクトA

13

オブジェクトB

本稿で説明に用いる記号を表 1 に示す．
= { 6, , 0.6 , 10, , 0.2 16, , 0.2 }= { 17, , 0.2 , 18, , 0.2 , 21, , 0.6 }表 1 本稿で用いる記号
記号

意味

O

オブジェクト集合

図 4 セルとオブジェクトのサマリo[t]時刻 t のオブジェクト o の状態

o.ur

オブジェクト o が存在しうる範囲

o.pdf

オブジェクト o が存在する確率を表す確率密度関数

Xo

オブジェクト o を表すパーティクル集合となる．従って，各セルと含まれるパーティクルの数から各みが等しいと仮定する．オブジェクト A も B もパーティク
ル数は 5 であるため，1 つのパーティクルが表す確率は 0.2

xio

パーティクル集合 Xo の i 番目のパーティクル

オブジェクトについて計算するとオブジェクト A のサマリは

wxi

パーティクル xio の重み

SA = {(6, A, 0.6), (10, A, 0.2), (16, A, 0.2)}，オブジェクト B のr < r′

領域 r ′ は領域 r を包含する

サマリは SB = {(17, B, 0.2), (18, B, 0.2), (21, B, 0.6)} となる．

o

各エントリは子ノードの確率を足しあわせて，親ノードのセル[8] [9] [10] では，オブジェクト o の曖昧な位置情報を，オブ

番号をキーとするエントリを作ることができる．そのため，１つジェクトが存在しうる範囲 o.ur と存在位置に関する確率密度関のオブジェクトについて，構築可能なサマリは複数考えられる．

数 o.pdf を用いて表している．オブジェクト o が位置 x に存在

この例の場合，オブジェクト A のサマリについて，セル番号 6,

する確率を o.pdf (x) とすると

o.pdf (x)dx = 1 となる．

10 について親ノードにあたるセル 8 に集約できる．従って，オ

本研究が対象となる，パーティクル集合による表現は，確率ブジェクト A のサマリとして SA = {(8, A, 0.8), (16, A, 0.2)}密度関数をモンテカルロ法で離散化したケースにあたり，各というサマリを考えることもできる．[10] では，どのエントリ

パーティクルがオブジェクトの存在しうる位置を示している．

を集約し，サマリを構築するかコストモデルによって判断する

パーティクルは重みを持ち，重みがパーティクルの尤度，つま手法を提案している．

∫

x∈o.urりオブジェクトがいる確率の高さを示している．重みが正規化∑されている場合，

11

wxio = 1 となる．
xi ∈Xoo

3. 関 連 研 究
3

8

14

19

3. 1 U-Quadtree
本研究で扱う確率分布は，離散的にサンプリングされた任意

1

2

4

5

6

7

9

10

12 13 15 1617

18 20 21の確率分布である．このような確率分布に対する範囲問合せを対象にした索引手法として Ying らが U-Quadtree [10] を提6, , 0.6 10, , 0.2

16, , 0.2 17, , 0.2

18, , 0.2 , (21, , 0.6)

案している．U-Quadtree は四分木によってセルで分割された
図 5 U-Quadtree空間に対し，サマリと呼ばれるオブジェクトの位置情報の近似
データを構築する．このサマリはセル番号，オブジェクト ID，
オブジェクトがセルに存在する確率の三組のタプル（エントリと呼ぶ）の集合として表される．オブジェクト o がセル c に存在する確率は，セル c の領域を rc としたとき，式（1）より計算できる．つまり，セルに含まれるパーティクルの重みの総和
より計算できる．

P r(c, o) =∑問合せ処理では，問合せ領域に包含されるセルと問合せ領域にオーバラップするセルに対応するエントリの確率から以下の2 つの条件判定を行う．
（ 1 ） 問合せ領域に包含されるセルのエントリの確率の総和が閾値以上かどうか（ 2 ） 問合せ領域にオーバラップするセルのエントリの確率

wxio

(1)

xio ∈Xo ∧xio <rcの総和が閾値以上かどうか
上記の条件１を満たす場合，そのオブジェクトを問合せ結果に加える．上記の条件２を満たす場合，パーティクルを用いた確サマリ作成の例を図 4 に示す．例では各パーティクルの重率の計算が必要となる．それ以外のオブジェクトは枝刈りされるため，パーティクルを用いた確率計算のコストが削減される．

t=1

t=2

t=3

root

MVR-tree

2

1

21
19

3

4

20

5

17

18

3D R-tree

11

7

6

root

16

8
9

15

図 7 MV3R-木

14時区間問合せを得意とする．各時刻に R-木を構築した場合に
10
問合せ範囲

12

13

オブジェクトA比べ，たどるノード数が少なくなるため，ディスクアクセス回

オブジェクトB

数が少なくなる．そのため，時区間問合せでは，MVR-木より= { 6, , 0.6 , 10, , 0.2 16, , 0.2 }= { 17, , 0.2 , 18, , 0.2 , 21, , 0.6 }効率が良くなる．MV3R-木は，問合せ条件の時区間の長さに

図 6 問合せ範囲とセルや時区間が短い時に使い，3D R-木を長い時区間の問合せに用応じて探索する木を選び，処理を行う．MVR-木を時点問合せいることで，２つを補完している．

例を図 6 を用いて説明する．問合せ範囲は図の q を中心とする円とし，確率の閾値を 0.5 とする．問合せ処理はまず，四分木を探索して，問合せ範囲にオーバラップするセルを見つける．
エントリが含まれていないセルは無視する．図 6 の場合では，この条件で探索すると，問合せ範囲にオーバラップするセル番
号は 6, 10, 16, 17 となる．次に，各オブジェクトについて，包含されるセルの確率の総和をエントリから計算する．包含されるセル番号は 6 のみなので，対応するエントリ (6, A, 0.6) が得られる．オブジェクト A が領域内に存在する確率が閾値 0.5 を超える，つまり条件 1 を満たすため，この時点でオブジェクト

4. 確率的時空間問合せ
本研究では時空間問合せの中でも基本的な問合せである，時
点問合せと時区間問合せ扱う．ここで想定している問合せは，「時区間 [ts , te ] の間に一度以上，指定した領域 r に存在した確率が θ 以上になったオブジェクトの ID を返す」という問合せである．
時刻 t のとき，問合せ領域にオブジェクト o が存在する確率を P r(r, t, o) とすると時区間問合せは以下のように定義する．
［定義 1］（時区間問合せ）

A は問合せ結果に含まれる．次に，オーバラップするセルの番
r u .or号に対応する各エントリについて，オブジェクトをキーとして確率を足し合わせると，A = 1.0, B = 0.2 となる．B は閾値

RQ(r, θ, [ts , te ]) = {oi |oi ∈ O, ts <=t<= te , P r(r, t, oi ) > θ}2

0.5 以下なので，条件 2 を満たさない．従ってこの時点で，問合せ条件を満たさないとわかるので確率計算を省略することができる．以上から，オブジェクト A が問合せの結果として返される．

3. 2 MV3R-木
２次元座標の時系列データを対象とした，時空間問合せとしrて時点問合せと時区間問合せがある．時点問合せは条件に時刻

r

o.ur

を指定し，時区間問合せは時区間を条件に指定する．MV3R-

図 8 積分される領域

図 9 計算されるパーティクル

木 [6] はこの２つの問合せに対応した索引構造である．MV3R木は MVR-木のリーフノードに対して，3D R-木 [4] を構築しこの P r(r, t, o) は問合せ領域 r とオブジェクト o.ur が重なた複合的なデータ構造をしている．そのデータ構造を図 7 にる範囲について確率密度関数を積分することで計算できる．積示す．

分範囲は図 8 の斜線部にあたる．連続的な確率密度関数の場合，MVR-木は MVB-木 [13] を拡張した手法で，各タイムスタン

式 (2) で表される．

∫

プに R-木を構築し，重複するノードを集約した構造である．そのため，時点問合せを得意とするが，時区間問合せは，時区間

P r(r, t, o) =中の各時刻について R-木を探索することになるため効率が悪い．特に，R-木はノードをたどるとき，ディスクへノード情報
を読みに行くため，ノードを探索する回数が増えるほど，処理時間がかかってしまう．一方で，3D R-木は２次元空間に時間(2)

本研究では確率分布をモンテカルロ近似した位置情報を考えるため，式 (2) の右辺を式 (3) によって近似できる．

∫∑

o[t].pdf (x)dx ≈軸を加えた３次元空間を対象に R-木を構築したデータ構造であx<r∧x<o[t].ur

る．こちらは MVR-木とは対照的に，時点問合せを苦手とし，

o[t].pdf (x)dxx<r∧x<o[t].ur

wxi

o[t]

xi

o[t]

∈Xo[t] ∧xi

o[t]

<r

(3)

つまり，確率は問合せ領域に含まれるパーティクルの重みの総和によって計算できる．図 9 の場合では，全てのパーティク

る．そこで，時間的・空間的に近い集約情報をまとめた索引を構築する．

ルの重みを 0.1 とすると問合せ領域に含まれるパーティクルが

セル番号はヒルベルト曲線に従って付けられているため，番号２つなので，オブジェクト o が含まれる確率は 0.2 となる．

が近いセルは空間上においても近くなる性質がある．そこで，本時区間問合せでは，各時刻の各パーティクル集合に対して，研究ではセル番号と時間を軸にした 2 次元空間に対して，R-木で式 (3) を用いて確率計算を行うことで，確率の閾値の条件を満索引付けを行う．前節で述べた集約情報は，オブジェクト ID がたすオブジェクトが求まる．時点問合せは時区間問合せの時刻キーとなっていた．そこで，セル番号と時刻をキーとなるようにの条件が一時刻のみの場合にあたるため，時区間問合せと同様組み替える．例として，(A, [(1, 0.7, 0.5), (3, 0.5, 0.3)], [k, k +1])の処理でオブジェクトを見つけることができる．

を 用 い る ．こ の 場 合 ，セ ル 番 号 と 時 刻 が キ ー と な る の で ，5. 問合せ処理の効率化(1, [k, k + 1]) というキーに対し，(A, 0.7, 0.5) をレコードに格納する．同様に (3, [k, k + 1]) というキーに対し，(A, 0.5, 0.3) をレ

シンプルな考え方として，各時刻に対して U-Quadtree をコードに格納する．この例をプロットしたのが図 10 の太線であ構築する方法がある．ただし，時点問合せでは該当時刻の U-る．そして，この 2 つのキーを矩形領域で集約すると，矩形領域

Quadtree の探索を行えば良いが，時区間問合せでは指定され((k, 1), (k + 1, 3)) をキーとして，(A, [(1, 0.7, 0.5), (3, 0.5, 0.3)])

た時区間の全ての時刻に対して U-Quadtree の探索を行う事にをレコードに格納する．この矩形領域を示したのが，図 10 のなり，処理コストが大きい．そこで，本研究では MV3R-木と似灰色の領域である．矩形領域を各オブジェクトについて作成し，たアプローチとして，U-Quadtree のリーフノードのデータにそれらの矩形領域の集合に対して，R-木で索引付けを行う．

対し，一定時間毎に集約情報を作成，時間軸とセル番号をキー
セル番号とした R-木を構築する．時区間問合せでは R-木を用いて条件を満たす時刻を絞り込むことで，効率的に処理を行う．

3

5. 1 データ構造
5. 1. 1 サマリの拡張

1

U-Quadtree で作成されるサマリは (セル番号，オブジェク
ト ID ，セルに含まれる確率) のタプルで表現された．ここでは，対象とするデータが時系列データであるため，作成される

k

タプルは，このタプルに時刻が加わり，(時刻，セル番号，オブ

図 10

k+1

time

セル番号と時刻の 2 次元空間における集約情報

ジェクト ID ，セルに含まれる確率) の形式になる．

5. 1. 2 時区間での情報の集約

U-Quadtree と R-木の関係を図 11 に示す．U-Quadtree に

各時刻に U-Quadtree を構築する場合，時間軸と空間情報がよってサマリが作成され，そのサマリを時区間毎に集約する．

独立しているため，時刻間での位置情報のつながりが無いデー

そして，集約されたデータを R-木で索引付けすることになる．

タ構造になっている．そのため，時区間問合せでは，毎時刻の集約情報からサマリへのアクセスは，集約情報が持つセル番号

U-Quadtree を探索する必要がある．条件となる時区間が広いと時区間中の各時刻をキーに行う．

ほど，処理のコストが増加する．そこで，本研究では一定時間

t=k

t=k+1

...

毎におけるオブジェクトの位置と確率の集約情報を作成し，探索する時区間を予め絞り込むことで，処理のコストを減らすア

U-Quadtree

プローチを取る．
ここでは集約情報として，ある時区間毎にオブジェクトの集約情報

各セルにおける確率の最大値と最小値を扱う．確率の最大値と最小値は閾値による枝刈りに用いる．これをデータ形
式で表すと，(オブジェクト ID, [(セル番号，確率の最大値

R-tree，最小値)]，時区間) というタプルになる．例えば，サマリ列(k, 1, A, 0.5), (k, 3, A, 0.5), (k + 1, 1, A, 0.7), (k + 1, 3, A, 0.3) に対して，オブジェクト ID=’A’ について，時区間 [k, k + 1] で集約すると集約情報は (A, [(1, 0.7, 0.5), (3, 0.5, 0.3)], [k, k + 1])となる．この集約情報から，時区間 [k, k + 1] において，オブジェクト A は 1 と 3 のセルにしか存在しないことがわかる．

5. 1. 3 集約情報の索引付け
時区間での集約情報を作ることで，時間軸について大きな粒度で探索することが可能になった．しかし，集約情報のみでは，問合せ範囲とセルとの包含関係を各セルについて見る必要があ

図 11 U-Quadtree と R-木の関係

5. 2 問合せ処理アルゴリズム
時区間問合せに対して，はじめに R-木による絞り込みを行う．セル番号と時刻の空間での範囲を決めるため，U-Quadtree
で使用している四分木を探索し，問合せ領域に包含されるセルの番号と問合せ領域にオーバラップするセルの番号を求める．
オーバラップするセルの番号と条件の時区間から矩形領域を構築し，R-木による探索を行う．この時点で，矩形領域にオーバ

ラップしなかったオブジェクトを枝刈りすることができる．
次に，到達した R-木が持つレコード，つまりオブジェクトと各セルにおける最大の確率と最小の確率から以下の条件判定を

セル番号
問合せ範囲

17
16

行う．
（ 1 ） 集約情報の時区間が問合せ条件の時区間に包含される

10とき，空間的に包含される各セルについて確率の最大値が閾値6を超えるかどうか

4（ 2 ） 集約情報の時区間が問合せ条件の時区間にオーバラッ
6

プするとき，空間的に包含されるセルの確率の最小値の総和が閾値を超えるかどうか

7

10

12

time

集約情報：( , [ 6, 0.8, 0.6 , 10, 0.6, 0.2 , 16, 0.4, 0.2 ], [6, 10])

（ 3 ） 集約情報の時区間が問合せ条件の時区間にオーバラッ

図 13

時刻がオーバラップし，セルが包含される場合

プするとき，空間的にオーバラップするセルの確率の最大値の総和が閾値を超えるかどうか

セル番号

条件 1 と 2 について，閾値を超える場合，そのオブジェクト
は問合せの条件を満たすとわかるため，問合せ結果に含める．
一方，条件 3 は閾値を満たさない場合，オブジェクトが問合せ

21
18
17

の条件を満たさないとわかるため，各時刻の確率計算を省略することができる．上記の条件について，枝刈りされなかったオ
ブジェクトに関して，各時刻のサマリから確率を計算し，閾値

4
問合せ範囲

判定を行う．サマリの確率を用いた閾値判定は U-Quadtree と6同様の処理を行う．

7

10

12

time

集約情報：( , [ 17, 0.4, 0.2 , 18, 0.6, 0.4 , 21, 0.4, 0.2 ], [6, 10])
セル番号

図 14

時刻がオーバラップし，セルがオーバラップする場合

問合せ範囲

17
16

ト A を問合せ結果に加える事ができる．
最 後 に ，条 件 3 の 例 を 図 14 に 示 す．今 度 は ，問 合 せ10条 件 の 時 区 間 が [7, 12]，オ ブ ジェク ト B の 集 約 情 報 が

6(B, [(17, 0.4, 0.2), (18, 0.6, 0.4), (21, 0.4, 0.2)], [6, 10]) の場合を4考える．このとき，空間的にオーバラップするセルの確率の総和を調べる．図 6 の問合せ範囲にオーバラップするセル 17 の
2

6

10

12

time

集約情報：( , 6, 0.8, 0.6 , 10, 0.6, 0.2 , 16, 0.4, 0.2 , [6,10])
図 12

時刻とセルが包含される場合

確率の最大値が 0.4 であるため，閾値 0.5 を超えることはない．
従って，オブジェクト B は問合せ条件を満たさないとわかるた
め，枝刈りできる．
この一連の確率の閾値処理の流れをアルゴリズム 1 にまとめ

各条件の処理について例を用いて説明する．例で用いる問合せる．処理の基本的な流れは，集約情報が持つセルの情報につい範囲は図 6 と同じとし，確率の閾値を 0.5 とする．条件 1 の例をて見ていくことになる．対象となるセルが問合せ範囲に含まれ

図 12 に示す．問合せ条件の時区間が [2, 12]，オブジェクト A のる場合は，確率の最大値と確率の最小値の総和を求めるため，集約情報が (A, [(6, 0.8, 0.6), (10, 0.6, 0.2), (16, 0.4, 0.2)], [6, 10])

それぞれを足していく．これが 12, 13 行目，22, 23 行目の処理とする．このとき，条件の時区間が集約情報の時区間を包含さになる．一方で，セルが問合せ範囲とオーバラップする場合は，れるので，図 6 の問合せ範囲に包含される各セルについて，確確率の最大値のみを加算する．こちらが 16 行目と 25 行目に該率の最大値を調べる．この場合，6 が問合せ範囲に包含される

当する．最終的に足し合わせた確率の最大値の総和 upper と最セルに該当する．集約情報から確率の最大値が 0.8 とわかり，小値の総和 lower を用いて，閾値判定を行う．29 行目が条件 2

閾値 0.5 を超えるので，オブジェクト A を問合せ結果に含める．

の処理にあたり，31 行目が条件 3 の処理にあたる．問合せ条件

次 に ，条 件 2 の 例 を 図 13 に 示 す．問 合 せ 条 件の時区間に集約情報の時区間が包含される場合と，オーバラッの 時 区 間 が [7, 12]，オ ブ ジェク ト A の 集 約 情 報 がプする場合の違いは 9, 10 行目にある．これは条件 1 の判定に(A, [(6, 0.8, 0.6), (10, 0.6, 0.2), (16, 0.4, 0.2)], [6, 10]) とする．今該当し，時区間が包含される場合は，1 つのセルの最大値を調度は空間的に包含されるセルについて，確率の最小値の総和をべ，閾値を越えた時点で結果を返している．

調べる．図 6 の問合せ範囲に包含されるセル 6 の確率の最小値

上記の閾値判定によって，枝刈りされなかった候補に対して，

は 0.6 であるため， 時区間 [7,10] においてオブジェクトは 0.6

エントリの確率情報を用いた処理を行う．エントリの確率情報

以上の確率で存在したことが保証される．従って，オブジェク

を用いて，パーティクルによる確率計算を省く方法については

アルゴリズム 1 集約情報の確率を用いた枝刈り処理

2 つで行った．四分木のみを利用する手法をここでは便宜上

1: 入力：R-木の探索で得た集約情報 S = (id, triplet set, interval)

MVU-Quadtree と呼ぶこととする．

2: //triplet set : 下記の triplet の集合

6. 1. 2 対象データ

3: //triplet = (cellid, max, min), interval = [start, end]

実験データとして，今回は Brinkhoﬀ の生成器 [14] を用いて

4: 出力:問合せ結果の集合：R，問合せの候補集合：C
5: if ts <= start and end <= te then6:

for triplet ∈ triplet set do

7:

if cellid ∈ Sc thenてサンプリングすることで，パーティクル集合の時系列データを作成した．Brinkhoﬀ の生成器は，道路ネットワーク上のオ

8://Sc ：問合せ範囲に包含されるセル番号の集合

9:

if triplet.max > θ thenR ← id10:

オブジェクトの移動データを生成し，生成した位置情報につい▷ 条件 1 の判定

return R

ブジェクトの移動データを生成する．初期のオブジェクト数を1000，各時刻のオブジェクトの増減数を 5，速度のパラメータを 250，タイムスタンプ数を 100 として生成した．今回は生成

11:

end if

する元となる道路ネットワークには，オルデンブルグの道路

12:lower = lower + triplet.min

ネットワークを用いた．そして，空間全体を 10000×10000 の13:

upper = upper + triplet.max

空間に正規化を行い，生成した位置情報を中心として，300 個

else if cellid ∈ So then

14:
15:

//So ：問合せ範囲に重なるセル番号の集合

16:

upper = upper + triplet.max

18:

リングを行った．データサイズは 237MB である．

6. 1. 3 その他のパラメータ

end if17:

実験で使用した，データセット以外の基本的なパラメータを

end for

19: else

表 2 に示す．四分木の高さは提案手法と比較手法ともに 6，サ20:

for triplet ∈ triplet set do

21:

if cellid ∈ Sc then22:

lower = lower + triplet.min

23:

upper = upper + triplet.max

4096 とした．空間全体に対する分布の偏りを考慮して，問合せの中心点は各軸 2000 から 6000 の範囲からランダムに選択し，
半径 1000 の円を問合せ領域とした．また，確率の閾値は 0.8とした．

upper = upper + triplet.max

25:

表 2 実験の各種パラメータ

end if26:
27:

マリを集約する区間を 10，サマリを格納するブロックサイズを

else if cellid ∈ So then24:のパーティクルを標準偏差 50 のガウス分布に基づいてサンプ

四分木の高さend for

28: end if
29: if lower >= θ then30:

R ← idC ← idサマリの集約する区間

10

サマリのブロックサイズ

4096

問合せ範囲の半径 1000

return R

31: else if upper >= θ then32:▷ 条件 2 の判定

6

確率の閾値

▷ 条件 3 の判定

0.8

return C

33: end if

6. 1. 4 実 行 環 境
実験で用いた計算機のスペックを表 3 に示す．実装は C++同じであるが，本手法が U-Quadtree と異なるのは，集約情報を用いて，各時刻どのセル番号を取得するか絞り込む点である．

U-Quadtree では，各時刻，問合せ範囲にオーバラップするセルを探索し，各セルに対応するエントリをディスクから読み込で行い，コンパイルには Visual Studio Express 2012 を使用した．
表 3 実行マシンのスペック

OS

Windows7 Professional 64bit

CPU Intel(R) Core(TM) i5 CPU M560 @ 2.67GHz

む必要がある．セルをキーとしてエントリを読み込みことで初CPU コア数

めて，オブジェクトがどこのセルにいたのかを得ることができ

メモリ

8GB

る．そのため，すでに結果として含まれているオブジェクトが

HDD

TOSHIBA MK6465GSX 5400rpm

2

存在したセルに対応するエントリを取得することになる．一方で，本手法では集約情報によって，各オブジェクトがどのセルにいたか見つけることができる．そのため，すでに結果として得られたオブジェクトを除外したセル番号の集合を作ることができる．従って，ディスクから読み込むエントリの数を減らすことができる．

6. 2 実験 1：問合せの時区間を変化
問合せ条件の時区間の長さを変化させたときの，処理速度とパーティクル集合を読み込むためのディスクアクセス回数の測定を行った．処理速度，ディスクアクセスともに 3 回のクエリを発行した際の平均値とする．処理速度の変化を図 15 に，パーティクル集合へのディスクアクセス回数の変化を図 16 に示す．

6. 評 価 実 験
6. 1 実験の概要
6. 1. 1 比 較 手 法
比較は提案手法と各時刻に四分木を構築するだけの手法の探索する時区間が長くなるほど，パーティクル集合をディスクから読み込む回数が増え，それに伴い，処理時間も増加した．

2 つの手法を比較すると，提案手法は MVU-Quadtree に比べ，パーティクル集合へのディスクアクセスの回数が減っており，
また処理時間も小さくなった．

MVU-Quadtree

20

提案手法

18

30

16
14

処理時間[s]

処理時間[s]

25
20
15

12
10
8
6

10

4

5

2
0

0
30

40

50

60

70

0

5

問合せ条件の時区間幅

15

20

25

30

集約する時区間の長さ

図 15 条件の時区間の長さと処理速度
MVU-Quadtree

10

図 17

集約する時区間の長さと処理時間

提案手法
1

集約情報から結果に加えられた
データの割合データ取得のディスクアクセス

7000
6000
5000
4000
3000
2000
1000
0
30

40

50

60

0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1

70

0
1

5

10

25

問合せ条件の時区間幅
集約する時区間の長さ

図 16

条件の時区間の長さとデータのディスクアクセス回数
図 18

集約情報による閾値判定で結果に加えられたデータの割合

6. 3 実験 2：サマリを集約する時区間を変化
6000

ス回数と処理時間を測定した．問合せ条件の時区間を 50 で固5000定して，集約する時区間を 1, 5, 10, 25 として計測した．
処理時間の変化を図 17 に示す．処理時間は集約する時区間が長いほど，処理時間は短くなった．図 18 は最終的な問合せ結果であるオブジェクトの数を 1 としたとき，集約情報を用いた閾値判定により，結果に加えられたオブジェクト数の割合で候補と成る集約情報の数

サマリを集約する時区間を変化させたときのディスクアクセ

4000
3000
2000
1000

ある．集約する時区間が長いほど，割合が減少しているため，

0
1

枝刈りの効率は下がっている．これは，時区間が長いほど 1 つ

5

10

25

集約する時区間の長さのセルからオブジェクトが移動するため，集約情報のセルの確
図 19率の最小値が下がってしまうことが原因と考えられる．一方で集約する時区間の長さ候補となる集約情報の数の変化候補とされるオブジェクトに関する集約情報の数は，時区間のMVU-Quadtree
70

連して処理速度が遅くなったという結果から，集約情報の探索

60と集約情報から取得するセルを決定する処理が，処理時間への50

大きな影響があると考えられる．

6. 4 実験 3：パーティクル数を変化
パーティクル集合のパーティクル数を変化させたときの処理処理時間[s]長さとともに小さくなっている．候補となる集約情報の数と関

提案手法

40
30
20
10

時間を測定した．パーティクル数を 1000, 5000, 10000 とし，問合せ条件の時区間を 50 として計測した．処理時間の変化を

0
0

2000

の処理時間の差が大きくなった．これはパーティクル集合の取得と確率計算の 1 回あたりのコストが大きくなり，パーティク
ル集合へのディスクアクセス回数を減らした影響が反映されたためである．

6. 5 実験 4：分布の標準偏差を変化
パーティクル集合をサンプリングするときの，ガウス分布の

4000

6000

8000

10000

12000

パーティクル数

図 20 に示す．オブジェクト数が増加するにつれて，2 つの手法
図 20

パーティクル数の変化と処理時間

標準偏差を変化させたときのパーティクル集合へのアクセス回
数と処理時間を測定した．標準偏差は 50, 100, 200 と変化させ，問合せ条件の時区間を 50 として計測した．処理時間の変化を
図 21 に，パーティクル集合へのアクセス回数の変化を図 22 に示す．標準偏差が大きくなるに連れて，パーティクル集合への率が小さくなることが原因であるため，U-Quadtree のエント

アクセス回数に差がなくなり，それに伴い処理時間の差も小さ

リの集約において，閾値以上の確率を満たすまでセルの確率をくなった．パーティクル集合へのアクセス回数に差がなくなっ結合するなどの工夫によって改善されると考えられる．他の課た理由は，閾値処理によって問合せ結果に加えられるオブジェ

題として，集約情報の作成方法が挙げられる．今回は一定時刻

クト数が少なくなったためである．閾値処理の効果が悪くなっごとに確率を集約し，矩形領域を構築した．しかし，オブジェた原因として，分布の標準偏差が大きくなるに連れて，1 つのクトは集約する時区間中，移動しているため矩形領域内は疎とセルに存在する確率が小さくなったことが挙げられる．1 つのなることが多い．そのため，矩形領域では，フィルタリング性

セルに存在する確率が下がるほど，閾値の条件，特に前述の条能が落ちてしまう．これに対して，集約する時区間の決め方や，

件 1 を満たすオブジェクトが少なくなり，結果としてパーティ

集約情報の領域の作り方を工夫することで，閾値処理の効率をクル集合へのアクセス回数が増加した．

良くすることができると考えられる．

MVU-Quadtree

謝

提案手法

辞

25

本研究の経費の一部は科学研究費（23650047, 25280039），
処理時間[s]20

内閣府最先端研究開発プロジェクト（FIRST），および地球環
境情報統融合プログラム（DIAS-P）による．

15

文

10
5
0
0

50

100

150

200

250

200

250

パーティクル集合の標準偏差

図 21

標準偏差の変化と処理時間

MVU-Quadtree

提案手法

データ取得のディスクアクセス

7000
6000
5000
4000
3000
2000
1000
0
0

50

100

150

パーティクル集合の標準偏差

図 22 標準偏差の変化とデータのアクセス回数

7. まとめと今後の課題
本研究では，パーティクル集合で表現された曖昧な位置情報の時系列データに対する時区間問合せの効率的な処理手法について述べた．任意の確率分布に対する範囲問合せのための索引である U-Quadtree を時空間問合せに対応するための拡張手法を示した．各時刻で U-Quadtree を構築する手法では，時区間問合せにおいて，各時刻について U-Quadtree を探索するため，コストが大きい問題があった．そこで時区間毎に確率と位置情報を集約し，集約情報に対して R-木で索引付けを行う手法を提案した．また，索引付けした R-木を用いた問合せ処理について述べた．評価実験から，データ取得のディスクアクセス回数の削減とそれによる処理時間の削減が確認できた．
今後の課題として，分布の標準偏差が大きくなったときへの対応が挙げられる．標準偏差が大きくなると，閾値処理の効率が下がり，処理時間が遅くなる．これは，1 つのセルの存在確

献[1] Dieter Fox, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun. Monte Carlo localization: Eﬃcient position
estimation for mobile robots. In AAAI/IAAI, pp. 343–349,
1999.
[2] Sebastian Thrun, Wolfram Burgard, Dieter Fox, et al. Probabilistic Robotics. MIT Press, 2005.
[3] 樋口知之. 粒子フィルタ. 電子情報通信学会誌, Vol. 88, No. 12,
pp. 989–994, 2005.
[4] Y Theoderidis, Michalis Vazirgiannis, and Timos Sellis.
Spatio-temporal indexing for large multimedia applications.
In Intl. Conf. on Multimedia Computing and Systems(ICMCS), pp. 441–448, 1996.
[5] Yufei Tao and Dimitris Papadias. Eﬃcient historical Rtrees. In SSDBM, pp. 223–232, 2001.
[6] Yufei Tao and Dimitris Papadias. MV3R-tree: A spatiotemporal access method for timestamp and interval queries.
In VLDB, pp. 431–440, 2001.
[7] Antonin Guttman. R-trees: A dynamic index structure forspatial searching. In ACM SIGMOD, pp. 47–57, 1984.
[8] Yufei Tao, Reynold Cheng, Xiaokui Xiao, Wang Kay Ngai,
Ben Kao, and Sunil Prabhakar. Indexing multi-dimensional
uncertain data with arbitrary probability density functions.
In VLDB, pp. 922–933, 2005.
[9] Ying Zhang, Xuemin Lin, Wenjie Zhang, Jianmin Wang,
and Qianlu Lin. Eﬀectively indexing the uncertain space.
IEEE TKDE, Vol. 22, No. 9, pp. 1247–1261, 2010.
[10] Ying Zhang, Wenjie Zhang, Qianlu Lin, and Xuemin Lin.
Eﬀectively indexing the multi-dimensional uncertain objects
for range searching. In EDBT, pp. 504–515, 2012.
[11] Jon Louis Bentley. Multidimensional binary search trees
used for associative searching. Communications of theACM, Vol. 18, No. 9, pp. 509–517, 1975.
[12] Raphael A. Finkel and Jon Louis Bentley. Quad trees a data
structure for retrieval on composite keys. Acta Informatica,
Vol. 4, No. 1, pp. 1–9, 1974.
[13] Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard
Seeger, and Peter Widmayer. An asymptotically optimal
multiversion B-tree. VLDB Journal, Vol. 5, No. 4, pp. 264–
275, 1996.
[14] Thomas Brinkhoﬀ. A framework for generating networkbased moving objects. GeoInformatica, Vol. 6, pp. 153–180,
2002.