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

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ソリューションを参照してください。