HNSW
HNSWインデックスはグラフベースのインデックス作成アルゴリズムであり、高次元の浮動ベクトルを検索する際のパフォーマンスを向上させることができる。優れた検索精度と低レイテンシを提供する一方で、階層グラフ構造を維持するために高いメモリオーバーヘッドを必要とする。
概要
HNSW（Hierarchical Navigable Small World）アルゴリズムは、異なるズームレベルの地図のような多層グラフを構築する。最下層にはすべてのデータ点が含まれ、上位層は下位層からサンプリングされたデータ点のサブセットで構成される。
この階層構造では、各レイヤーはデータポイントを表すノードを含み、それらの近接性を示すエッジで接続されている。上位レイヤーはターゲットに素早く近づくための長距離ジャンプを提供し、下位レイヤーは最も正確な結果を得るためのきめ細かい検索を可能にする。
その仕組みは以下の通りだ：
- エントリーポイント：探索は、グラフ内のあらかじめ決められたノードである最上位レイヤーの固定されたエントリー・ポイントから開始される。
- 貪欲な探索：アルゴリズムは、クエリーベクトルにこれ以上近づけなくなるまで、現在のレイヤーで最も近い近傍に貪欲に移動する。上位レイヤーは、下位レイヤーでより細かい探索を行うための潜在的なエントリーポイントを見つけるための粗いフィルターとして機能し、ナビゲーションの役割を果たす。
- レイヤーは下降する：現在のレイヤーでローカル・ミニマムに到達すると、アルゴリズムは事前に確立されたコネクションを使用して下のレイヤーにジャンプダウンし、貪欲な探索を繰り返す。
- 最終 絞り込み：このプロセスは最下層に到達するまで続けられ、最終的な絞り込みステップで最近傍を特定する。
HNSW
HNSWの性能は、グラフの構造と探索動作の両方を制御するいくつかの重要なパラメータに依存する。これらには以下が含まれる：
M:各ノードがグラフの各階層で持つことのできる最大エッジ数または最大接続数。Mが高いほどグラフは密になり、探索する経路が増えるため、想起率と精度が向上する。上の画像に示すように、M = 5は、HNSWグラフの各ノードが最大5つの他のノードに直接接続されていることを示す。これにより、ノードが他のノードに到達するための複数の経路を持つ、適度に密なグラフ構造が形成される。efConstruction:インデックス構築時に考慮される候補の数。一般にefConstructionが高いほど質の高いグラフになるが、構築により多くの時間を要する。ef:検索時に評価される近傍ノードの数。efを増やすと、最近傍を見つける可能性が向上しますが、検索プロセスが遅くなります。
これらの設定をニーズに合わせて調整する方法の詳細については、Index paramsを参照してください。
インデックスの構築
Milvusでベクトル場にHNSW インデックスを構築するには、add_index() メソッドを使用し、index_type 、metric_type 、インデックス用の追加パラメータを指定します。
from pymilvus import MilvusClient
# Prepare index building params
index_params = MilvusClient.prepare_index_params()
index_params.add_index(
field_name="your_vector_field_name", # Name of the vector field to be indexed
index_type="HNSW", # Type of the index to create
index_name="vector_index", # Name of the index to create
metric_type="L2", # Metric type used to measure similarity
params={
"M": 64, # Maximum number of neighbors each node can connect to in the graph
"efConstruction": 100 # Number of candidate neighbors considered for connection during index construction
} # Index building params
)
この設定では
index_type:構築するインデックスのタイプ。この例ではHNSWとします。metric_type:ベクトル間の距離の計算方法。サポートされている値には、COSINE、L2、IPがあります。詳細については、メトリック・タイプを参照してください。params:インデックスを構築するための追加設定オプション。M:各ノードが接続できる近隣ノードの最大数。efConstruction:インデックス構築時に接続を考慮する近隣候補の数。
HNSWインデックスで使用可能な構築パラメータについては、インデックス構築パラメータ を参照してください。
インデックス・パラメータを構成したら、create_index() メソッドを直接使用するか、create_collection メソッドでインデックス・パラメータを渡してインデックスを作成できます。詳細は、コレクションの作成 を参照してください。
インデックスでの検索
インデックスが構築され、エンティティが挿入されると、インデックス上で類似検索を実行できます。
search_params = {
"params": {
"ef": 10, # Number of neighbors to consider during the search
}
}
res = MilvusClient.search(
collection_name="your_collection_name", # Collection name
data=[[0.1, 0.2, 0.3, 0.4, 0.5]], # Query vector
limit=10, # TopK results to return
search_params=search_params
)
この構成では
params:インデックスで検索するための追加構成オプション。ef:検索時に考慮する近隣の数。
HNSWインデックスで利用可能な検索パラメータについては、インデックス固有の検索パラメータ を参照。
インデックスパラメータ
このセクションでは、インデックスを構築し、インデックス上で検索を実行する際に使用するパラメータの概要を説明します。
インデックス構築パラメータ
以下の表は、params でインデックスを構築する際に設定できるパラメータの一覧です。
| パラメータ | 説明 | 値の範囲 | チューニングの提案 |
|---|---|---|---|
M | 各ノードがグラフ内で持つことのできる接続（またはエッジ）の最大数。 このパラメータはインデックス構築と検索の両方に直接影響する。 | 型：整数 範囲[2, 2048] デフォルト値: 30 (ノードあたり最大 30 の送信エッジと 30 の受信エッジ) | M を大きくすると一般的に精度が高くなるが、メモリ・オーバーヘッドが増加し、インデックス構築と検索の両方が遅くなる。高次元のデータセットや高い再現性が重要な場合は、 M を増やすことを検討する。メモリ使用量と検索速度を重視する場合は、 M を減らすことを検討する。ほとんどの場合、この範囲内の値を設定することを推奨する：[5, 100]. |
efConstruction | インデックス構築時に接続を考慮する近隣候補の数。 各新要素に対してより多くの候補が評価されますが、 実際に確立される接続の最大数は M によって制限されます。 | 型：整数 範囲: [1, int_max]：[1,int_max] です。 デフォルト値： 360 | efConstruction を大きくすると、より多くの潜在的なコネクションが探索されるため、通常より正確なインデックスが作成される。しかし、これはインデックス作成時間の延長と、作成中のメモリ使用量の増加にもつながります。特にインデックス作成時間がそれほど重要でないシナリオでは、 efConstruction を増やして精度を向上させることを検討する。リ ソ ース制約が懸念 さ れ る 場合には、 efConstruction を減らして イ ンデ ッ ク ス作成を高速化す る こ と を検討 し て く だ さ い。ほとんどの場合、この範囲内の値を設定することを推奨します：[50, 500]. |
インデックス固有の検索パラメータ
次の表は、インデックスを検索する際にsearch_params.params で設定できるパラメータの一覧です。
| パラメータ | 説明 | 値の範囲 | チューニングサジェスチョン |
|---|---|---|---|
ef | 最近傍検索時の検索の幅を制御する。どれだけのノードが最近傍候補として訪問され、評価されるかを決定します。このパラメータは検索プロセスのみに影響し、グラフの最下層にのみ適用される。 | 型を指定します：整数 範囲: [1, int_max[1,int_max］ デフォルト値:limit(TopK nearest neighbors to return) | ef を大きくすると、より多くの近傍候補が考慮されるため、一般的に検索精度が高くなります。しかし、これは検索時間を増加させます。高い想起率を達成することが重要であり、検索速度があまり気にならない場合は、 ef を増やすことを検討する。特に精度が多少低下しても構わないようなシナリオでは、 ef を減らして、より高速な検索を優先させることを検討してください。ほとんどの場合、この範囲内の値を設定することをお勧めします：[K, 10K]。 |