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

• 松村 聖司

• 赤間 浩樹

• 山室 雅司

書誌事項

タイトル別名

• Approximate Nearest Neighbor Search using GPGPU for Massive High-dimensional Vectors with kNN Graph

抄録

大規模な画像や音声等の各認識処理において，高次元ベクトルの近似最近傍探索の処理が行われている．近似最近傍探索では，探索精度と探索時間の関係がトレードオフの関係にある．そして近似最近傍探索法の１つに，kNN グラフを用いた探索がある．kNN グラフは，グラフの枝数を増やすことで，高精度かつ高速な探索が可能になる．しかし，kNN グラフの構築コストは大きく，構築コスト削減の為，近似 kNN グラフが考案されている．近似 kNN グラフの １ つに NN-Decent という手法があり，枝数が少ないと，構築コストが小さくなるといった特徴がある．その為，本検討では，近似 kNN グラフ及び GPGPU を用いた高精度かつ高速な近似最近傍探索法について検討を行った．その結果，枝数の多い場合の kNN グラフと同等の精度及び処理時間で探索が可能であることを確認した．An approximate nearest neighbor search for high-dimensional vectors are used for massive object, image and sound recognition. In an approximate nearest neighbor search, there is trade-off between searching accuracy and speed. One of approximate nearest neighbor search, there is kNN graph. kNN gprah is able to search with high speed and high accuracy when that graph has many branches. However, because it needs too much time to build kNN graph, approximate kNN graph is invented to reduce time building kNN graph. There is NN-Decent in one of approximate kNN graph. When there are few branches, NN-Decent doesn't spend much time to build. Therefore, we studied searching method using GPGPU with high accuracy and high speed when NN-Decent has a few branches. As a result, we confirmed that it was possible to search with high accuracy and high speed compared with kNN graph, which has many branches.

収録刊行物

• 研究報告コンピュータセキュリティ（CSEC）

  研究報告コンピュータセキュリティ（CSEC） 2013 (55), 1-6, 2013-03-07

詳細情報

• CRID: 1571135652896253696
• NII論文ID: 110009551678
• NII書誌ID: AA11235941
• 本文言語コード: ja
• データソース種別:
  • CiNii Articles