IVF_RABITQCompatible with Milvus 2.6.x

IVF_RABITQインデックスは、FP32 ベクトルをバイナリ表現に量子化するバイナリ量子化ベースのインデックス作成アルゴリズムである。このインデックスは、比較的良好な想起率を維持しながら、1対32の圧縮率という優れた保存効率を提供します。また、ストレージを追加する代わりに、より高い想起率を実現するための絞り込み機能をオプションでサポートしており、メモリ制約のあるシナリオにおいて、IVF_SQ8や IVF_FLATに代わる汎用性の高いインデックスとなっています。

概要

IVF_RABITQは Inverted File with RaBitQ quantizationの略で、効率的なベクトル探索と保存のための2つの強力な手法を組み合わせたものです。

IVF

インバーテッド・ファイル（IVF）は、k-meansクラスタリングを用いてベクトル空間を管理しやすい領域に整理します。各クラスタはセントロイドで表され、そのクラスタ内のベクトルの参照点として機能します。このクラスタリング手法により、アルゴリズムがクエリ処理中に最も関連性の高いクラスタのみに焦点を当てることができるため、検索空間が縮小されます。

IVFの技術的な詳細については、IVF_FLATを参照してください。

RaBitQ

RaBitQは、Jianyang GaoとCheng Longによる研究論文 "RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search "で紹介された、理論的保証のある最先端のバイナリ量子化手法です。

RaBitQはいくつかの革新的な概念を導入している：

角度情報エンコーディング：従来の空間エンコーディングとは異なり、RaBitQはベクトルの正規化を通じて角度情報をエンコードする。IVF_RABITQでは、データベクトルは最も近いIVF重心に対して正規化され、量子化プロセスの精度が向上します。

理論的基礎核となる距離近似式は以下の通りである：

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

ここで

• $ormathbf{o_r}$orはデータセットからのデータベクトルである。
• $qrmathbf{q_r}$qrはクエリベクトルである。
• $comathbf{c_o}$cois the nearest IVF centroid vector for$ormathbf{o_r}$or
• $C(\mathbf{o_r}, \mathbf{c_o})$C$(\mathbf{o}$r, co) および$C_1(\mathbf{o_r}, \mathbf{c_o})$C${}_{}(o$ r, c o) は事前に計算された定数である。
• $o~tilde{mathbf{o}}$ ~ はインデックスに格納された量子化バイナリベクトルである。
• $co⟩langle$\$rangle$ o ~$,$q${}_{}-$ c${}_{}⟩は$ドット積演算を表す。

計算効率：$o~tilde{mathbf{o}}$ ~ の2進数の性質により、距離計算が非常に高速になり、特に Intel Ice Lake+ または AMD Zen 4+ プロセッサの専用 AVX-512 VPOPCNTDQ 命令を持つ最新の CPU アーキテクチャの恩恵を受けています。

アルゴリズムの強化RaBitQは、FastScan アプローチや ランダム回転のような確立された技術と効果的に統合し、パフォーマンスを向上させます。

IVF + RaBitQ

IVF_RABITQインデックスは、IVFの効率的なクラスタリングとRaBitQの高度なバイナリ量子化を組み合わせたものです：

1. 粗いフィルタリング：IVFはベクトル空間をクラスタに分割し、最も関連性の高いクラスタ領域に焦点を当てることで検索範囲を大幅に縮小します。

2. バイナリ量子化：各クラスタ内で、RaBitQは理論的保証により本質的な距離関係を保持しながら、ベクトルをバイナリ表現に圧縮します。

3. オプションの洗練：有効化された場合、インデックスは高精度フォーマット（SQ6、SQ8、FP16、BF16、FP32）を用いて精緻化されたデータを追加格納する。

Milvusは以下のFAISSファクトリー文字列を使用してIVF_RABITQを実装しています：

• 絞り込みあり"RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• 絞り込みなし"RR({dim}),IVF{nlist},RaBitQ"

インデックスの構築

Milvusでベクトル場にIVF_RABITQ インデックスを構築するには、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="IVF_RABITQ", # 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={
        "nlist": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

この設定では

• index_type:構築するインデックスのタイプ。この例ではIVF_RABITQ とします。

• metric_type:ベクトル間の距離の計算方法。サポートされている値には、COSINE 、L2 、IP があります。詳細については、メトリック・タイプを参照してください。

• params:インデックスを構築するための追加設定オプション。詳細は「インデックス構築パラメータ」を参照。

インデックス・パラメータを構成したら、create_index() メソッドを直接使用するか、create_collection メソッドでインデックス・パラメータを渡してインデックスを作成できます。詳細は、コレクションの作成 を参照してください。

インデックスでの検索

インデックスが構築され、エンティティが挿入されると、インデックス上で類似検索を実行できます。

search_params = {
    "params": {
        "nprobe": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement magnification factor
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field", # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]], # Query vector
    limit=3, # TopK results to return
    search_params=search_params
)

この構成では

• params:インデックスで検索するための追加構成オプション。詳細については、インデックス固有の検索パラメータを参照してください。

インデックスパラメータ

このセクションでは、インデックスを構築し、インデックス上で検索を実行するために使用されるパラメータの概要を説明します。

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

次の表は、インデックスを構築する際にparams で設定可能なパラメータの一覧です。

	パラメータ	説明	値の範囲	チューニングの提案
IVF	nlist	インデックス構築時にk-meansアルゴリズムを使用して作成するクラスタの数。セントロイドで表される各クラスタには、ベクトルのリストが格納されます。このパラメータを増加させると、各クラスタ内のベクトル数が減少し、より小さく、より焦点を絞ったパーティションが作成されます。	タイプ整数 範囲: [1, 65536[1, 65536] デフォルト値：128	より大きなnlist 値は、より洗練されたクラスタを作成することでリコールを向上させるが、インデックス構築時間を増加させる。データセットサイズと利用可能なリソースに基づいて最適化する。ほとんどの場合、この範囲内の値を設定することを推奨する：[32, 4096].
RaBitQ	refine	refine処理を有効にし、refineされたデータを格納する。	タイプはブール値 範囲：[true,false]。 デフォルト値：false	0.9以上の想起率が必要な場合、true に設定。絞り込みを有効にすると精度は向上するが、ストレージ要件とインデックス構築時間が増加する。
	refine_type	refine が有効な場合に絞り込みに使われるデータ表現を定義する。	型：文字列 範囲：[SQ6,SQ8,FP16,BF16,FP32]。 デフォルト値：なし	リストされた値は、想起率の増加、QPSの減少、ストレージサイズの増加の順に表示される。SQ8 が出発点として推奨され、精度とリソース使用量の良いバランスを提供する。

インデックス固有の検索パラメータ

次の表は、search_params.params でインデックス検索時に設定できるパラメータの一覧です。

	パラメータ	説明	値の範囲	チューニングサジェスチョン
IVF	nprobe	候補を検索するクラスタ数。値を大きくすると、より多くのクラスタを検索できるようになり、検索範囲が広がることでリコールが向上しますが、その代償としてクエリの待ち時間が長くなります。	型：整数 範囲：[1,nlist］ デフォルト値：8	この値を大きくすると想起は向上するが、検索が遅くなる可能性がある。速度と精度のバランスをとるために、nlist に比例してnprobe を設定する。ほとんどの場合、この範囲内の値を設定することを推奨する：[1,nlist]。
RaBitQ	rbq_query_bits	クエリ・ベクトルのスカラー量子化を行うかどうかを設定する。0 に設定すると、クエリは量子化されずに使用されます。1, 8]内の値に設定された場合、クエリはnビットのスカラー量子化を用いて前処理される。	型：整数 範囲： [0, 8[0, 8] デフォルト値：0	デフォルト値0 は、最大想起率を提供するが、パフォーマンスは最も遅い。0 、8 、6 の値をテストすることを推奨する。これらの値は、6 が最速で、同様の想起率を提供するからである。より高い想起要求には、より小さな値を使用する。
	refine_k	リファイニングプロセスは、IVF_RABITQを使用して選択されたrefine_k 倍の候補プールから必要な数の最近傍を選択するために、より高品質な量子化を使用します。	型：Float 範囲： [1, float_max)[1,float_max) デフォルト値：1	refine_k の値を高くするとQPSは低下するが、想起率は上昇する。1 、テスト値2,3,4,5 で開始し、データセットに最適な QPS と想起率のトレードオフを見つける。