ANNとは

Approximate Nearest Neighbors（ANN）とは、高次元のベクトルデータ（例えば、テキストや画像のベクトル埋め込み）に対して、もっとも近い近傍点を厳密に計算せずに近似的に見つけるための手法です。

高次元ベクトルデータにおいて、全てのデータ点との距離を計算してもっとも近い点を見つけるのは計算コストが高くなりがちです。特に大規模なデータセットやリアルタイムのアプリケーションでは、この計算コストが問題となります。ANNは、高速で効率的なアルゴリズムを使用して、もっとも近い近傍点を迅速に見つけることができるため、実用的な速度で近傍探索を行うことが可能です。このようなアルゴリズムは、類似画像検索やレコメンドシステムなどの多くの分野で利用されています。

この記事では、以下のANNのアルゴリズムについて紹介します。

• LSH
• HNSW
• IVF

LSH (Locality-Sensitive Hashing)

LSHは、類似したアイテムが高い確率で同じ「バケット」にハッシュされるような特殊なハッシュ関数を用います。

LSHのアルゴリズム

LSHアルゴリズムは、以下の主要なステップで構成されます。

1. ハッシュ関数の選定: 類似したアイテムが同じバケットに入る確率を最大化するハッシュ関数を選ぶ
2. データのハッシング: 各データポイントをハッシュ関数によってバケットに割り当てる
3. バケット内での検索: クエリポイントと同じバケットに割り当てられたデータポイントを検索する
4. 候補の絞り込み: バケット内での検索により得られた候補から、更なる計算を用いてもっとも近いデータポイントを選出する

HNSW (Hierarchical Navigable Small World)

HNSWは、多層のグラフ構造を用いてデータを表現し、クエリポイントから効率よく近いデータポイントを検索します。

HNSWのアルゴリズム

HNSWアルゴリズムは、次の主要なステップによって構成されます。

1. グラフの構築: データポイントを頂点とする多層のグラフを構築
2. エッジの割り当て: 近いデータポイント同士にエッジを割り当て、グラフ上での探索が効率的に行えるようにする
3. 階層的探索: グラフの上層から開始し、順次下層へと移動しながらクエリポイントにもっとも近いデータポイントを探索

IVF (Inverted File)

Inverted File（IVF）は、クラスタリングにより高次元データを効率的に検索する方法です。

IVFのアルゴリズム

IVFの基本的なアルゴリズムは以下のように構成されます。

1. クラスタリング: データポイントをあらかじめいくつかのクラスタに分け、各クラスタにIDを割り当てる
2. インデクシング: クラスタIDと各データポイントの関連性をインデクス（逆引きファイル）に保存する
3. 検索: クエリが与えられた際には、もっとも近いクラスタを特定し、そのクラスタ内で詳細な距離計算を行って最近傍を見つける

それぞれの手法の比較

速度と精度

• LSH: 高速な検索が可能ですが、精度は他の方法と比較して低い場合が多いです。
• HNSW: 高い精度と効率性を兼ね備えていますが、メモリ使用量が多くなる可能性があります。
• IVF: インデクス化により高速な検索が可能ですが、クラスタリングの品質に依存するため、精度が不安定になる可能性があります。

メモリ使用量

• LSH: ハッシュテーブルの使用により、メモリ効率は一般的に良いです。
• HNSW: 高度なグラフ構造により、メモリ使用量が大きくなる可能性があります。
• IVF: インデックス情報を保存する必要があるため、データ量に応じてメモリ使用量が増加します。

実装の複雑さ

• LSH: アルゴリズムがシンプルで、多くのプログラミング言語で容易に実装できます。
• HNSW: 複雑なグラフ構造を使用するため、実装がやや難しいです。
• IVF: データ構造自体は比較的シンプルですが、効率的なクラスタリングとインデクシングが必要です。

参考

https://archive.pinecone.io/learn/vector-indexes/
https://speakerdeck.com/matsui_528/jin-si-zui-jin-bang-tan-suo-falsezui-qian-xian