ANNとは
Approximate Nearest Neighbor / 近似最近傍探索
厳密な最近傍探索の代わりに、多少の精度を犠牲にして高速に類似ベクトルを検索する手法の総称
ひとことで言うと
完璧な正確さより速さを優先して、似ているデータを高速に見つける検索方法の総称。
概要
ANN(Approximate Nearest Neighbor、近似最近傍探索)とは、高次元ベクトルの集合から、クエリベクトルに最も近い点を厳密に求める代わりに、多少の精度低下を許容しながら高速に「近い」点を検索する手法の総称。 データ量・次元数が増えるほど、全件を総当たりで比較する厳密な最近傍探索は計算コストが膨大になる(次元の呪い)。ANNは、探索範囲をあらかじめ絞り込んだり、近似的に距離計算したりすることで、精度と速度のトレードオフを許容しながら実用的な検索速度を実現する。 HNSW(グラフベース)、IVF(クラスタベースの転置ファイル)、LSH(Locality-Sensitive Hashing、局所性鋭敏型ハッシュ)等、複数のアプローチのアルゴリズムが存在し、データ規模・次元数・要求精度に応じて使い分けられる。ベクトルデータベースやセマンティック検索の基盤技術として広く利用されている。
背景
埋め込みベクトルを用いた類似検索の需要が高まる一方、全件と総当たりで比較する厳密な最近傍探索は、データ量や次元数の増加とともに計算コストが急激に増大し、実用的な応答速度を確保できなくなる。ANNは、多少の精度低下を許容することでこの計算コストの課題を解決し、大規模なベクトル集合でも実用的な速度で類似検索を行えるよう発展した。
歴史
1998年: Piotr IndykとRajeev Motwaniが、STOC 1998にて論文「Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality」を発表。代表的なANNアルゴリズムの1つであるLSH(Locality-Sensitive Hashing)の枠組みを提案した。 以降、IVFとProduct Quantizationを組み合わせた手法(2011年)やHNSW(2016年)等、クラスタリングやグラフ構造に基づく多様なANNアルゴリズムが提案され、ベクトルデータベースの基盤技術として普及した。
利点
- 厳密な最近傍探索と比べ、大規模・高次元なベクトル集合でも実用的な速度で検索できる
- アルゴリズムやパラメータの調整により、検索速度と精度のトレードオフを用途に応じて制御できる
欠点
- 近似的な手法であるため、厳密な最近傍探索と比べて検索漏れが発生しうる
- アルゴリズムの選定やパラメータチューニングに、データ特性への理解を要する
比較
- HNSW — HNSWは、グラフ構造を用いた代表的なANNアルゴリズムの1つ
- IVF — IVFは、ベクトルをクラスタへ分割し探索範囲を絞り込む代表的なANNアルゴリズムの1つ
- ベクトルデータベース — 多くのベクトルデータベースは、内部でANNアルゴリズムを用いて類似検索を高速化している