(D)　データ構造の開発

地理情報システムやCADシステムでは，点，線分，領域などの図形データを管理しており，様々な検索処理が実行されます．

本研究室では，大規模な図形データを記憶し，効率的な検索を可能とするためのデータ構造について研究をしてきました．

以下に，その一例を示します．

分割された領域の例

　図のように，平面上のある領域Rが，多くの部分領域に分割されているものとします．

対象とする検索操作は，

・ R内のある点を指定したときに，それを含む領域を見つける点検索

・ R内のある範囲を指定したときに，それと重なるすべての領域を見つける範囲検索

の2種類です．本研究室では，分割された領域の隣接関係を示すグラフ（領域隣接グラフ）と

R木あるいはセル構造を組み合わせたデータ構造を提案しました．そして，実データを用いた

計算機実験により，このデータ構造の範囲検索効率が従来のものより優れていることを示しました．

図形データに関しては，他に，動的な多次元点データや平面上の線分データなどを扱うための

データ構造について研究してきました．

パターン認識の分野では，データベース中から，質問データに最も近いものを求める最近傍検索や，

質問データに近いものからk個のデータを求めるk近傍検索などの処理がよく用いられます．

高速な最近傍検索手法として，TLAESAと呼ばれる手法が知られていました．本研究室では，

TLAESAのデータ構造と検索アルゴリズムを改良し，データ間の距離の計算回数を削減する方法を示しました．

さらに，解の精度を保証できるような近似k近傍検索手法へと拡張しました．

［発表論文］

・　“MD木の領域分割法の改良,” 電子情報通信学会論文誌(D-I), vol. J82-D-I, pp. 508-513 (1999).

・　“2段階の木による領域情報管理構造の構成法,” 電子情報通信学会論文誌(D-I), vol. J83-D-I, pp. 134-142 (2000).

・　“GBD木における線分の分割法の改良,” 電子情報通信学会論文誌(D-I), vol. J83-D-I, pp. 1300-1304 (2000).

・　“TLAESAに基づく近似k近傍検索手法,” 電子情報通信学会論文誌(D), vol. J89-D, pp. 1610-1616 (2006).

・　“地理データに対する隣接領域グラフを利用した領域管理手法,” 電子情報通信学会論文誌(D), vol. J90-D, pp. 586-591 (2007).

など