移動物体を対象とした時空間データ管理構造
野澤　博 1.研究の背景

近年，VR技術やCG技術の進歩により大規模な３次元仮想空間の構築が可能となってお り，それを様々な分野に応用し，活用しようという動きが活発になっている．３次元 仮想世界を用いた現実擬似体験やアニメーション作成等を考える際に，これら時空間 データに対して高速なレスポンスが可能なデータ管理手法が必要になっているが，最 近では特に「時間」の重要性が認識されてきている．
従来の多次元データの管理構造として，静的データを管理対象としたk-d木，動的デ ータに拡張したMD木等が提案されている．ここでの静的とは，データがあらかじめ全 て与えられているという意味であり，動的とは，逐次データが投入・削除されていく という意味である．またこれらの手法を応用して時空間情報を持つデータを管理する 場合，代表的な手法としては，MT構造，ST構造，3D管理構造などが考えられている． しかしながら，これらの手法は位置が固定された物体をデータの対象としており，移 動物体に対しては用いられていない．
そこで，本研究では移動物体を対象とした時空間データに対して，今後ベースとなる ようなデータ管理方式と新たに考案したデータ管理方式の２種類の管理方式を提案す る．さらに，その２種類の方式でシミュレーション実験をおこない，性能評価等の比 較・検討をおこなった．

2.提案するデータ構造

（１）提案するデータ構造１
この方式は，まず各物体の移動経路を微少時間で区切ることにより線分の集合と考え ，その中点をk-d木を用いて木構造を作成する．次に木構造の葉ノードにおいて，各 線分にその線分を含む最小の領域（以下，外接直方体）を設定し，各ノードにはその ノードの２つの子ノードの外接直方体を共に含む最小の領域を設定する．そして，検 索する際にはこの領域と検索領域を比較することにより，まず検索範囲に含まれる線 分を検出し，そこから物体を導き出すという手法を取った．

（２）提案するデータ構造２
この方式は，空間木と時間木の２つの木構造を用意しておき，空間と時間の検索範囲 に応じて，検索範囲の割合の狭い方の木構造を検索するという方式を採用する．空間 木は，各移動物体の移動経路を含む最小の領域（以下，外接長方形）を設定し，その 中点をk-d木を用いて木構造を作成した．次に木構造の各ノードにはそのノードの２ つの子ノードの外接長方形を共に含む最小の領域を設定する．そして，検索する際に はこの領域と検索領域を比較することにより検索を実行する．
時間木は，移動物体をその物体の発生・消滅時間により２次元データに変換し，３分 木で管理する手法を取った．
計算機実験では，２種類の管理方式について比較の結果，検索範囲がある程度狭い場 合にはデータ構造１が，広い場合にはデータ構造２が有効であることが確認された．

3.まとめ

本研究では従来のデータ管理構造の問題点について検討をおこない，移動物体を対象 とした２種類のデータ管理方式を提案した．さらに計算機によるシミュレーション実 験をおこない，２種類のデータ管理方式の比較・検討をした．その結果，検索効率は 「検索範囲がある程度狭い場合にはデータ構造１が，広い場合にはデータ構造２が優 れている」ことがわかった．
今後の課題としては，複数状態を有する移動物体及び動的データへの適用の可能性に ついての検討が必要であると思われる．