IVF_PQ

IVF_PQインデックスは、高次元空間における近似最近傍探索のための量子化ベースのインデックス作成アルゴリズムである。グラフベースの手法ほど高速ではないが、IVF_PQは多くの場合メモリ使用量を大幅に削減できるため、大規模なデータセットに対して実用的な選択肢となる。

概要

IVF_PQは Inverted File with Product Quantizationの略で、効率的なベクトル検索と検索のためにインデックス作成と圧縮を組み合わせたハイブリッドアプローチである。IVF_PQは2つのコアコンポーネントを活用しています：反転ファイル(IVF)と積量子化(PQ)です。

IVF

IVFは、本の索引を作るようなものです。すべてのページ（私たちの場合はすべてのベクトル）をスキャンする代わりに、インデックスで特定のキーワード（クラスタ）を検索し、関連するページ（ベクトル）をすばやく見つけます。このシナリオでは、ベクターはクラスターにグループ化され、アルゴリズムはクエリーベクターに近いいくつかのクラスター内を検索します。

以下がその仕組みだ：

1. クラスタリング：ベクトルデータセットは、k-meansのようなクラスタリングアルゴリズムを使用して、指定された数のクラスタに分割されます。各クラスタにはセントロイド（クラスタを代表するベクトル）があります。
2. 割り当て：各ベクトルは、セントロイドが最も近いクラスタに割り当てられます。
3. 転置インデックス：各クラスタのセントロイドを、そのクラスタに割り当てられたベクトルのリストにマッピングするインデックスが作成されます。
4. 検索：最近傍を検索する場合、検索アルゴリズムはクエリベクトルとクラスタ重心を比較し、最も有望なクラスタを選択します。そして、その選択されたクラスタ内のベクトルに検索が絞り込まれます。

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

PQ

Product Quantization (PQ)は、高次元ベクトルの圧縮手法であり、高速な類似性検索を可能にすると同時に、ストレージ要件を大幅に削減します。

PQプロセスには以下の主要な段階があります：

PQプロセス-1

1. 次元分解：このアルゴリズムは、各高次元ベクトルをm 等しい大きさの部分ベクトルに分解することから始まる。この分解により、元のD次元空間はm 分割された部分空間に変換され、各下部空間はD/m次元を含む。パラメータm は分解の粒度を制御し、圧縮率に直接影響する。
2. 部分空間コードブック生成：それぞれの部分空間内で、アルゴリズムはk-meansクラスタリングを適用し、代表ベクトル（セントロイド）の集合を学習する。これらのセントロイドは集合的に、その部分空間のコードブックを形成する。各コードブックにおけるセントロイドの数は、パラメータnbits によって決定される。例えば、nbits = 8 の場合、各コードブックは256個のセントロイドを含む。各セントロイドには、nbits ビットの一意なインデックスが割り当てられる。
3. ベクトル 量子化：元のベクトル内の各サブベクトルに対して、PQは対応する部分空間内で、特定のメトリックタイプを使用して、その最も近いセントロイドを特定する。このプロセスは、各サブベクトルをコードブック内の最も近い代表ベクトルに効果的にマッピングする。完全な部分ベクトル座標を格納する代わりに、マッチしたセントロイドのインデックスのみが保持される。
4. 圧縮表現：最終的な圧縮表現は、各サブスペースから1つずつ、m 、PQコードと総称されるインデックスで構成される。このエンコーディングにより、D×32ビット（32ビット浮動小数点数を仮定）からm×nビットへとストレージ要件が削減され、ベクトル距離の近似能力を維持しながら大幅な圧縮が達成されます。

パラメータのチューニングと最適化の詳細については、Index paramsを参照してください。

PQによる距離計算

クエリーベクターで類似検索を行う場合、PQは以下のステップで効率的な距離計算を可能にする：

1. クエリの前処理

   1. クエリ・ベクトルは、元のPQ分解構造と一致するように、m サブ・ベクトルに分解される。
   2. 各クエリーサブベクターとそれに対応するコードブック（2^nbitsのセントロイドを含む）に対して、すべてのセントロイドへの距離を計算し、格納する。
   3. これにより、m ルックアップテーブルが生成され、各テーブルには2^nbitsの距離が格納される。

2. 距離近似

   PQコードで表現されたデータベースベクトルに対して、クエリベクトルとの近似距離は以下のように計算される：

   1. m の各サブベクトルについて、対応するルックアップテーブルから、格納されているセントロイドインデックスを使用して、事前に計算された距離を取得する。
   2. これらのm 距離を合計して、特定のメトリックタイプ（ユークリッド距離など）に基づく近似距離を求める。

pq-process-1

IVF + PQ

IVF_PQインデックスは、IVFと PQの長所を組み合わせて検索を高速化する。このプロセスは2つのステップで動作する：

1. IVFによる粗いフィルタリング： IVFはベクトル空間をクラスタに分割し、検索範囲を狭める。データセット全体を評価する代わりに、このアルゴリズムはクエリーベクトルに最も近いクラスターのみに焦点を当てる。
2. PQによるきめ細かな比較：選択されたクラスタ内で、PQは圧縮・量子化されたベクトル表現を用いて近似距離を高速に計算する。

IVF_PQインデックスの性能は、IVFとPQの両アルゴリズムを制御するパラメータに大きく影響される。与えられたデータセットとアプリケーションに最適な結果を得るためには、これらのパラメータを調整することが極めて重要です。これらのパラメータの詳細と調整方法については、Index paramsを参照してください。

インデックスの構築

Milvusでベクトル場にIVF_PQ インデックスを構築するには、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_PQ", # 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": 4, # Number of sub-vectors to split eahc vector into
    } # Index building params
)

この設定では

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

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

• params:インデックスを構築するための追加設定オプション。

  • m:ベクトルを分割するサブベクトルの数。

  IVF_PQ インデックスで使用可能な構築パラメータについては、インデックス構築パラメータを参照してください。

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

インデックスでの検索

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

search_params = {
    "params": {
        "nprobe": 10, # Number of clusters to 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=3,  # TopK results to return
    search_params=search_params
)

この構成では

• params:インデックスで検索するための追加構成オプション。

  • nprobe:検索するクラスタの数。

  IVF_PQ インデックスで利用可能な検索パラメータについては、インデックス固有の検索パラメータを参照してください。

インデックスパラメータ

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

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

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

	パラメータ	説明	値の範囲	チューニングの提案
IVF	nlist	インデックス構築時にk-meansアルゴリズムを使用して作成するクラスタの数。	型：整数 範囲[1, 65536] デフォルト値：128	より大きなnlist 値は、より洗練されたクラスタを作成することでリコールを向上させるが、インデックス構築時間を増加させる。データセットサイズと利用可能なリソースに基づいて最適化する。 ほとんどの場合、この範囲内の値を設定することを推奨する：[32, 4096].
PQ	m	量子化処理時に各高次元ベクトルを分割するサブベクトルの数（量子化に使用）。	型：整数 範囲： [1, 65536[1, 65536] デフォルト値：なし	m の値を大きくすると精度が向上するが、計算の複雑さとメモリ使用量も増加する。 m は、適切な分解を保証するために、ベクトル次元(D) の約数でなければなりません。一般的に推奨される値はm = D/2 です。 ほとんどの場合、この範囲内の値を設定することをお勧めします：[D/8, D]。
	nbits	各サブベクトルの重心インデックスを圧縮形式で表現するためのビット数。各コードブックは2^nビットのセントロイドを含む。例えば、nbits が 8 に設定されている場合、各サブベクトルは 8 ビットのセントロイドのインデックスで表現される。これにより、そのサブベクトルのコードブックには、2^8 (256) 個のセントロイドが含まれることになる。	タイプ整数 範囲： [1, 64[1, 64] デフォルト値：8	nbits の値を大きくすると、コードブックを大きくすることができ、元のベクトルをより正確に表現できる可能性がある。しかし、これは各インデックスを格納するためにより多くのビットを使用することを意味し、結果として圧縮率が低下します。 ほとんどの場合、この範囲内の値を設定することをお勧めします：[1, 16].

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

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

	パラメータ	説明	値の範囲	チューニングサジェスチョン
IVF	nprobe	候補を検索するクラスタの数。	型：整数 範囲[1,nlist］ デフォルト値：8	より高い値は、より多くのクラスタを検索することを可能にし、検索範囲を拡大することでリコールを向上させるが、その代償としてクエリの待ち時間が増加する。 速度と精度のバランスをとるために、nlist に比例してnprobe を設定します。 ほとんどの場合、この範囲内の値を設定することをお勧めします：[1, nlist]。