空間インデクシングに基づく距離推定を用いた高速かつ省メモリな近似最近傍探索

摘要

本稿では，高次元かつ大規模なデータセットを高速かつ省メモリで扱うための近似最近傍探索手法を提案する．近似最近傍探索は，入力ベクトルに最も距離が近いベクトルを探索する最近傍探索問題において，探索誤りを許容することで計算時間，メモリ使用量を大幅に削減するものである．ハッシュ構造を用いてクエリからの距離を推定する手法に改良を加え，より一般的なデータに対して高速に解を得られるようになった．また，ベクトルを量子化表現することでメモリ使用量を削減した．実験では大規模なSIFT特徴とGIST特徴のデータセットを用いて精度，処理時間，メモリ使用量の観点で比較を行い，最新の既存手法と比べて高速に最近傍点を得られることを確認した．