表題番号：2003A-948 日付：2006/03/24
研究課題ヒルベルト曲線を利用した多次元データ管理システム
研究者所属（当時） 資格 氏名
（代表者） 大学院情報生産システム研究科 教授 鎌田　清一郎
研究成果概要
　本研究では，画像表現形式のまま移動や拡大等の処理ができ，範囲検索が高速にできるような多次元データ管理手法として、ヒルベルト曲線を用いて線形４分割木構造表現を行う手法を検討した．これは，空間内においてデータの有無を1，0の2値データで表現し，データがある領域をアドレスと領域サイズの組を一つのデータとして表し，そのデータの組をヒルベルト曲線が辿る順に並べて、多次元データを表現する手法である．ヒルベルト曲線はデータ間の近傍保存性が良く，データのクラスタ抽出ができるという特徴を持つ。範囲検索を高速に行えるMD木による範囲検索では，検索する領域を分割し，それぞれの検索領域を木構造の根から順にノードを辿って検索する．これに対し本手法は，1次元データで管理していることから，検索する領域を1次元データの先頭から検索領域が見つかるまで探索し，検索できれば，分割された他の検索領域は1次元配列上で近傍に存在するはずであるため，その近傍を検索するだけでよい．また，本手法は領域をアドレスで管理していることから，検索はアドレスの比較により簡単に行うことができる．本研究では，ヒルベルト曲線を用いたデータ表現から，表現形式を変えずに，移動，拡大・縮小，回転，抜き取り，共有，交わり，投影，制約，結合，差といった10種の処理を行う手法について述べた．2次元データである2値画像を用いて，本手法の有効性を確認した．また、MD木によるデータ表現において範囲検索の検索速度を比較し、本手法はMD木に対して20～30%検索効率がよいことがわかった．さらに，本手法の応用として，実時間描画のためにデータベースから高速な検索が必要である仮想都市空間のデータ管理への本手法の適用可能性について検討した．今後は，高速に範囲検索が行え，データ表現のまま種々の演算処理ができることから，仮想都市空間のデータ管理への適用をさらに検討する予定である．