Hierarchical Navigable Small World索引の理解
ベクトル近似類似検索用のHNSW索引の作成方法を理解するには、これらの例を使用してください。
Navigable Small World(NSW)の概念は、次の3つの特性に基づいて、グラフ内の各ベクトルが他の複数のベクトルに接続する近接グラフを作成することです。
- ベクトル間の距離
- 挿入時に検索の各ステップで考慮される最も近いベクトル候補の最大数
(EFCONSTRUCTION) - ベクトルごとに許可される最大接続数(
NEIGHBORS)内
前述の2つのしきい値の組合せが高すぎる場合は、緊密に接続されたグラフが作成されるため、検索処理が遅くなる可能性があります。一方、これらのしきい値の組合せが低すぎる場合、グラフが疎になりすぎるか、切断されるため(あるいはその両方)、検索中に特定のベクトルの間のパスを見つけることが困難になります。
ベクトル検索のNavigable Small World (NSW)グラフ走査は、グラフ内の事前定義済のエントリ・ポイントから始まり、密接に関連するベクトルのクラスタにアクセスします。検索アルゴリズムでは、2つのキー・リストを使用します。1つはCandidatesであり、グラフの走査中に検出されたベクトルの動的に更新されたリスト、もう1つはResultsであり、これまでに検出された問合せベクトルに最も近いベクトルを含みます。検索が進行するにつれて、アルゴリズムはグラフ内を移動し、結果内のベクトルよりも近い可能性があるベクトルを探索して評価することで、候補を継続的に絞り込みます。このプロセスは、Resultsの中で最も遠い方に近いCandidatesにベクトルがなくなると、局所的な最小値に達し、問合せベクトルに最も近いベクトルが識別されたことを示し、終了します。
これを次の図に示します。
説明した方法では、グラフへのベクトル挿入で特定のスケールまでは堅牢なパフォーマンスを示します。このしきい値を超えたHierarchical Navigable Small World (HNSW)のアプローチでは、確率スキップ・リストで確認された構造と同質の多層階層を導入することによって、NSWモデルが強化されています。この階層アーキテクチャは、グラフの接続を複数のレイヤーに分散し、後続の各レイヤーに下のレイヤーからのリンクのサブセットが含まれるように編成することによって実装されます。この階層化により、上位レイヤーは長い距離のリンクを取得してグラフ全体の高速な経路として効果的に機能し、下位レイヤーは短いリンクに重点を置いて詳細でローカルなナビゲーションを容易にします。その結果、検索は上位レイヤーから開始され、ターゲット・ベクトルの領域にすばやく近づき、より正確な検索のために下位レイヤーに段階的に移動し、上位レイヤーから下位レイヤーに移動するときにベクトル間の短いリンク(小さい距離)を利用することで、検索の効率と精度が大幅に向上します。
これがHNSWでどのように機能するかをよりよく理解するために、この階層が確率スキップ・リスト構造にどのように使用されるかを見てみましょう。
確率スキップ・リスト構造では、リンクされたリストの複数のレイヤーが使用され、上位レイヤーでは下位レイヤーよりも多くの数がスキップされます。この例では、17番を検索しようとしています。最上位レイヤーから開始して、17が見つかるか、リストの最後に到達するか、17より大きい数値を見つけるまで、次の要素にジャンプします。リストの最後に到達した場合、または17より大きい数値が見つかった場合は、前のレイヤーで17未満の最後の数値から開始します。
HNSWでは、NSWレイヤーと同じ原則が使用され、高いレイヤーでベクトル間の距離が長くなります。次の図の2D空間にこれを示します。
最上位レイヤーには最も長いエッジがあり、最下位レイヤーには最も短いエッジがあります。
最上位レイヤーから開始し、1つのレイヤーでの検索はエントリ・ベクトルから開始されます。次に、各ノードについて、現在のノードよりも問合せベクトルに近い近隣がある場合は、その近隣にジャンプします。アルゴリズムでは、問合せベクトルのローカル最小値が見つかるまで、この処理が続けられます。ローカル最小値が1つのレイヤーで検出されると、次のレイヤーの同じベクトルを使用することで検索がその新しいレイヤーに移動し、そのレイヤーで検索が続行されます。このプロセスは、すべてのベクトルを含む最下位レイヤーのローカル最小値が見つかるまで繰り返されます。この時点で、検索は見つかったその最後のローカル最小値のあたりでNSWアルゴリズムを使用した近似類似検索に変換され、問合せベクトルに最も類似した上位k件のベクトルが抽出されます。上位レイヤーは、NEIGHBORSパラメータによって設定された各ベクトルの最大接続数を持つことができますが、レイヤー0は2倍の接続数を持つことができます。次の図はこのプロセスを示しています。
レイヤーは、(Oracle Inmemoryグラフではなく)インメモリー・グラフを使用して実装されます。各レイヤーでは、個別のインメモリー・グラフが使用されます。すでに説明したように、HNSW索引の作成時には、上位レイヤーのベクトルごとの最大接続数はNEIGHBORSパラメータを使用して、挿入時に検索の各ステップで考慮される最も近いベクトル候補の最大数はEFCONSTRUCTIONパラメータ(ここで、EFはEnter Factorを表します)を使用して微調整できます。
前述のように、Oracle AI Vector Searchを使用して、HNSW索引を使用して近似検索問合せを実行する場合は、近似検索を実行するターゲット精度を指定できます。
HNSW近似検索の場合、ターゲット精度のパーセント値を指定して、検索の精査で考慮される候補の数に影響を与えることができます。これは、アルゴリズムによって自動的に計算されます。値が100の場合は、完全検索と同様の結果となる傾向がありますが、システムでは引き続き索引が使用され、完全検索は実行されません。オプティマイザでは、問合せの述語がある場合は索引を使用する方が高速になる可能性があるため、引き続き索引を使用することが選択されることがあります。ターゲット精度パーセンテージの値を指定するかわりに、EFSEARCHパラメータを指定して、索引の精査中に考慮される特定の最大候補数を指定できます。その数値が大きいほど、精度が高くなります。
ノート:
- 近似検索問合せでターゲット精度を指定しない場合、索引の作成時に設定された精度が継承されます。索引の作成時に、作成する索引のタイプに応じて、パーセンテージ値またはパラメータ値を使用してターゲット精度を指定できることがわかります。
- 索引検索では、索引の作成時の設定と異なるターゲット精度を指定できます。HNSW索引の場合は、
EFSEARCHパラメータ(索引の作成時に指定されたEFCONSTRUCTION値より大きい)を使用してより多くの近傍を検索し、より正確な結果を取得できます。索引の作成時に指定するターゲット精度によって、索引作成のパラメータが決まり、ベクトル索引検索のデフォルトの精度値としても機能します。
親トピック: インメモリー近傍グラフ・ベクトル索引について