インメモリインデックス
このトピックでは、Milvusがサポートする様々なタイプのインメモリインデックス、それぞれのインデックスが最適なシナリオ、および、より良い検索パフォーマンスを達成するためにユーザが設定できるパラメータについて説明します。オンディスクインデックスについては、オンディスクインデックスを参照してください。
インデックスはデータを効率的に整理するプロセスであり、大規模なデータセットに対する時間のかかるクエリを劇的に高速化することで、類似検索を有用なものにする上で大きな役割を果たします。
クエリー性能を向上させるために、各ベクトルフィールドにインデックスタイプを指定することができます。
ANNSベクトルインデックス
Milvusがサポートするベクトルインデックスタイプのほとんどは、近似最近傍探索(ANNS)アルゴリズムを使用しています。通常非常に時間のかかる正確な検索と比較して、ANNSの核となる考え方は、もはや最も正確な結果を返すことに限定されず、ターゲットの近傍のみを検索することです。ANNSは、許容範囲内の精度を犠牲にすることで、検索効率を向上させる。
実装方法によって、ANNSベクトルインデックスは4つのタイプに分類される：ツリーベース、グラフベース、ハッシュベース、量子化ベースである。
Milvusでサポートされるインデックス
Milvusは様々なインデックスタイプをサポートしており、それらは扱うベクトル埋め込みタイプによって分類されます：浮動小数点埋め込み（浮動小数点ベクトルまたは密ベクトルとも呼ばれる）、バイナリ埋め込み（バイナリベクトルとも呼ばれる）、スパース埋め込み（スパースベクトルとも呼ばれる）。
浮動小数点埋込みのインデックス
128次元の浮動小数点埋め込み（ベクトル）の場合、浮動小数点埋め込みが占有するストレージは128 * floatのサイズ = 512バイトです。また、浮動小数点埋め込みに使われる距離指標は、ユークリッド距離 (L2) と内積 (IP) です。
これらのタイプのインデックスには、CPUベースのANN検索用にFLAT,IVF_FLAT,IVF_PQ,IVF_SQ8,HNSW,SCANN がある。
バイナリ埋め込み用インデックス
128次元のバイナリ埋め込みでは、128 / 8 = 16バイトのストレージを占有する。そして、バイナリ埋め込みに使われる距離メトリックスはJACCARD とHAMMING です。
このタイプのインデックスには、BIN_FLAT とBIN_IVF_FLAT がある。
スパース埋め込みインデックス
スパース埋め込みでサポートされる距離メトリックは，IP のみです．
このタイプのインデックスには，SPARSE_INVERTED_INDEX とSPARSE_WAND があります．
| サポートされるインデックス | 分類 | シナリオ |
|---|---|---|
| フラット | 該当なし |
|
| IVF_FLAT | 量子化ベースのインデックス |
|
| IVF_SQ8 | 量子化ベースのインデックス |
|
| IVF_PQ | 量子化ベースのインデックス |
|
| HNSW | グラフベースのインデックス |
|
| SCANN | 量子化ベースのインデックス |
|
| 対応インデックス | 分類 | シナリオ |
|---|---|---|
| BIN_FLAT | 量子化ベースのインデックス |
|
| BIN_IVF_FLAT | 量子化ベースのインデックス |
|
| 対応インデックス | 分類 | シナリオ |
|---|---|---|
| sparse_inverted_index | 転置インデックス |
|
| スパースワンド | 転置インデックス |
|
フラット
完璧な精度が要求され、比較的小さな（百万規模の）データセットに依存するベクトル類似検索アプリケーションには、FLATインデックスが良い選択である。FLATはベクトルを圧縮せず、正確な検索結果を保証できる唯一のインデックスである。FLATの結果は、再現率が100%に満たない他のインデックスが生成した結果の比較対象としても使用できる。
FLATが正確なのは、検索に網羅的なアプローチをとるからである。つまり、クエリごとに、ターゲット入力がデータセット内のすべてのベクトル集合と比較される。このため、FLATは我々のリストの中で最も遅いインデックスであり、膨大なベクトルデータのクエリには適していない。MilvusではFLATインデックスに必要なパラメータはなく、これを使用することでデータ学習も不要である。
検索パラメータ
パラメータ 説明 範囲 metric_type[オプション] 選択された距離メトリック。 サポートされるメトリックを参照。
IVF_FLAT
IVF_FLAT はベクトルデータをnlist クラスタ単位に分割し、ターゲット入力ベクトルと各クラスタの中心との距離を比較します。システムがクエリに設定したクラスタ数 (nprobe) に応じて、ターゲット入力と最も類似したクラスタ内のベクトルとの比較のみに基づいて類似性検索結果が返され、クエリ時間が大幅に短縮されます。
nprobe を調整することで、シナリオに応じた精度と速度の理想的なバランスを見つけることができる。IVF_FLATの性能テストの結果は、ターゲット入力ベクトルの数(nq)と検索するクラスタの数(nprobe)の両方が増加すると、クエリ時間が急激に増加することを示しています。
IVF_FLATは最も基本的なIVFインデックスであり、各ユニットに格納される符号化データは元データと一致する。
インデックス構築パラメータ
パラメータ 説明 範囲 デフォルト値 nlistクラスタユニット数 [1, 65536] 128 検索パラメータ
共通検索
パラメータ 説明 範囲 デフォルト値 nprobe検索するユニットの数 [1, nlist］ 8 範囲検索
パラメータ パラメータ 範囲 デフォルト値 max_empty_result_buckets
これは範囲検索パラメータであり、連続した空のバケツの数が指定された値に達する間、検索プロセスを終了する。
この値を大きくすると、検索時間が長くなる代償として、リコール率を向上させることができる。[1, 65535] 2
IVF_SQ8
IVF_FLATは圧縮を行わないため、生成されるインデックスファイルのサイズは、インデックス付けされていない元の生のベクトルデータとほぼ同じです。例えば、元の 1B SIFT データセットが 476 GB の場合、IVF_FLAT のインデックスファイルは若干小さくなります（~470 GB）。すべてのインデックスファイルをメモリにロードすると、470GBのストレージを消費します。
ディスク、CPU、GPU のメモリリソースが限られている場合は、IVF_FLAT よりも IVF_SQ8 の方が適しています。このインデックスタイプは、スカラー量子化（SQ）を実行することで、各 FLOAT（4バイト）を UINT8（1バイト）に変換することができます。これにより、ディスク、CPU、GPUのメモリ消費量が70～75%削減される。1B SIFTデータセットの場合、IVF_SQ8インデックスファイルに必要なストレージはわずか140GBです。
インデックス作成パラメータ
パラメータ 説明 範囲 nlistクラスタユニット数 [1, 65536] 検索パラメータ
共通検索
パラメータ 説明 範囲 デフォルト値 nprobe検索するユニットの数 [1, nlist］ 8 範囲検索
パラメータ パラメータ 範囲 デフォルト値 max_empty_result_buckets
これは範囲検索パラメータであり、連続した空のバケツの数が指定された値に達する間、検索プロセスを終了する。
この値を大きくすると、検索時間が長くなる代償として、リコール率を向上させることができる。[1, 65535] 2
IVF_PQ
PQ (Product Quantization) は、元の高次元ベクトル空間を、 低次元ベクトル空間のデカルト積に一様に分解し、分解された低次元ベクトル空間を量子化する。積量子化により、対象ベクトルと全ユニットの中心との距離を計算する代わりに、対象ベクトルと各低次元空間のクラスタリング中心との距離を計算することが可能となり、アルゴリズムの時間的複雑性と空間的複雑性を大幅に削減することができる。m
IVF_PQ は，ベクトルの積を量子化する前にIVFインデックスクラスタリングを行います．そのインデックスファイルはIVF_SQ8よりもさらに小さいが、ベクトル探索時の精度が低下する。
インデックス作成パラメータと検索パラメータはMilvus分布によって異なります。まずはMilvusディストリビューションを選択してください。
インデックス作成パラメータ
パラメータ 説明 範囲 nlistクラスタユニット数 [1, 65536] m積量子化の因子数 dim mod m == 0nbits[オプション] 各低次元ベクトルが格納されるビット数。 [1, 64] (デフォルトは8) 検索パラメータ
共通検索
パラメータ 説明 範囲 デフォルト値 nprobe検索するユニットの数 [1, nlist］ 8 範囲検索
パラメータ パラメータ 範囲 デフォルト値 max_empty_result_buckets
これは範囲検索パラメータであり、連続した空のバケツの数が指定された値に達する間、検索プロセスを終了する。
この値を大きくすると、検索時間が長くなる代償として、リコール率を向上させることができる。[1, 65535] 2
SCANN
ScaNN (Scalable Nearest Neighbors) は、ベクトルクラスタリングと積量子化という点でIVF_PQに似ています。両者の違いは、積量子化の実装の詳細と、効率的な計算のためのSIMD（Single-Instruction / Multi-data）の使用にあります。
インデックス構築パラメータ
パラメータ 説明 範囲 nlistクラスタユニット数 [1, 65536] with_raw_data生データをインデックスに含めるかどうか Trueまたは 。デフォルトは 。FalseTrueIVF_PQ とは異なり、パフォーマンスを最適化するために、デフォルト値は
mとnbitsに適用されます。検索パラメータ
共通検索
パラメータ 説明 範囲 デフォルト値 nprobe検索するユニットの数 [1, nlist］ reorder_kクエリーするユニット候補の数 [ top_k, ∞ ]を指定する。top_k範囲検索
パラメータ パラメータ 範囲 デフォルト値 max_empty_result_buckets
これは範囲検索パラメータであり、連続した空のバケツの数が指定された値に達する間、検索プロセスを終了する。
この値を大きくすると、検索時間が長くなる代償として、リコール率を向上させることができる。[1, 65535] 2
HNSW
HNSW（Hierarchical Navigable Small World Graph）は、グラフベースのインデックス作成アルゴリズムである。HNSWは、ある規則に従って、画像に対して多層のナビゲーション構造を構築する。この構造では、上層ほど疎でノード間の距離が遠く、下層ほど密でノード間の距離が近い。探索は最上層から開始し、この層でターゲットに最も近いノードを見つけ、次の層に入って別の探索を開始する。何度も繰り返すうちに、目標位置に素早く近づくことができる。
パフォーマンスを向上させるために、HNSWはグラフの各レイヤー上のノードの最大次数をM に制限している。さらに、efConstruction （インデックス構築時）またはef （ターゲット検索時）を使って検索範囲を指定することができる。
インデックス構築パラメータ
パラメータ 説明 範囲 MM は、グラフ内の発信接続の最大数を定義します。Mが大きいほど、固定ef/efConstructionでの精度/run_timeが高くなる。 [2, 2048] efConstructionef_construction は、インデックス検索速度と構築速度のトレードオフを制御する。efConstructionパラメータを大きくするとインデックスの品質が向上するが、インデックス作成時間が長くなる傾向がある。 [1, int_max］ 検索パラメータ
パラメータ 説明 範囲 ef検索時間と精度のトレードオフを制御するパラメータ。 efが高いほど検索精度は高くなるが、検索時間は遅くなる。[ top_k, int_max］
BIN_FLAT
このインデックスはFLATと全く同じであるが、バイナリ埋め込みにのみ使用できる。
完璧な精度が要求され、比較的小さな（百万規模の）データセットに依存するベクトル類似検索のアプリケーションには、BIN_FLATインデックスが良い選択です。BIN_FLAT はベクトルを圧縮せず、正確な検索結果を保証できる唯一のインデックスです。BIN_FLATの結果は、再現率が100%に満たない他のインデックスが作成した結果の比較対象としても使用できます。
BIN_FLATが正確なのは、検索に網羅的なアプローチを取るからである。つまり、クエリごとに、ターゲット入力がデータセットのベクトルと比較される。このため、BIN_FLATは我々のリストの中で最も遅いインデックスであり、膨大なベクトルデータのクエリには適していない。MilvusにはBIN_FLATインデックス用のパラメータはなく、これを使用することでデータトレーニングや追加ストレージを必要としない。
検索パラメータ
パラメータ 説明 範囲 metric_type[オプション] 選択された距離メトリック。 サポートされるメトリックを参照してください。
BIN_IVF_FLAT
このインデックスは IVF_FLAT と全く同じですが、バイナリ埋め込みにのみ使用できます。
BIN_IVF_FLAT はベクトルデータをnlist クラスタ単位に分割し、ターゲット入力ベクトルと各クラスタの中心との距離を比較します。システムがクエリに設定するクラスタ数（nprobe ）に応じて、ターゲット入力と最も類似したクラスタ（複数可）内のベクトル間の比較に基づく類似性検索結果が返され、クエリ時間が大幅に短縮されます。
nprobe を調整することで、精度と速度の理想的なバランスを見つけることができます。クエリ時間は、ターゲット入力ベクトルの数 (nq) と検索するクラスタの数 (nprobe) の両方が増加するにつれて急激に増加します。
BIN_IVF_FLATは最も基本的なBIN_IVFインデックスであり、各ユニットに格納されるエンコードされたデータは元のデータと一致する。
インデックス構築パラメータ
パラメータ 説明 範囲 nlistクラスタユニット数 [1, 65536] 検索パラメータ
共通検索
パラメータ 説明 範囲 デフォルト値 nprobe検索するユニットの数 [1, nlist］ 8 範囲検索
パラメータ パラメータ 範囲 デフォルト値 max_empty_result_buckets
これは範囲検索パラメータであり、連続した空のバケツの数が指定された値に達する間、検索プロセスを終了する。
この値を大きくすると、検索時間が長くなる代償として、リコール率を向上させることができる。[1, 65535] 2
sparse_inverted_index
各次元は、その次元で0でない値を持つベクトルのリストを保持する。検索中、milvusはクエリベクトルの各次元を繰り返し、その次元で非ゼロ値を持つベクトルのスコアを計算する。
インデックス構築パラメータ
パラメータ 説明 範囲 drop_ratio_buildインデックス作成時に除外される小さなベクトル値の割合。このオプションを使用すると、インデックスを作成する際に小さな値を無視することで、効率と精度のトレードオフを行い、インデックス作成プロセスを微調整することができます。 [0, 1] 検索パラメータ
パラメータ 説明 範囲 drop_ratio_search検索処理中に除外する小さなベクトル値の割合。このオプションは、クエリベクトル内の最小値を無視する割合を指定することで、検索処理を微調整することができます。検索精度とパフォーマンスのバランスをとるのに役立ちます。 drop_ratio_searchに設定する値が小さければ小さいほど、これらの小さな値が最終的なスコアに与える影響は小さくなります。いくつかの小さな値を無視することで、精度への影響を最小限に抑えながら検索パフォーマンスを向上させることができる。[0, 1]
SPARSE_WAND
このインデックスは、SPARSE_INVERTED_INDEX と類似しているが、Weak-ANDアルゴリズムを利用することで、検索プロセスにおけるフル IP 距離評価の回数をさらに減らしている。
我々のテストに基づくと、SPARSE_WAND は一般的にスピードの点で他の方法を上回る。しかし、その性能はベクトルの密度が高くなるにつれて急激に悪化する可能性がある。この問題に対処するため、ゼロでないdrop_ratio_search を導入することで、精度の低下を最小限に抑えつつ、性能を大幅に向上させることができます。詳細はスパースベクトルを参照。
インデックス構築パラメータ
パラメータ 説明 範囲 drop_ratio_buildインデックス作成時に除外する小さなベクトル値の割合。このオプションを使用すると、インデックスを作成する際に小さな値を除外することで、効率と精度のトレードオフを行い、インデックス作成処理を微調整することができます。 [0, 1] 検索パラメータ
パラメータ 説明 範囲 drop_ratio_search検索処理中に除外する小さなベクトル値の割合。このオプションは、クエリベクトル内の最小値を無視する割合を指定することで、検索処理を微調整することができます。検索精度とパフォーマンスのバランスをとるのに役立ちます。 drop_ratio_searchに設定する値が小さければ小さいほど、これらの小さな値が最終的なスコアに与える影響は小さくなります。いくつかの小さな値を無視することで、精度への影響を最小限に抑えながら検索性能を向上させることができる。[0, 1]
よくある質問
FLATインデックスとIVF_FLATインデックスの違いは何ですか？
IVF_FLAT インデックスはベクトル空間をnlist クラスタに分割します。nlist のデフォルト値を16384のままにしておくと、Milvusはターゲットベクトルと16384クラスタすべての中心との距離を比較し、nprobe 最も近いクラスタを取得します。次に、Milvusはターゲットベクトルと選択されたクラスタのベクトル間の距離を比較し、最も近いベクトルを得ます。IVF_FLATと異なり、FLATはターゲットベクトルと各ベクトル間の距離を直接比較します。
そのため、ベクトルの総数がnlist 程度であれば、IVF_FLAT と FLAT は、必要な計算方法や探索性能にほとんど差がありません。しかし、ベクトル数がnlist の2倍、3倍、n倍になるにつれて、IVF_FLATインデックスがますます大きな利点を示し始めます。
詳しくはMilvusにおけるインデックスの選び方を参照してください。
次のステップ
- Milvusでサポートされている類似度指標について詳しく知る。
