インクリメンタルな空間集約アルゴリズム

6.2.1 クエリの表現

本章では，次のクエリQ を想定する．

Q = hA, DT, T I, SC, DCi (6.1) Aは問合せ領域，DT はセンサデータの種類，T Iは時区間，SCは空間制約であ る．DCは，センサデータの値に対する条件である．

なお，本章では，時間制約(T C)は指定しない場合を想定する．したがって，4 章のクエリにおいて，時区間を分割しない場合に相当するため，問合せ領域A に 対する分割領域a_i は，次のように定義される．

A = a₁∪a₂ ∪...∪a_k (6.2)

∀i, j a_i∩a_j =φ (i6=j) a_i は，分割された領域を示す．kは分割数である．

分割領域 a_iは，4章の式(4.5)，(4.6)と同じように，a^upper_i とa^lower_i の差分領域 として定義される．

6.2.2 インクリメンタルな統合処理のためのデータ構造

空間集約をインクリメンタルに行うためのデータ構造として，以下の3つのリス トを導入する．

• RESULT LIST_i

a_iに対して受信したセンサデータオブジェクトを保持する．RESULT LIST_i の要素を oi,k とする時，oi,k.loc ∈ai が成り立つ．

• OV ERLAP LIST_i

OV ERLAP LIST_iは，a_iと重なり合う空間データオブジェクトの集合を表

し，OV ERLAP LIST_i の要素p_i,jについて，p_i,j.geom∩a_i 6=φが成り立つ．

p_i,jはa_iに対するセンサデータオブジェクトの統合対象となりうる．

• LAST OV ERLAPi

a_i のセンサデータを収集した時に，空間データオブジェクト p に含まれる すべてのセンサデータの収集が完了する場合に，pをLAST OV ERLAP_iの 要素とする．すなわち，LAST OV ERLAPi は，ai のセンサデータ受信時 に，集約処理を完了させることのできる空間データオブジェクトの集合を示 す．p は，p.geom∩a_i 6= φ が成り立つ最大の領域に関連付けられる．なお，

LAST OV ERLAPi ⊆OV ERLAP LISTi である．

OV ERLAP LIST_iおよびLAST OV ERLAP_iについて，図6.1の例で説明する．

図中のP1, P2, P3, P4はポリゴンデータオブジェクト，O1, O2, O3, O4, O5はセン サデータオブジェクトである．

図6.1において，P1.geom∩a_i 6=φ，P2.geom∩a_i 6=φが成り立つので，P1，P2 は，ともに，OV ERLAP LISTiの要素となる．しかし，aiのデータ受信時に，集約 処理を完了することができるのは，P1のみであるため，P1∈LAST OV ERLAP_i である．領域a_i+1 については，P2, P3∈LAST OV ERLAP_i+1となる．

6.2.3 センサデータとポリゴンデータの統合

次の処理手順に従って，空間データ統合を行う．

1 統合データの準備

図5.1の空間データサーバから，空間データオブジェクトpを取得する．

2 集約処理のためのデータ構造の作成

問合せ領域を分割し，各分割領域 aiに対して，RESU LT LISTi，

OV ERLAP LIST_i，LAST OV ERLAP_i を作成する．さらに，この段階で，

OV ERLAP LIST_i と LAST OV ERLAP_iの要素を計算する．

a

i-1

a

i

a

i+1

a

i-1

upper

a

i

upper

a

i+1

upper

a

i+2

P1 P2

P4 P3

O4

O3 O2

O1

O5

図 6.1: 領域分割に基づくポリゴンデータとの統合例 3 クエリQを仲介エージェントに送信する

4 仲介エージェントから検索結果を受信し，処理を行う

最終結果を受信するまで，検索結果を受信するごとに，4.1と4.2の処理を順 番に繰り返す．ここで，検索結果は，分割領域ごとに，a₁から順番に受信さ れ，対応する RESULT LIST_iに格納される．

4.1 中間結果の計算

検索結果を受信する度に，RESU LT LIST_iの要素であるすべてのセンサデー タオブジェクト oi,k について，OV ERLAP LISTi の要素である空間データ オブジェクトp_i,j との比較を行う．2.1.3節で説明したfilter&refinement戦略 に従い，o_i,k.loc ∈ p_i,j.rect という条件を調べ，条件を満たす p_i,j について，

oi,k.loc ∈pi,j.geom が成り立つ場合に，pi,j の属性として，oi,k の値を用いて 中間結果を計算する．

4.2 集約処理の完了

この段階で，aiに対するすべてのサーバからの結果が受信されていれば，

LAST OV ERLAP_i の要素であるすべての空間データオブジェクト p_i,j につ

いて，保持されている中間結果を用いて集約結果を計算し，その結果を表示 する．この時，集約結果が，センサデータ dtl に対する条件 dcl を満たして いるかどうかについても評価する．

OV ERLAP LIST_i は，センサデータオブジェクトを関連付けられるポリゴン

データオブジェクトを探し出す際の探索コストを軽減するためのデータ構造であ

り，LAST OV ERLAP_i は，ポリゴンデータオブジェクトの集約処理の完了を判 定するためのデータ構造である．

6.2.4 空間補間に基づくメッシュ統合

次に，インクリメンタルなメッシュ統合の手順について示す．メッシュ統合は，

5.1.2節で述べたように IDW に基づいて行われる．セル c を空間データオブジェ

クト pと置き換えることで，メッシュ統合の各ステップを記述できる．ここでは，

6.2.3節の [1]，[4.1]，[4.2]に対応する処理が異なるため，それらのステップについ

て述べる．

1⁰ 統合データの準備

セルの大きさを指定し，問合せ領域 A に対するメッシュデータを生成する．

セル cは，メッシュデータを構成する空間データオブジェクトと言える．

4.1⁰ 中間結果の計算

センサデータオブジェクトo_i,k (∈ RESULT LIST_i) について，o_i,k.loc ∈ c_i,j.rect が成り立つ時，c_i,j の属性として，o_i,kごとに，観測値(もしくは時系 列集約値)と位置情報(o_i,k.loc)を保持する．

4.2⁰ 集約処理の完了

a_m (m = 1,2, ..., i) に対する LAST OV ERLAP_m の要素c_m,n について，

cover rect(c_m,n)⊆a^upper_i を評価する．この条件が成り立つ時，式(5.2)，(5.3) に基づき，cover rect(c_m,n)に含まれるセンサデータを用いて，セルc_m,n の 値を計算する．その値が，センサデータ dt_l に対する条件式dc_l を満たす場 合に，最終的な出力結果として表示する．

IDWに基づくメッシュ統合では，セルc に含まれるセンサデータオブジェクト だけでなく，cover rect(c)に含まれるすべてのセンサデータオブジェクトの収集を 完了するまでは，集約処理を完了させることができない(図6.2)．

6.2.5 オーバーレイ処理に基づく異種センサデータ統合

5.1.2節で述べたように，オーバーレイ処理を実現するためには，センサデータ

の種類ごとに空間補間に基づくメッシュ統合を適用する必要がある．したがって，

オーバーレイ処理に基づくインクリメンタルなメッシュ統合処理は，基本的には，

6.2.4節で述べた手順と同様に行われる．

オーバーレイ処理に基づくメッシュ統合では，DT に指定したすべてのセンサ データ dt_l に対するメッシュデータML^lと，統合結果を格納するメッシュデータ OLが必要となる．そこで，まず，ML^lおよびOLを生成する．

a

i-1

a

i

a

i+1

target cell cover rect

a

i+1

a

i

a

i-1

upper

upper upper

図 6.2: セルの集約計算のための領域判定

次に，領域 a_i のデータを受信した時，ML^l に対しては，6.2.4節の[4.1⁰]と同 じ手順で，中間結果の保持を行い，[4.2⁰]と同じ手順で，集約処理の完了判定を行 う．この処理を，すべての ML^l について適用する．ただし，OLの計算について は，ML^lに対する処理とは異なり，a_iのデータを受信時に，[4.1⁰]の中間結果の保 持は行わず，[4.2⁰]で，ML^lとは異なる条件で，統合結果の計算を行う．6.2.4節の [4.2⁰]に対する OL の処理として，OLの構成要素であるセル cm,n(1≤ m ≤ i) に 対して，次の処理が行われる．

4.2 ⁰⁰ 集約処理の完了

LAST OV ERLAP_m の要素である c_m,nに対応するML^l (l = 1,2, ...) の要 素 c^l_m,n について，集約処理が完了しているかどうか調べる．すべてのセンサ データdt_l に対して，c^l_m,n の集約処理が完了している場合に，OLの要素c_m,n の統合処理を行い，その結果を表示する．

ドキュメント内 検索手法とセンサデータベースへの応用 (ページ 126-130)