木構造に基づいた時空間データ管理の検討
西田研究室 奥野 倫也
1. はじめに
近年の著しいCG（Computer Graphics），VR（Vertual Reality）技術の進歩により大規模な3次元仮想世界の構築が可能になってきている．それに伴い空間+時間のデータ，いわゆる時空間データの効率的な管理が問題になってきている．最近では時空間データの管理方式として，MT構造・ST構造・3Ｄ管理構造・AT構造など様々な手法が考えられてきたが，これらの研究においてはデータの検索形態として矩形エリアの時空間範囲検索のみを取り扱っているものが多く，その管理構造が実際に求められる様々な検索形態を満足できるかどうかは疑問である．そこで本研究では建物設備など位置が動かない物体の時空間データに対し，AT構造をもとに様々な検索を行うことができるシステムを構築した．また，動作確認のためのシミュレーション実験及び結果の検討を行った．
2. AT構造
本研究では，時空間データ構造を構築する手法としてAT構造を採用した．AT構造とは，物体の空間情報によって作成した「空間木」と時間情報によって作成した「時間木」の2つのデータ構造を持ち，検索範囲の全範囲に対する割合が最小となるデータ構造を選択して検索を行うというものである．この検索方式は，木構造によるデータ管理においては検索範囲が狭い場合は検索効率が非常によいが，検索範囲が広くなるにつれて検索効率が悪化するという性質を和らげるということに主眼を置いている．AT構造は従来の時空間データ管理構造であるST構造，3D管理構造などと比較すると，検索時間が短くて済むことが確認されている．
3. 本研究で取り扱う検索形態
近年の時空間データに対する研究において矩形エリアの時空間範囲検索が最も多く扱われている理由としては，この範囲検索が最も一般的に用いられる検索形態であり，その他の検索形態にも応用できるものと考えられているからである．このことを念頭に置き，本研究では矩形エリアの時空間範囲検索を核として様々な検索が可能なデータ構造の構築を行った．具体的な検索形態については以下のとおりである．
- 矩形エリアの時空間範囲検索（完全包含）
- 矩形エリアの時空間範囲検索（部分包含）
- 最近点検策
- 球状エリアの時空間範囲検索
- 分布濃度による時空間範囲検索
- 状態の継続時間による時空間範囲検索
- 状態に対する検索
- 時間指定範囲にないオブジェクトの検索
また以上の検索形態について，それぞれ動作確認のシミュレーション実験を行った．
4. デモシステムの概要
前章で述べた検索形態を実現するデモシステムを構築した．以下にその概略を示す．
図1 デモシステム概略図
5. まとめ
本研究では従来の範囲検索主体のデータ構造に加え，矩形エリアの時空間範囲検索以外の様々な検索形態を取り入れたシステムを構築した．その結果，それらの検索形態がそのような範囲検索主体のデータ構造でも実現できることを確認した．
今後は，従来の検索形態に対してもパフォーマンスを向上させつつ，さらに多種多様な検索形態が実現できるかどうか検討し本システムに取り込んでいきたい．また，今回は静的でかつ位置が動かない物体の時空間データを対象としたが，動的なデータや位置が動く物体の時空間データに対しても検討を行う必要があると考えられる．