GPGPUを用いた近似kNNグラフによる大規模高次元ベクトルに対する高速な近似最近傍探索法の検討

スポンサーリンク

概要

論文の詳細を見る
大規模な画像や音声等の各認識処理において,高次元ベクトルの近似最近傍探索の処理が行われている.近似最近傍探索では,探索精度と探索時間の関係がトレードオフの関係にある.そして近似最近傍探索法の1つに,kNN グラフを用いた探索がある.kNN グラフは,グラフの枝数を増やすことで,高精度かつ高速な探索が可能になる.しかし,kNN グラフの構築コストは大きく,構築コスト削減の為,近似 kNN グラフが考案されている.近似 kNN グラフの 1 つに NN-Decent という手法があり,枝数が少ないと,構築コストが小さくなるといった特徴がある.その為,本検討では,近似 kNN グラフ及び GPGPU を用いた高精度かつ高速な近似最近傍探索法について検討を行った.その結果,枝数の多い場合の kNN グラフと同等の精度及び処理時間で探索が可能であることを確認した.
2013-03-07

著者

関連論文

もっと見る

スポンサーリンク