ANN検索の説明
k最近傍探索(kNN)は、クエリベクトルに最も近いk個のベクトルを見つけます。具体的には、クエリベクトルをベクトル空間内のすべてのベクトルと比較して、k個の完全一致が現れるまで行います。kNN探索は完全な精度を保証しますが、高次元ベクトルを含む大規模なデータセットにとっては時間がかかります。
対照的に、近似最近傍探索(ANN)は事前にインデックスを構築する必要があります。様々なインデックスアルゴリズムは、検索速度、メモリ使用量、精度のトレードオフを示しています。一般的に、これらのアルゴリズムを実装するためには、検索範囲を狭めることと、高次元ベクトル空間を低次元部分空間に分解することの2つの方法があります。
検索範囲を狭めることで、クエリベクトルと比較する可能性のある候補のサブセットのみを選択することで、検索時間を短縮することができます。これにより、関係のないベクトルを避けることができます。ベクトルがサブセットに含まれるかどうかを判断するには、ベクトルをソートするためのインデックス構造が必要です。
インデックス構造を形成するために一般的に利用可能な3つのアイデアがあります:グラフ、ツリー、およびハッシュ。
HNSW:グラフベースのインデックス付けアルゴリズム
Hierarchical Navigable Small World(HNSW)は、階層的な近接グラフを作成することによってベクトル空間をインデックス化します。具体的には、HNSWは、各層のベクトル(または頂点)間に近接リンク(またはエッジ)を描画して、単層の近接グラフを形成し、それらを積み重ねて階層グラフを形成します。最下層にはすべてのベクトルとその近接リンクが含まれています。層が上がるにつれて、より小さなベクトルと近接リンクのセットのみが残ります。
階層的な近接グラフが作成されたら、検索は以下のように行われます:
-
トップレイヤーのエントリーポイントとしてベクトルを見つけてください。
-
利用可能な近接リンクに沿って、最も近いベクトルに徐々に移動してください。
-
最上層で最も近いベクトルを決定したら、エントリーポイントとして下層で同じベクトルを使用して、その層で最も近い隣人を見つけます。
-
最下層に最も近いベクトルが見つかるまで、前の手順を繰り返してください。
LSH:ハッシュベースのANNインデックスアルゴリズム
局所性に敏感なハッシング(LSH)は、さまざまなハッシュ関数を使用して、任意の長さのデータピースを固定長の値にハッシュとしてマッピングし、これらのハッシュをハッシュバケットに収集し、少なくとも1回同じ値にハッシュされたベクトルを候補ペアとしてタグ付けすることによって、ベクトル空間をインデックス化します。
DiskANN: Vamanaグラフに基づくディスク上のANN検索
HNSWとは異なり、Vamanaのインデックス作成過程は比較的シンプルです。
-
ランダムグラフを初期化する
-
最初にグローバル重心を特定し、最も近いポイントを決定してナビゲーションポイントを見つけます。グローバル比較を使用して、平均検索半径を最小限に抑えます。
-
ステップ2から初期化されたランダム近隣グラフと探索開始点を使用して近似最近傍探索を実行します。探索経路上のすべての点を候補近隣集合として使用し、アルファ=1でエッジトリミング戦略を適用して探索半径を縮小します。
-
ステップ3を調整したアルファ値>1（論文で推奨されている1.2）で繰り返し、グラフの品質と再現率を改善してください。
インデックスが準備できたら、検索は以下のように行われます:
-
関連データ(クエリセット、PQ中心点データ、コードブックデータ、検索開始点、インデックスメタなど)をロードします。
-
インデックス付きデータセットを使用してcached_beam_searchを実行し、各ポイントのアクセス時間をカウントし、アクセス頻度が最も高いnum_nodes_to_cacheポイントをキャッシュします。
-
WARMUP操作は、サンプルデータセットを使用してデフォルトで実行され、cached_beam_searchを実行します。
-
指定されたパラメータLごとに設定されたクエリでcached_beam_searchを実行し、リコール率やQPSなどの統計情報を出力します。ウォームアップデータやホットスポットデータの統計情報はクエリ時間に含まれません。
詳細については、DiskANN, A Disk-based ANNS Solution with High Recall and High QPS on Billion-scale Datasetを参照してください。