IVF+PQ（量子化による圧縮）

FAISS（Facebook AI Similarity Search）における「IVF+PQ（Inverted File + Product Quantization）」は、大規模なベクトル集合に対して高速かつ省メモリでの近似類似検索を実現するための重要なインデックス構造です。この手法は以下の2つの技術を組み合わせています：

---

1. IVF（Inverted File Index：反転ファイルインデックス）

概要

IVFは、まずすべてのベクトルを**クラスタリング（通常はk-means）して複数のクラスタ中心（セントロイド）**を作成し、各ベクトルを最も近いクラスタに割り当てて格納します。この構造により、検索時には全クラスタを対象とせず、近いクラスタのみを探索することで高速化します。

• クラスタ数（nlist）が多いほど検索の精度は上がるが速度は下がる。

• 検索時には近傍のクラスタ（例：nprobe個）を探索します。

---

2. PQ（Product Quantization：積量子化）

概要

PQは、各ベクトルを低ビットの圧縮表現に変換する手法です。元のベクトルを複数の部分ベクトルに分割し、それぞれの部分に対して量子化（クラスタリング）を行い、インデックス（符号）だけを保存します。

• メモリ消費が大幅に削減される。

• 近似検索が可能（厳密な検索ではない）。

---

IVF+PQ の仕組み（統合的視点）

1. インデックス作成時：

   • すべてのベクトルを nlist 個のクラスタに分割（IVF）。

   • 各クラスタ内のベクトルを m 個のサブベクトルに分割してPQを適用（PQ）。

   • 各ベクトルは、「クラスタID + PQ符号」で保存。

2. 検索時：

   • クエリベクトルをクラスタ中心に割り当て、nprobe 個の近傍クラスタを選択。

   • 各クラスタ内で、PQ符号を使って近似距離を計算し、最も近いベクトルを返す。

---

利点

• 高速検索：クラスタによる範囲限定で探索コストを大幅に削減。

• 省メモリ：PQによりベクトルデータを大幅に圧縮。

• スケーラブル：何百万〜何十億のベクトルにも適用可能。

---

パラメータの主な調整項目

---

実装例（Python）

python
import faiss

d = 128             # ベクトルの次元
nlist = 100         # IVFのクラスタ数
m = 8               # PQの分割数
nbits = 8           # 量子化ビット

quantizer = faiss.IndexFlatL2(d)  # IVF用のクラスタリングベース
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, nbits)

# 学習と追加
index.train(embedding_vectors)  # embedding_vectors: np.ndarray
index.add(embedding_vectors)

# 検索
index.nprobe = 10
D, I = index.search(query_vectors, k)  # k件の類似ベクトル

---

総括

IVF+PQは、大規模データに対する高速な近似類似検索を実現するために設計されたFAISSの中核的なインデックス手法です。特に、精度とメモリ使用量、検索速度のバランスを柔軟に調整できる点で、実務上極めて有用です。特に数千万〜数億のベクトルを扱うアプリケーション（レコメンド、検索エンジン、画像検索など）で効果を発揮します。