メインコンテンツまでスキップ
バージョン: User Guides (BYOC)

ANN 検索の解説

k-近傍（kNN）検索は、クエリベクトルに最も近い k 個のベクトルを見つけます。具体的には、クエリベクトルをベクトル空間内のすべてのベクトルと比較し、k 個の完全一致が現れるまで続けます。kNN 検索は完璧な精度を保証しますが、特に高次元ベクトルで構成される大規模なデータセットの場合、時間がかかります。

これに対し、近似最近傍（ANN）検索では、事前にインデックスを構築する必要があります。さまざまなインデックスアルゴリズムは、検索速度、メモリ使用量、精度の間にトレードオフを示します。一般に、これらのアルゴリズムを実装するには、検索範囲を狭める方法と、高次元ベクトル空間を低次元部分空間に分解する方法という 2 つのアプローチがあります。

検索範囲を狭めることで、クエリベクトルとの比較対象となる候補のサブセットのみを選択し、検索時間を短縮できます。これにより、無関係なベクトルを回避できます。あるベクトルがそのサブセットに含まれるかどうかを判断するには、ベクトルをソートするためのインデックス構造が必要です。

インデックス構造を形成するには、一般にグラフ、ツリー、ハッシュという 3 つの考え方があります。

HNSW: グラフベースのインデックスアルゴリズム​

Hierarchical Navigable 小 World（HNSW）は、階層的な近接グラフを作成することでベクトル空間をインデックス化します。具体的には、HNSW は各レイヤー上でベクトル（または頂点）間に近接リンク（またはエッジ）を描いて単一レイヤーの近接グラフを形成し、それらを積み重ねて階層グラフを構築します。最下層にはすべてのベクトルとその近接リンクが保持されます。レイヤーが上がるにつれて、保持されるベクトルと近接リンクのセットは小さくなります。

階層的な近接グラフが作成されると、検索は次のように行われます。

  1. 最上層でエントリーポイントとなるベクトルを見つけます。

  2. 利用可能な近接リンクに沿って、徐々に最も近いベクトルへ移動します。

  3. 最上層で最も近いベクトルを特定したら、そのベクトルを下のレイヤーのエントリーポイントとして使用し、そのレイヤーでの最近傍を見つけます。

  4. 最下層で最も近いベクトルが見つかるまで、前述の手順を繰り返します。

hnsw-explained

LSH: ハッシュベースの ANN インデックスアルゴリズム​

Locality-sensitive hashing（LSH）は、さまざまなハッシュ関数を使用して任意の長さのデータピースを固定長の値（ハッシュ）にマッピングし、これらのハッシュをハッシュバケットに集め、少なくとも 1 回同じ値にハッシュされたベクトルを候補ペアとしてタグ付けすることで、ベクトル空間をインデックス化します。

locality_sensitive_hashing

DiskANN: Vamana グラフに基づくディスク上の ANN 検索​

階層化された検索のために階層グラフを構築する HNSW とは異なり、Vamana のインデックス処理は比較的単純です。

  1. ランダムなグラフを初期化します。

  2. グローバル重心を最初に特定し、最も近い点を決定することでナビゲーションポイントを見つけます。平均検索半径を最小化するためにグローバル比較を使用します。

  3. ステップ 2 で初期化されたランダムな隣接グラフと検索開始点を用いて、近似最近傍検索を実行します。検索パス上のすべての点を候補隣接セットとして使用し、エッジトリミング戦略を alpha = 1 で適用して検索半径を削減します。

  4. グラフの品質と再現率を向上させるため、alpha > 1（論文では 1.2 を推奨）に調整してステップ 3 を繰り返します。

インデックスの準備が整うと、検索は次のように行われます。

  1. クエリセット、PQ 中心点データ、コードブックデータ、検索開始点、インデックスメタなど、関連するデータを読み込みます。

  2. インデックス化されたデータセットを使用して cached_beam_search を実行し、各点のアクセス回数をカウントして、アクセス頻度が最も高い num_nodes_to_cache 個の点をキャッシュします。

  3. サンプルデータセットを使用して cached_beam_search を実行する WARMUP 操作がデフォルトで実行されます。

  4. 指定されたパラメータ L ごとにクエリセットを用いて cached_beam_search を実行し、再現率や QPS などの統計情報を出力します。Warmup およびホットスポットデータの統計はクエリ時間に含まれません。

詳細については、DiskANN, A Disk-based ANNS ソリューション with High Recall and High QPS on Billion-scale データセット を参照してください。