インメモリーインデックス

浮動小数点埋込みのインデックス

128次元の浮動小数点埋め込み（ベクトル）の場合、浮動小数点埋め込みが占有するストレージは128 * floatのサイズ = 512バイトです。また、浮動小数点埋め込みに使われる距離指標は、ユークリッド距離 (L2) と内積 (IP) です。

これらのタイプのインデックスには、CPUベースのANN検索用にFLAT,IVF_FLAT,IVF_PQ,IVF_SQ8,HNSW,HNSW_SQ,HNSW_PQ,HNSW_PRQ,SCANN がある。

FLAT

完全な精度が要求され、比較的小規模な（100万個規模の）データセットに依存する ベクトル類似検索アプリケーションには、FLATインデックスが適している。FLATはベクトルを圧縮せず、正確な検索結果を保証できる唯一のインデックスである。FLATの結果は、再現率が100%に満たない他のインデックスが生成した結果の比較対象としても使用できる。

FLATが正確なのは、検索に網羅的なアプローチをとるからである。つまり、クエリごとに、ターゲット入力がデータセット内のすべてのベクトル集合と比較される。このため、FLATは我々のリストの中で最も遅いインデックスであり、膨大なベクトルデータのクエリには適していない。MilvusではFLATインデックスに必要なパラメータはなく、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よりもさらに小さいが、ベクトル探索時の精度が低下する。

• インデックス作成パラメータ

  パラメータ	説明	範囲
  nlist	クラスタユニット数	[1, 65536]
  m	積量子化の因子数	dim mod m == 0
  nbits	[オプション] 各低次元ベクトルが格納されるビット数。	[1, 24] (デフォルトは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 またはFalse 。デフォルトはTrue 。

  IVF_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 （ターゲット検索時）を使って検索範囲を指定することができる。

• インデックス構築パラメータ

  パラメータ	説明	範囲	デフォルト値
  M	Mは、グラフ内の発信接続の最大数を定義する。M が大きいほど、固定 ef/efConstruction での精度/run_time が高くなる。	[2, 2048]	なし
  efConstruction	ef_construction はインデックス検索速度と構築速度のトレードオフを制御します。efConstructionパラメータを大きくするとインデックスの品質が向上しますが、インデックス作成時間が長くなる傾向があります。	[1, int_max］	なし

• 検索パラメータ

  パラメータ	説明	範囲	デフォルト値
  ef	検索時間と精度のトレードオフを制御するパラメータ。ef を高くすると、検索精度は高くなるが、検索時間は遅くなる。	[top_k, int_max］	なし

HNSW_SQ

スカラー量子化(SQ)は、浮動小数点データをその大きさに基づいて有限の値の集合に離散化するために使用される技法である。例えば、SQ6 は(2^6 = 64) 個の離散値への量子化を表し、各浮動小数点数は 6 ビットでエンコードされる。同様に、SQ8 はデータを (2^8 = 256) 個の離散値に量子化し、各浮動小数点数は 8 ビットで表されます。この量子化により、効率的な処理のためにデータの本質的な構造を保持しながら、メモリフットプリントを削減します。

SQと組み合わせることで、HNSW_SQは高いクエリーパーセカンド（QPS）性能を維持しながら、インデックスサイズと精度のトレードオフを制御できる。標準的なHNSWと比較すると、インデックス構築時間の増加はわずかである。

• インデックス構築パラメータ

  パラメータ	説明	範囲	デフォルト値
  M	Mは、グラフ内の発信接続の最大数を定義する。M が大きいほど、固定 ef/efConstruction での精度/run_time が高くなる。	[2, 2048]	なし
  efConstruction	ef_construction はインデックス検索速度と構築速度のトレードオフを制御します。efConstructionパラメータを大きくするとインデックスの品質が向上しますが、インデックス作成時間が長くなる傾向があります。	[1, int_max］	なし
  sq_type	スカラー量子化タイプ。	SQ6SQ8, 、BF16 FP16	SQ8
  refine	インデックス構築時に洗練されたデータを予約するかどうか。	true,false	false
  refine_type	リファインインデックスのデータ型。	SQ6 SQ8, , 、BF16 FP16 FP32	なし

• 検索パラメータ

  パラメータ	説明	範囲	デフォルト値
  ef	検索時間と精度のトレードオフを制御するパラメータ。ef を高くすると、検索精度は高くなるが、検索時間は遅くなる。	[top_k, int_max］	なし
  refine_k	kに対するrefineの倍率。	[1,float_max)	1

HNSW_PQ

PQ の基本的な考え方は，ベクトルをm 個の部分ベクトルに分割し，それぞれの部分ベクトルが kmeans に基づいて2^{nbits} のセントロイドを見つけ，それぞれの部分ベクトルがその近似部分ベクトルとして最も近いセントロイドを選択することである．そして、すべてのセントロイドを記録する。したがって、各サブベクトルはnbits 、長さdim の浮動ベクトルはm・nビットとして符号化できる。

PQと組み合わせることで、HNSW_PQはインデックスサイズと精度のトレードオフを制御できるが、同じ圧縮率ではHNSW_SQよりQPS値が低く、想起率が高い。HNSW_SQと比較すると、インデックス構築に時間がかかる。

• インデックス構築パラメータ

  パラメータ	説明	範囲	デフォルト値
  M	Mは、グラフ内の発信接続の最大数を定義する。M が大きいほど、固定 ef/efConstruction での精度/run_time が高くなる。	[2, 2048]	なし
  efConstruction	ef_construction はインデックス検索速度と構築速度のトレードオフを制御します。efConstructionパラメータを大きくするとインデックスの品質が向上しますが、インデックス作成時間が長くなる傾向があります。	[1, int_max］	なし
  m	ベクトルを分割するサブベクターグループの数。	[1, 65536]	32
  nbits	各グループのサブベクトルを量子化するビット数。	[1, 24]	8
  refine	インデックス構築時に洗練されたデータを予約するかどうか。	true,false	false
  refine_type	絞り込みインデックスのデータ型。	SQ6 SQ8, , 、BF16 FP16 FP32	なし

• 検索パラメータ

  パラメータ	説明	範囲	デフォルト値
  ef	検索時間と精度のトレードオフを制御するパラメータ。ef を高くすると、検索精度は高くなるが、検索時間は遅くなる。	[top_k, int_max］	なし
  refine_k	kに対するrefineの倍率。	[1,float_max)	1

HNSW_PRQ

PRQ は PQ に似ており、ベクトルをm グループに分割する。各サブベクトルはnbits として符号化される。pq 量子化が完了すると、ベクトルと pq 量子化されたベクトルとの残差を計算し、残差ベクトルに pq 量子化を適用する。合計nrq の完全な pq 量子化が実行されるため、長さdim の浮動ベクトルはm・nビット・nrqビットとして符号化されます。

積残差量子化器（PRQ）と組み合わせることで、HNSW_PRQはインデックスサイズと精度のトレードオフをさらに高く制御できる。HNSW_PRQは同じ圧縮率でHNSW_PQとほぼ同等のQPS値と高い再現率を持つ。HNSW_PQと比較すると、インデックス構築にかかる時間は数倍になる可能性がある。

• インデックス構築パラメータ

  パラメータ	説明	範囲	デフォルト値
  M	Mは、グラフ内の発信接続の最大数を定義する。M が大きいほど、固定 ef/efConstruction での精度/run_time が高くなる。	[2, 2048]	なし
  efConstruction	ef_construction はインデックス検索速度と構築速度のトレードオフを制御します。efConstructionパラメータを大きくするとインデックスの品質が向上しますが、インデックス作成時間が長くなる傾向があります。	[1, int_max］	なし
  m	ベクトルを分割するサブベクターグループの数。	[1, 65536]	32
  nbits	各グループのサブベクトルを量子化するビット数。	[1, 24]	8
  nrq	残余部分量子化器の数。	[1, 16]	2
  refine	インデックス構築時にリファインデータを予約するかどうか。	true,false	false
  refine_type	絞り込みインデックスのデータ型。	SQ6 SQ8, , 、BF16 FP16 FP32	なし

• 検索パラメータ

  パラメータ	説明	範囲	デフォルト値
  ef	検索時間と精度のトレードオフを制御するパラメータ。ef を高くすると、検索精度は高くなるが、検索時間は遅くなる。	[top_k, int_max］	なし
  refine_k	kに対するrefineの倍率。	[1,float_max)	1