 論文

  

曖昧な位置情報に基づく空間問合せの処理手法

          石川 佳治


図  移動オブジェクトの位置推定          !"# 

センサ環境や移動ロボット応用では，測定の誤差やオブジェク
ト自身の移動により，オブジェクトの位置自体が曖昧である状況がしばしば生じる．本稿では，問合せオブジェクトの位置が正規分布に基づく確率密度関数で曖昧に指定されている状況における空間データベース問合せについて，その処理手法のアイデアを示す．
  
              

                                            はじめに曖昧な位置情報に基づくデータベース問合せ処理技術は，近年その必要性を増している．センサ環境においては，センサの位置を考慮して問合せ処理を行うことが求められることがある．
を利用することで正確な位置を把握できる場合もあるが，必ずしもが利用できる状況ばかりではない．また，による位置の取得による電力の消費は，電池によりセンサ機器を駆動する場合にはできるだけ避けたいものである．曖昧な位置情報の別の例として，移動ロボットがある．移動するロボットが，自身の位置を確実に把握することは必ずしも容易ではない．移動の方向や距離などの情報を用いて推定することは可能であるが，誤差が伴う．
本研究では，オブジェクトの位置情報が確定的ではなく，曖昧に表現されている場合の問合せ処理について考える．特に，オブジェクトの位置が正規分布で表されている場合を対象とする．正規分布による曖昧な位置の表現は，移動ロボットにおける移動位置を統計的に推定する場合などにおいてしばしば用いられる．
図 にそのアイデアを示す．この図は，移動ロボットが，自身の移動情報をもとに定期的に自身の移動位置の推定（）を行う状況を示している．楕円で示したのは，各時点における移動位置の推定により得られた，正規分布に基づく確率密度関数の等確率面である．このような移動の各時点において，自身の近くにどのようなオブジェクトがあるかを移動オブジェクトが把握したいというのは，しばしば発生する要求である．
そこで本研究では，その位置が正規分布で表されるようなオブジェクトが，その周辺に位置するオブジェクトを検索するための空間問合せについて考える．ただし，周辺のオブジェクトは確定的な位置で表される点データであるとする．対象とする問合せは，距離に基づく範囲問合せ（）である．距離に基づく範囲問合せについては，これまでに多くの研究が存在しているが，問合せを行うオブジェクトの位置自体が確定的でなく，       正会員

名古屋大学情報連携基盤センター   

その位置が正規分布で表されるような場合についての問合せ処理については，これまで研究がなされていない．
本稿では，距離に基づく範囲問合せの概念を拡張し，確率的範囲問合せの概念を提案する．まず，直感的なアイデアを示すため，より容易な 次元の場合について，問合せ処理方式のアイデアを示す．次いで， 次元の場合についてそのアイデアを一般化する．
木などの空間索引が効率的に利用できるようなアルゴリズムを示す．

%&$   関連研究
存在位置が不確かなオブジェクトに対する問合せ処理のアプロー
チは他にもみられる．
らは，データベース中の各オブジェクトについて確率密度関数が対応し，そのオブジェクトの確率的な位置を与えるような状況を考えた．問合せは長方形の領域で指定され，その領域内に含まれる確率が閾値以上であるようなオブジェクトを効率的に求めることが目的である．彼らは，そのような問合せを効率的に評価するための索引手法として 木を提案した．本研究と同様，確率的な範囲問合せを考えているが，彼らのアプローチではデータベース中のオブジェクトの位置が不確定で問合せ領域は確定的であり，本研究とは逆の状況を扱っている．
確率密度関数としては特定の分布を想定してはいない．とは，問合せオブジェクトおよびデータベースオブジェクトの両者の位置が曖昧であるような場合の範囲問合せ手法を提案した．各オブジェクトが存在する領域は長方形の領域として表される．その他，曖昧性を持ったデータに対する問合せ処理に関連する研究はにもある．
移動オブジェクトデータベースにおいて，曖昧なオブジェクトの位置を正規分布に基づく確率分布でとらえようとするアプロー
チは， に見られる．移動オブジェクトにおける曖昧な位置情報に関しては，などでも議論がある．

'

()&*+

*+


$ , -.

  次元の確率的範囲問合せ$

アイデアを示すため，まず 次元の場合を考える．図 に，次元直線上に位置する つのオブジェクト      を示している． から  のそれぞれの位置は      であり，位置に曖昧性はない．一方， の位置は，原点を中心とし分散が である正規分布        で表されているとする．図中の曲線はその確率密度曲線を表している．ここで， から距離以内にあるオブジェクトを探索したいとする． の位置は確率的にしか分からないため，たとえば  の位置が   である場合には  が問合せ結果に含まれ，一方，の場合には  のみが問合せ結果となる．
問合せオブジェクト  の位置に応じて問合せ結果が異なることから，範囲問合せの概念の拡張が必要となる．そこで，空間データベースにおける従来の範囲問合せの概念を拡張し，確率的範囲問合せ（）を定義する．

.



/ " "  0   1 %2

定義  確率的範囲問合せ を，その位置が正規分布     に従うオブジェクトとする．

日本データベース学会    論文
prob0.45



0.4

0.25
0.20.150.10.05

a0-4-3-2-1qb01c2de34ÆÆ0 + +   45で表されるとする．つまり       である．このようなオブジェクト  が与えられたとき， との距離が Æ 以下である確率が 以上であるようなオブジェクトの集合を Æ  で表す．
先の例では，問合せオブジェクト  の  座標  の確率密度関数が      であり，Æ  である場合を述べた．さらに，
，すなわち確率の閾値がと与えられたと仮定する．この問合せを処理するために，次のように考える．たとえば，オブジェクト について考える． が  の探索範囲に含まれるのは， の位置  が       の範囲にある場合である．この範囲内に  が存在する確率は，確率密度関数をこの範囲で積分す ることで得られ，     となる．同様に，
は      の場合に探索範囲に含まれ，その確率は 6  である．さらに， で表されるとする．ただし， はの共分散行列であり， は次元の平均ベクトルである．なお，本稿では共分散行列の行列式は  であると想定するが，このように仮定しても一般性を失わない．また，オブジェクトの平均的な位置も，原点の場合
Ù ¼ に単純化する．
この節では，まず等確率面が円であるような特殊な場合について検討し，それを一般の場合について拡張する．

$

すなわち， の位置が  である確率が，確率密度関数

 なる  を求める       

図 ,  次元の範囲問合せアルゴリズム
  , &3  " "  0 %  2 7  +8

図 $  次元の確率的範囲問合せ  $ &3  " "  0 %  2 

%24  5      0.3

   Æ

0.35

   

   となる．つまり，  という閾値以上となるのは   のみであり， は閾値以下となる． は  よりもさらに遠い位置にあるため，計算するまでもなく明らかに閾値以上とはならない．すなわち，問合せ結果は   となる．
以上のアイデアを踏まえると，以下のように与えられた問合せを処理するために探索が必要な範囲を限定できることがわかる．

 

 の場合

まず，特殊な場合として，共分散行列が単位行列である場合（ Á）について考える．式において  ¼ Ü   とおくと，4,5    Æ  

yda,

  次元の確率的範囲問合せ$ Ü     Ü  b

図 - $ 次元の確率的範囲問合せ（ Á の場合）
  - $&3  " "  0 %  2 4 0   Á5
 が求まると，後の処理は簡単である．原点を中心とした半径の範囲にあるオブジェクトをすべて検索すればよい．この例では， は条件を満たし  は条件を満たさない．半径  内のオブジェ
クトの検索は，空間索引を用いて効率的に処理できる．
 一般の場合
 問合せの例

一般の場合，すなわち，共分散行列  が単位行列とは限らない場合について考える．この場合，等確率面は円とはならず楕円の形状となる．簡単化のため  ¼ という制約を置いている
ため，確率密度関数の式
は4,5問合せオブジェクト  の位置が， 次元の正規分布xq$ ÜRaÆ

オブジェクト の位置  が      になると，  から距離 Æ内に問合せオブジェクト  が入る確率は  未満となるため，確率の閾値  を満たさないことになる．確率密度関数は左右対称であるため，負の方向についても同様の議論が成り立ち， の場合には閾値  を満たさない． を直接的に求めることはできな
いが，適当な値から 分探索を行うことで，近似値を求めることができる．上の例で示した      Æ    の場合には，  となる．
以上をまとめると， 次元の確率的範囲問合せ Æ  の問合せ処理アルゴリズムは図 のようになる．次節では，このアイデアを 次元の場合について拡張する．

$45を満たすとする．与えられた Æ と  に対して  の値を解析的に求めることはできないため，事前に数値積分を行い，Æ    の対応表を求めておく．なお，確率の閾値  については，ユーザから半端な値が与えられることはまれであるので，     のように，粗い設定としても，実用上問題ないと考えられる．

オブジェクト が確率的範囲問合せの結果となることは，その座標値  が          を満たすことと等価である．

4-5-4$5   となり，等確率面は原点を中心とする円の形状となる．
次の例でアプローチを説明する．図 は，原点を中心とした正規分布によりその位置が表される問合せオブジェクト  と検索対象のオブジェクト  の位置を示している．また，原点から  の距離の位置に，半径 Æ の円 を図示している．ただし， は，性質        とし，   を，以下を満たす値とする．

   4,5 Ü Ü   Ü

日本データベース学会 4.5
   

論文と簡略化できる．
図 に問合せのイメージを示す．この図では，問合せオブジェ
クト  の周辺に    という検索対象のオブジェクトが存在する．この場合，確率密度関数が等方的でないため，前節で述べたような単純な範囲の限定は行えない．

yp qTpqx

yqbdTpqxq

  .  Ü  Ü のイメージ  . 9     Ü 3  Üa図c

制約を満たすとする½ ．

 $ 次元の確率的範囲問合せ（一般の場合）
   $&3  " "  0 %  2 4   * 05図 上限と下限の関数
以下のような性質を用いる．行列 

 で定義される Ü Ü$ つの関数  454(5の等確率面の形状は円である．また，同じ確率について等確率面を描いたとき，  Ü  Ü の等確率面は，式の確率密度関数の等確率面に外接および内接する．

4.5$

 の値は次の性質に基づいて求められる．

45とする．  Ú はそれぞれ  番目の固有値と固有ベクトルである（  ）．ただし，とする．ここでは以下の議論の便 宜上， と置く．このとき，以下の性質が成り立つ．
性質$

なお， つの関数  Ü  Ü は， 次元平面全体で積分してもとはならないので，もはや確率密度関数ではない．
 Ü  Ü には次のような性質がある．



性質 ! 任意の Ü について以下が成り立つ．

 Ü   Ü   Ü45 Æ である
性質 "  を，原点からの距離が  であり，半径がような円領域とする．ただし， は以下の制約を満たすとする．のスペクトル分解を Ú Ú  

45

この  に対し， は

4$5  


4,5 という関係を満たす．

45以上は，式の積分の変数変換を行うことで証明できる．
 Á の場合には，  Ü に対して，確率の閾値  および円の半径 Æ が与えられたときに，式の制約を満たす  を返す対応表があれば，範囲問合せが処理できることを示した．一方，上の性質は，同じ対応表を利用して  が導出可能であることを述べている．同様のアプローチで  も導出できる．
上記の性質の活用法について述べる．図 は，先ほどまでと見方を変え，ある   の方向を横軸とし，縦軸（ 軸）を関数の値としてグラフをプロットしたイメージを表す． Ü の確率密度関数の曲線が，関数  Ü  Ü により，上下から挟まれているのが分かる．影が入った領域のうちの左側は，横軸の値が  である点（つまり，原点からの距離が  である点）を中心として，半径 Æ の円領域で  Ü を積分した状況を表し，先ほどの議論よりその体積は  である．同様に右側の領域は，原点からの距離が である点を中心として，半径 Æ の円領域で  Ü を積分した状況を表し，こちらの体積も  である．

45z

また， Ü  Ü は，このような性質を満し，等確率面が円である関数のうちで，最良のものである．

 Ü  Ü は，  Ü の上限と下限を与えていることになる．
図  に対する  Ü  Ü のイメージを図 . に示す．外側の円が  Ü に対応し，内側の円が  Ü に対応する．この図は各関数において同じ値（確率）が得られるような   座標値の軌跡を示しており，ある特定の  軸（確率の値の軸）の値についてスライスした結果にあたる．

p qTpqTpq
Ta 問合せ処理方式のアイデア
まず，  Ü について考える．  を，原点からの距離が  であり，半径が Æ であるような円領域とする．ただし， は以下の

aT   % 0 
図xy と  の役割

3½ 以降では，状況に応じて Ô Ü Ô Ü Ý の表記を用いるが，同義とする．

日本データベース学会    論文
この図から，原点から  よりも離れてしまうと，高めの見積もりを与える  Ü であっても，半径 Æ で積分したときにその確率は  未満になることがわかる．つまり，原点から  より離れたオブジェクトは探索候補とはなりえない．一方，原点からの距離が  以下の場合には，低めの見積もりを与える  Ü でも面積以 以上であることが保障される．つまり，原点からの距離が 下のオブジェクトについては，無条件に確率が  以上となる．原点からの距離が  より大きく  以下のオブジェクトについては，実際に確率  を満たすかどうかは，数値積分を実際に行わないとわからない．

確率的範囲問合せ処理のアルゴリズムは次のように与えられる．

- 行目において半径  の範囲検索を行い，積分結果が 以上となりうる候補オブジェクトをすべて選択する．各オブジェクトについて距離  以内にあるかをチェックし（ 行目），条件を満たさない場合のみ数値積分により条件をチェックする． 行目の処理
で，空間索引を用いて効率的に候補を絞り込めると考えられることから，一部のオブジェクトについては数値積分が必要ではあっても，全体としては効率的なアルゴリズムとなっている．

.

-%24 Æ 5
 を規定している共分散行列  の逆行列を固有値分解して   を得る  Æ から  を求める統計表（事前に作成）をもとに，を求める

原点から距離  以内にあるオブジェクトをすべて検索し，候補オブジェクトの集合  とする     原点から  への距離が  以下  は明らかに条件を満たす
 









を， を中心とする半径 Æ の円領域とする
     
数値積分する        


図  $ 次元の範囲問合せ処理アルゴリズム
   $&3  " "  0 %  2  00  7  +8
図 ( に，図  に対する問合せ処理の例を示す．問合せ処理アルゴリズムに従えば，まず，距離  以内のオブジェクトが検索され，   が候補オブジェクトとなる．このうち， は  以内の距離にあるため，無条件に問合せ結果として出力できる．  に関しては数値積分が必要となるが，上記のようなアプローチにより，本当に数値積分が必要なオブジェクトのみについて，対象を絞り込むことが可能となる．

 議論と今後の課題
本稿では，位置が正規分布で表されるようなオブジェクトにおいて，範囲問合せを行う新たなアプローチを述べた．従来の範囲問合せの概念を拡張し，確率的範囲問合せを定義した． 次元の場合に対するアイデアを拡張し， 次元の一般的な場合にも適用可能なアルゴリズムを示した．実際には，本稿で提案したアルゴリズムは 次元以上の場合についても適用可能である．たとえば次元の場合については，  の固有値を   とした 
とき，  ととればまったく同じアルゴリズムが適用できる．ただし，次元数が増えると数値積分などのコストが高く$,,yb ddxcdqaT 問合せ処理のアルゴリズム

  aaT

図 ( $ 次元の確率的範囲問合せ処理  ( $&3  " "  0 %  2  00 なるという問題がある．
今後は，実験に基づく評価と最近傍問合せへの拡張などを考えたい．

謝辞

本研究の一部は，文部科学省科学研究費（による．

($-,）の助成

文献

 : *+ 3 % *+ ;<       8/ 0  &3/3  0 =    $$ % *+ >? @  0+ A  3   "+ A  ; &  / " "  0  0  8/ 0 3   =    // B.$ : $,
, % *+ >? @  0+ A  3   "+ A  2& 8/ 0 3   8  "#    80  ?  . 9  ( // $B$ /8"
$-
- % *+ C D    "+ A  % + + 3 : ? 
;<  3E  8+ 30   / " "  0 +0+ 3 0     3   =   // .B 70&/8" $- C    /  0 79  / 3 /  0 3   ? 00 &
 A /  0 3  0   
!" # # =3  / " 0+  $. >  0 3 * :0 * /  +    
8 & "#  /0  0 =  $  %& #'    ( )**+ ?  .
 ,  // B, : (((  %  E   +  3 7 ? 0 3  -        @ 8  $  +A+  3  *+ F    "  G  $$
( C '  % *+ D D  H@ 9  I @  3  "+ A  =3E  8 &3 80     3  F + "   / " "   30    0 =  // ($$B(,, 70 $  '+ H I 3 3 >  E . '+ =' 00 $ ! H 0  7  0   *+ 8"  3 C C0+ )/3   3   3  " 00 +   A 8 "  0 "# #   ?   9  ,
// $B$ : (((石川 佳治   

名古屋大学情報連携基盤センター教授．データベース，データ工学，情報検索等に興味を持つ．日本データベース学会，情報処理学会，電子情報通信学会，人工知能学会，，各会員．

7* =;;; *

日本データベース学会   