グラフ索引構造を用いた高速類似探索

摘要

大規模な高次元のデータに対して高速な類似探索を可能とする新たなアプローチを提案する．このrnアプローチは，オブジェクト集合から構築されたスモールワールド性を有するグラフを索引構造として用い，類似オブジェクト探索問題を，グラフの辺をたどりながらクエリオブジェクトに類似する頂点を見つけるグラフ探索問題としてとらえる．我々は，探索の効率性に優れた索引構造として，単純な近傍グラフの拡張である次数低減近傍グラフを提案し，このグラフを構成する効率的アルゴリズムと，これに最良優先近傍探索アルゴリズムを組み合わせた高速類似探索法を提案する．提案法の探索性能を，探索対象として文書データを用いた実験により評価し，探索性能と次元数との関係を，人工データを用いて解析した．結果，高次元データを対象とした場合，提案法が非常に小さい探索コストで類似探索することを確認した．