ビットコーディングを用いた R-tree に基づく多次元空間内近傍探索の高速化
書誌事項
- タイトル別名
-
- High Dimensional Nearest Neighbor Searching by R-tree Using Bit Coding
この論文をさがす
説明
本論文では, 高次元空間内のオブジェクト近傍探索に有用な空間ビットコーディング法と呼ぶインデックス構築手法を提案し, その構造と探索, 挿入, 削除アルゴリズムについて述べる.画像データベースシステムにおいては, テキスト形式で記述された付加情報に基づく検索のみならず, 画像の内容に基づく検索が優れたヒューマンインタフェースを実現する上で必要である.しかし内容検索を実現するには, 画像処理を実行して特徴量を抽出した後, 類似した特徴量を有する1つもしくは, 複数個の画数サンプルをデータベースから探索する必要がある.特にデータベースが大規模化し, さらに特徴量における次元数が高次元化するほど, 類似検索のための探索処理が高負荷となる.これに対し, R-treeおよびその派生手法は対象画像の射影空間位置に基づいて, 迅速に類似検索を実行するためのインデックス検索法である.本論文で提案する空間ビットコーディング法はR-treeの技術を利用するとともに, これに範囲矩形(bounding rectangle)の位置, サイズをビットコーディングによって表現する仮想範囲矩形(virtual bounding rectangle)の概念を導入することにより, 探索時においてさらなるディスクアクセスの低減化を実現した.本研究では実験を通じて, 探索, 挿入処理のディスクアクセス数を計測し, 従来手法と比較することにより空間ビットコーディング法を評価する.その性能評価によって, 大規模データ集合に対する本手法の優位性を示す.
収録刊行物
-
- 情報処理学会研究報告. DBS,データベースシステム研究会報告
-
情報処理学会研究報告. DBS,データベースシステム研究会報告 116 (2), 303-310, 1998-07-09
一般社団法人情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1572261552106808192
-
- NII論文ID
- 110002930856
-
- NII書誌ID
- AN10112482
-
- ISSN
- 09196072
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles
