画像データベース類似検索におけるk最近傍探索の高速計算アルゴリズム

スポンサーリンク

概要

論文の詳細を見る
本論文では、高次元ベクトル空間におけるk最近傍探索の高速近似アルゴリズムを提案する。k最近傍探索において提案されてきた従来方法は、次元が大きくなると急激にその性能が劣化することが知られている。ところが、近年盛んに研究されている画像類似検索では、10^2のオーダーの特徴量が用いられている。また、検索者好みの検索システムにするために検討されている適合フィードバック法では、従来の静的空間分割法が利用できない。一方、動的空間分割法の基本アルゴリズムとして良く知られているFriedmanらの射影アルゴリズムも、高次元になるに従って性能は劣化する。我々は射影アルゴリズムの高次元の性能を改善するための近似的手法を提案する。シミュレーション実験によって、高次元における提案方式の性能を検証した結果、200次元の空間において、90%の検索精度を全数探索の約半分のCPU時間で達成した。
2001-03-30

著者

関連論文

もっと見る

スポンサーリンク