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

ANN 検索の説明

k近傍 (kNN) 検索は、クエリベクトルに最も近い k 個のベクトルを見つけます。具体的には、クエリベクトルをベクトル空間のすべてのベクトルと比較し、k 個の正確な一致が見つかるまで続けます。kNN 検索は完全な精度を保証しますが、特に高次元ベクトルを含む大規模データセットでは時間がかかります。

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

検索範囲を狭めることで、クエリベクトルと比較する可能性のある候補のサブセットのみを選択することで検索時間を短縮できます。これにより、不必要なベクトルを回避します。ベクトルがサブセット内にあるかどうかを判断するには、ベクトルを並べ替えるインデックス構造が必要です。

インデックス構造を形成するための一般的なアイデアは、グラフ、ツリー、およびハッシュの3つがあります。

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

階層的ナビゲーション可能なスモールワールド (HNSW) は、階層的な近接グラフを作成することでベクトル空間にインデックスを付与します。具体的には、HNSW は各レイヤーのベクトル（または頂点）間に近接リンク（またはエッジ）を描画して単層の近接グラフを形成し、それらを積み重ねて階層的なグラフを形成します。最下層にはすべてのベクトルとそれらの近接リンクが含まれます。レイヤーが上に進むにつれて、少数のベクトルと近接リンクのみが残ります。

階層的な近接グラフが作成されると、検索は以下のようになります：

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

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

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

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

hnsw-explained

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

ローカリティセンシティブハッシング (LSH) は、任意の長さのデータをさまざまなハッシュ関数を使用して固定長の値（ハッシュ）にマッピングし、これらのハッシュをハッシュバケットに収集し、少なくとも一度同じ値にハッシュされたベクトルを候補ペアとしてマークすることで、ベクトル空間にインデックスを付与します。

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 などの統計情報を出力します。ウォームアップおよびホットスポットデータの統計はクエリ時間には含まれません。

詳細については、DiskANN、10億スケールデータセットで高再現率と高QPSを実現したディスクベースのANNSソリューションを参照してください。