ANN
Approximate Nearest Neighbor Search
近似近傍探索_
Approximate k-NN
kNNは、他のデータとの全ての距離を計算する
正確に近いものを特定できるが、データ量が多いと計算に時間がかかる
次元の呪い
一方で、ANNでは、当たりを付けて一部のデータとの距離のみを計算して結論を出す
正確性は疎かになるが、計算コストが小さく済む
全体の1万件のうち、100件しか距離を見ない、みたいなイメージ
#wip
https://wangzwhu.github.io/home/file/acmmm-t-part3-ann.pdf
https://www.elastic.co/jp/blog/understanding-ann
手順GPT-4.icon
1. インデックス構築
データセットを特定の構造(例: グラフ、ツリー)に変換します。
代表的なアルゴリズムには以下のようなものがあります:
HNSW: グラフベースで高性能。
Annoy: ツリー構造を使用。
Faiss: ベクトルデータに特化。
NMSLIB
2. 近似検索
クエリをインデックスと比較し、類似度が高いデータを効率的に取得します。
精度を調整可能(例: 返す候補数、探索の深さなど)。
https://docs.opensearch.org/docs/latest/vector-search/vector-search-techniques/approximate-knn/