1. 概要

Product Quantization(PQ)は、高次元ベクトルを複数の subvector に分割し、各部分空間を小さな codebook で量子化することで、1本のベクトルを短いコードに圧縮する nearest neighbor search の手法です。核心は、元のベクトルをすべて RAM に載せなくても、圧縮されたコード上で距離計算を近似し、大規模検索のメモリボトルネックを減らすことです。

大規模なベクトル検索は、推薦システム、画像検索、意味ベースの文書検索などで繰り返し現れる問題です。NSW や HNSW がこの問題にグラフ探索を速くする方向からアプローチするのに対し、PQ はベクトル自体を短いコードに圧縮し、距離計算を圧縮されたコード上で近似する方向からアプローチします。Product Quantization for Nearest Neighbor Search 論文(Jégou, Douze, Schmid, 2011)は、このアプローチを ANN 検索に体系的に適用した代表的な論文です。

論文をたどりながら、次の4つの問いを確認していきます。

• Vector quantization と Product Quantization の基本原理
• Hamming embedding 系の強みと、distinct distance の不足という限界
• Product Quantization が単一 quantizer のメモリ限界をどう回避するのか
• Inverted file structure を組み合わせた IVFADC が非 exhaustive 検索をどう実現するのか

2. 必須概念

2.1. Quantization

Quantization とは、連続的な値をあらかじめ定められた有限個の代表値のいずれかに変換する過程です。最も身近な例がデジタル写真です。カメラのセンサーは光の量を連続的な実数として受け取りますが、保存するときは 0〜255 の整数に変換します。1600万通りの可能な色を GIF の 256色パレットの中で最も近い色にマッピングするのも同じ原理です。

입력: 무한한 가능성 (연속적인 값)
       ↓ quantizer
출력: 유한한 k개 대표값 중 하나

ここで、quantization を実行する関数を quantizer、代表値の集合を codebook、codebook の各要素を codeword と呼びます。結果として、quantizer が行う仕事は2つの段階に分かれます。

1. 入力を受け取り、最も近い codeword のインデックスを決定する
2. そのインデックスから再び codeword の値を復元する

元の値をそのまま保存する代わりにインデックスだけを保存すれば、メモリが大幅に削減されます。codeword が256個なら、インデックスは 1 byte で十分です。この圧縮が*非可逆(lossy)*である理由は、元の正確な値を codeword という代表点に置き換えるからです。

扱うデータによって quantizer の種類が分かれます。

PQ(Product Quantization) が扱う vector quantization では、codeword はベクトル空間内の1点であり、データの cluster の中心という意味で使われるため centroid と呼びます。quantizer の品質は、元の値と codeword の間の距離の二乗の平均である MSE (Mean Squared Error) で測定します。

2.2. SIFT と GIST Descriptor

PQ 論文が実験で使用する2種類の画像 descriptor です。両者はデータ分布の特性が異なり、PQ の次元グルーピング戦略にも影響を与えます。(3.7 参照)

SIFT、GIST descriptor の説明

SIFT (Scale-Invariant Feature Transform) は local descriptor です。画像からキーポイント(コーナーやエッジのような特徴的な地点)を検出し、各キーポイントの周辺でグラディエントヒストグラムを集めた128次元ベクトルを作ります。画像1枚あたり数百〜数千個のベクトルが生成されます。回転やスケール変化に頑健である代わりに、インデックス対象のベクトル数は画像数の数百倍以上に膨らみます。

GIST は global descriptor です。画像全体を1つのベクトルに要約するため、画像1枚につき1個のベクトルになります。論文の実験で使われた GIST は、色チャネルごとの320次元ブロックを3つつなぎ合わせた960次元です。

両 descriptor とも orientation histogram をつなぎ合わせて作られた構造ですが、natural order(先頭から順に切り分けること)が意味の単位をうまくまとめてくれる度合いが異なります。SIFT は natural order がすでに空間的に隣接するセルをまとめているためグルーピングに鈍感である一方、GIST は natural order がやや恣意的で、どの次元をまとめるかが性能を大きく左右します。

2.3. Hamming Embedding

Hamming embedding は、高次元の実数ベクトルを短い binary code にマッピングする手法です。

マッピングされた2つのコード間の Hamming distance(互いに異なるビット数)で、元の空間の距離を近似します。Spectral Hashing(SH)、Hamming Embedding(HE) などが代表的な学習方法です。

長所は、コードが小さく(通常8バイト)、table lookup 8回で距離計算が終わるという点です。一方、本質的な限界は、b ビットのコードの distinct distance がわずか b+1 通りしかないことです。64ビットの signature は距離値を 0〜64 の整数65通りでしか表現できないため、数多くのベクトルペアが同じ距離を受け取り、ranking の精度が低下します。

Hamming distance の表現可能な通り数

有力なベンチマーク比較の baseline は Hamming 系のアルゴリズムです。Product Quantization は、短いコード + 高速な lookup という Hamming 系アルゴリズムの長所を受け継ぎながら、不足していた距離精度を補います。

2.4. Inverted File Structure

Inverted file structure は情報検索から借用したデータ構造で、データセットをあらかじめ分割し、各分割に属する項目のリストを保存します。本の索引が単語 → ページのリストになっているのと同じ構造です。検索時には全体ではなく少数の list だけをスキャンします。

ベクトル検索では、分割を作るために coarse quantizer $q_c$ という別の quantizer を使用します。$q_c$ は普通の k-means で学習され、centroid 数 $k'$ は通常 $10^3\sim 10^6$ です。$q_c$ が作った centroid 1つが inverted list 1つに対応します。

左は coarse centroid(★)が空間を Voronoi cell に分割した様子、右は各 cell のベクトルが inverted list として保存された様子。query は最も近い centroid の list 1つだけをスキャン

この論文では、product quantizer 1つだけではすべてのデータを毎回 scan しなければならないという限界を、inverted file で解決します。coarse quantizer でどの領域か(上位ビット)を決め、product quantizer でその中の residual(下位ビット)を圧縮する 2段階の階層構造が IVFADC です。

3. PQ 論文まとめ

3.1. 論文の概要

論文が登場した時点で、ANN 検索の分野には3つの流れがありました。

1. ツリーベースの検索: KD-tree やその変種で、低次元では速いものの、高次元では brute-force と変わらない worst-case の計算量を示します。FLANN はこの系統の自動チューニングライブラリです。re-ranking の段階で元のベクトルをメモリに保持していなければならないという点が、メモリ面での本質的な制約です。

2. LSH 系: E2LSH (Euclidean Locality-Sensitive Hashing) が代表的で、理論的な検索品質の保証はあるものの、元のベクトルをそのままメモリに保持していないと re-ranking ができず、メモリ使用量がむしろ元データより大きくなる問題があります。

3. Hamming embedding: 上の第2章で扱った binary code 系。メモリ・速度は優れていますが、distinct distance の数が少なく ranking 精度に限界があります。

3.1.1. メモリが第一の制約になる理由

論文が*「メモリ」を核心的な動機として掲げる理由は、ANN 検索の評価基準が (検索品質, 検索速度) だけでなく (検索品質, 検索速度, メモリ) の trade-off であるという認識にあります。データセットが数十億ベクトル*の規模に大きくなると、次のことが自然な要求になります。

• 元のベクトル全体を RAM に載せられない → ディスク I/O が検索速度を支配 → ベクトルを圧縮して RAM に載せる必要がある
• LSH や FLANN のように re-ranking のために元データを保管する方式は、この時点で破綻する
• ベクトル自体を短いコードに置き換え、コード上で距離を推定する方式が唯一の解法

この要求を受けて、論文は問題をこう絞り込みます。

短いコードでベクトルを圧縮しながらも、距離計算の精度と distinct distance の多様性の両方を確保できるのか?そしてコード自体だけでなく codebook もメモリに載らなければならないという制約の下で、それは可能なのか?

単一の k-means で $k = 2^{64}$ 個の centroid を学習すると、codebook 自体が $k \cdot D$ floats となり RAM に載りません。PQ が解こうとしているのは、まさにこの codebook のメモリ問題です。

3.1.2. なぜ他の quantizer ではなく PQ なのか

PQ 以前にも centroid 数を増やす試みはありました。

3つの代替案はいずれも、学習データ、時間、メモリという3つの問題を同時には解決できません。PQ はこの3つをまとめて扱う構造を提案し、論文はその位置づけを semi-structured quantizer と呼びます。

3.1.3. PQ の位置づけ: "semi-structured" quantizer

Quantizer は構造性によって3つの部類に分けられます。

PQ は、空間全体は k-means で自由に学習しつつ、その空間を m 個の subspace の積として強制する部分的な構造を持ちます。k-means の適応性と lattice の効率性の両方を手に入れることができます。

"To our knowledge, such a semi-structured quantizer has never been considered in any nearest neighbor search method."

Product quantizer 自体は情報理論では古くからある手法ですが、ANN 検索に適用したのはこの論文が初めてだと述べています。

3.1.4. Product Quantization の2つの長所

1つ目の長所は、distinct distance の多様性です。$b$ ビットの Hamming コードが距離値を $b+1$ 通りの整数でしか表現できないのに対し、PQ-ADC は LUT(Look-Up Table)に実数の距離が入るため、事実上連続的な距離値を作り出します。同じコード長で、はるかに正確な ranking が可能になります。

2つ目の長所は、expected squared distance を推定できることです。PQ は順位だけでなく、実際の距離値の推定値まで教えてくれます。この性質が必要な応用が2つあります。距離が ε 以内のすべてのベクトルを見つける ε-radius 検索には実際の距離値が必要で、SIFT マッチングで1位の距離と2位の距離の比率からマッチングの信頼性を判断する標準的な手法である Lowe's distance ratio criterion も、距離値そのものを要求します。

Hamming embedding は順位しか与えられず、こうした距離値を提供できません。PQ は追加コストなしで距離値も一緒に返します。

3.1.5. Hamming 陣営の速度面の強みも同等

Hamming embedding が人気だった理由は、table lookup を利用した非常に高速な距離計算です。ところが PQ-ADC も同じ回数の table lookup(8回の lookup + 7回の加算)で距離を計算します。

lookup のコストは同程度なのに距離情報ははるかに豊富であることが、論文が Hamming 系に対して掲げる比較優位です。

3.2. Vector Quantization

論文は vector quantization を形式的に定義するところから始まります。

Quantizer $q$ は、$D$ 次元の実数ベクトルを codebook の要素にマッピングする関数です。

• $c_i$ : centroid (論文の表現では reproduction value)
• $\mathcal{C}$ : サイズ $k$ の codebook
• $\mathcal{I}$ : インデックス集合

同じインデックスにマッピングされるベクトルの集合を Voronoi cell と呼びます。

$k$ 個の cell が $\mathbb{R}^D$ の partition を形成し、同じ cell に属するすべてのベクトルは同じ centroid $c_i$ に reconstruction されます。

quantizer の品質は、元の値と reconstruction の間の距離の二乗の平均で測定します。

3.2.1. Lloyd's optimality conditions

論文は、最適な quantizer が満たすべき2つの条件を明示します。

1. Nearest Neighbor Condition: $q(x) = \arg\min_{c_i \in \mathcal{C}} d(x, c_i)$ — 最も近い centroid にマッピング
2. Centroid Condition: $c_i = \mathbb{E}[X \mid X \in \mathcal{V}_i]$ — centroid は cell 内部の平均

PQ 論文は、k-means が2つの条件を(near-optimal に)満たすため、これを学習ツールとして使用します。

3.2.2. Cell distortion

cell ごとの distortion も定義します。cell $\mathcal{V}_i$ に限定した平均二乗誤差です。

全体の MSE は、cell ごとの distortion の確率による加重平均として表現されます。

3.2.3. メモリコスト

最後に、インデックス値を1つ保存するコストは $\lceil \log_2 k \rceil$ bits です。したがって $k$ を2の累乗にとることが byte アラインメントに効率的であり、PQ で $k^* = 256$ を標準として使う理由です(ちょうど 1 byte)。

3.3. Product Quantization

各 subquantizer $q_j$ はその subspace 専用の codebook $\mathcal{C}_j$ を持ち、全体の PQ codebook は Cartesian product として定義されます。

Product Quantization における Cartesian product の原理

各 subquantizer が $k^* = 256$ 個の centroid を持つ場合、全体の product quantizer が表現できる distinct centroid の数は、各 codebook のサイズの積になります。

同じ $2^{64}$ 個の centroid なのに、学習と保存にかかるコストはまったく異なります。

$m=8, k^*=256$ のとき、PQ の codebook はわずか $8 \times 256 \times 16 \times 4 = 128\text{KB}$ です。これが $2^{64}$ 個の centroid を暗黙的に表現する方法です。

3.3.1. データ保存コスト

codebook だけでなく、各ベクトルの表現方式もメモリに大きな影響を与えます。1億個の128次元 SIFT ベクトルを保存するとしましょう。

LSH や FLANN は re-ranking のために元データを保管しなければならないので、1行目に該当します。PQ はコード上で直接距離を推定するため、2行目で十分です。51GB と 800MB というこの差が、数十億ベクトルを単一マシンでインデックスすることを可能にしました。

「大きな codebook 1つ」の代わりに「小さな codebook 複数個の積」で同じ表現力を指数的に少ないリソースで獲得し、ベクトルまで短いコードに圧縮して RAM に載せます。

各 subquantizer は $k^*$ が小さいため、普通の Lloyd's algorithm で十分に学習できます。そして各ベクトルは、各 subquantizer のインデックス $m$ 個を集めた短いコードで表現されます。$m=8, k^*=256$ なら、1本のベクトルが 8バイトに圧縮されます。

Train_PQ(training_set, m, k*)
1   // training_set: n개의 D차원 벡터
2   for j = 1 to m:
3       // subspace j 학습 데이터: 모든 n개 벡터의 j번째 subvector
4       sub_data_j ← { u_j(y) : y ∈ training_set }
5       C_j ← k-means(sub_data_j, k*)   // k*개 centroid 학습
6
7   return (C_1, C_2, ..., C_m)

各 subspace の学習は互いに独立なので、m 個を並列に処理できます。

学習が終わると codebook $(C_1, \ldots, C_m)$ が作られ、これを内部状態として持つエンコード関数 $q_p$ を定義できます。

Encode_PQ(y: D차원 벡터, codebooks=(C_1, ..., C_m))   // 곧 q_p(y)
1   code ← empty array of length m
2   for j = 1 to m:
3       // u_j(y): y의 j번째 subvector (D/m차원)
4       // C_j에서 *가장 가까운 centroid의 인덱스* 찾기
5       code[j] ← argmin_{i=0..k*-1} ||u_j(y) - c_{j,i}||²
6
7   return code                          // m개 인덱스, 총 m byte

論文の表記 $q_p(y)$ は、この Encode_PQ 関数呼び出しの結果 — m byte code — を指します。つまり:

• Train_PQ: 学習関数。結果は codebook(centroid の座標群、一度だけ作る)
• $q_p$ = Encode_PQ: エンコード関数。codebook を読み取ってベクトル → code に変換(データごとに呼び出す)

PQ コードのエンコードアルゴリズムの図解

3.3.2. Product Quantization の2つの仮定

1. 各 subvector が同程度のエネルギーを持つ。 すべての subspace に同じ $k^*=256$ 個の centroid を均等に配分するため、分散が一方に激しく偏ると一部の subspace で解像度不足になります。解決策は quantization の前に random orthogonal matrix を掛けることですが、論文は隣接次元の correlation を保存することが優先だとして推奨していません。
2. Subspace が互いに直交する。 ベクトルを先頭から順に切り分けて subvector を作れば、基本座標軸に沿った分割なので自動的に保証されます。この仮定のおかげで、式 $\text{MSE}(q) = \sum_j \text{MSE}(q_j)$ によって MSE を分解できます。

3.4. 距離計算: SDC vs ADC

短いコードで距離をどう計算するのでしょうか?PQ 論文は2つの方法を提示します。

SDC と ADC。SDC は query も quantize し、ADC は query をそのままにして database ベクトルだけを quantize

Symmetric Distance Computation (SDC): query $x$ と database ベクトル $y$ の両方を quantize した後、2つの centroid 間の距離で近似します。

Asymmetric Distance Computation (ADC): query は quantize せず、database ベクトルだけを quantize します。

一見すると SDC の方が対称的で自然に見えますが、ADC の方がほぼ常に正確です。理由は単純です。ADC は query 側に quantization の誤差がないからです。

ADC のもう1つの長所は、LUT(Look-Up Table)を query ごとに一度だけ事前計算しておけばよいという点です。query が入ってくると、各 subquantizer $j$ ごとに次の表を事前計算します。

その後、database ベクトル1本の距離を計算するときは、そのベクトルのコード $(i_1, i_2, ..., i_m)$ を見て $m$ 回の table lookup と $m-1$ 回の加算だけで済みます。

Hamming distance の計算よりわずかに重い程度ですが、はるかに豊富な distinct distance を表現できます。

ADC_Distance(x: query, codes: database codes, codebooks)
1   // Step 1: query 쪽 LUT 미리 계산 (한 번만)
2   for j = 1 to m:
3       for i = 1 to k*:
4           LUT[j][i] ← d(u_j(x), c_{j,i})^2
5
6   // Step 2: 각 database 벡터 거리 계산 (n번 반복)
7   for each y_code in codes:
8       dist² ← 0
9       for j = 1 to m:
10          dist² ← dist² + LUT[j][y_code[j]]
11      record dist²
12
13  return top-k smallest distances

LUT を使った ADC の距離計算アルゴリズムの図解

全体のコストがほぼ同じなので、query 側のメモリを減らす必要がある特殊なケースでなければ、ADC を使うことが推奨されます。

3.5. 距離推定の統計的保証

PQ が単純なヒューリスティックではなく原理に基づいた近似であることを示す結果があります。ADC の距離推定誤差が quantizer の MSE によって統計的に bound されるというものです。

ここで $\text{MSDE}$(Mean Squared Distance Error)は推定距離と実際の距離の二乗誤差の平均であり、$\text{MSE}$ は quantizer 自体の平均二乗誤差です。

3.5.1. 証明のステップ

核心となる道具は三角不等式です。任意の3点 $x, y, q(y)$ に対して:

これは三角不等式の一形態ですが、直観的には*「ある1点を少し動かしたとき、他の点との距離の変化は動かした距離の分だけしか起こりえない」ということです。ADC は $\tilde{d}(x, y) = d(x, q(y))$ と定義されるため、左辺は私たちが知りたい距離推定誤差*です。

3点 x, y, q(y) に対する三角不等式。ADC の推定誤差(黒い辺 - 青い点線)は y の quantization error(赤い実線)以下に bound されます。

両辺を二乗すると:

$\text{MSDE}$ の定義に $(1)$ を代入し、$x$ についての積分を整理すると:

SDC の場合、query と database ベクトルの両方が quantize されるため三角不等式を2回適用する必要があり、結果は $\text{MSDE}_{\text{SDC}}(q) \leq 2 \cdot \text{MSE}(q)$ になります。ADC が SDC より正確である数学的な理由は、この bound の差にあります。

この bound が、学習と検索品質をつなぎます。

• k-means(Lloyd's algorithm)で quantizer を学習すれば MSE が小さくなる (3.2節の optimality conditions)
• MSE が小さければ MSDE も小さい(上の証明)
• MSDE が小さければ NN 検索の ranking が真の距離に近くなる

3.6. ADC の bias 分析と補正

3.5 節の bound は誤差の大きさを扱いましたが、誤差には方向もあります。ADC の推定距離は、平均的に実際の距離を過小評価(underestimate)します。

1000個の SIFT ベクトルに対する実際の距離 vs 推定距離(SDC/ADC)の散布図 (m=8, k*=256)

3.6.1. 補正公式の導出

この bias を正確に補正するために、y が cell $\mathcal{V}_i$ にあるという条件下での expected squared distance を直接計算します。

論文では $x - y$ を $c_i$ を経由する形に分解します。

3つの項を積分すると、cross term がちょうど 0 になります。Lloyd's の2番目の optimality condition のおかげです。

centroid が cell の平均という条件が cross term を正確に 0 にして、補正公式をきれいにしてくれます。残る2つの項は:

PQ に適用すると、各 subspace の cell distortion の和として分解されます。

各 $\xi_j(y)$ は学習時点で事前計算して LUT(Look-Up Table)に保存できるので、検索時点の追加コストは加算 $m$ 回だけです。

しかし実際には使いません

数学的には適用可能な補正なのですが、論文は NN 検索には補正なしで使えと勧めています。理由は bias-variance trade-off です。

補正 ADC は bias をほぼ 0 にしますが、分散が大きくなります(variance: 0.00146 → 0.00155、10000個の SIFT、m=8、k*=256)。NN 検索の ranking 精度には元の ADC の方が有利です。

• 元の ADC: bias = -0.044 (underestimate)、variance = 0.00146
• 補正 ADC: bias = +0.002 (ほぼ 0)、variance = 0.00155 (増加)

bias が減った代わりに分散が大きくなりました。そして NN 検索では、補正項 $\xi_j$ が元の推定値より大きい場合が頻繁に発生します。これはめったに割り当てられないインデックス(= distortion $\xi$ が大きい cell)のベクトルにペナルティを与える効果となり、本当に近いベクトルを取り逃がすことになります。

3.7. 次元グルーピングの影響

PQ の最も単純な実装は、ベクトルを先頭から順に切り分けて subvector を作ることです。ところが、この grouping の方式が性能に意外なほど大きな影響を与えます。

論文が SIFT と GIST で確認した結果は次のとおりです。

($recall@100$、$k^*=256$ 基準)

GIST descriptor では、natural order から structured order に変えるだけで recall@100 が 0.338 から 0.652 へと2倍になります。同じコード長で同じアルゴリズムを走らせたのに、次元のまとめ方ひとつでこれだけの差がつきました。

SIFT や GIST のような descriptor は orientation histogram をつなぎ合わせて作られた構造です。natural order で切ると1つの histogram の bin が複数の subvector に散らばる可能性があり、random order はさらにひどくなります。structured order は同じ意味を持つ dimension 群(例: 同じ orientation を表す bin 群)を1つの subvector にまとめてくれます。意味的に関連する次元が1つの subvector の中にあるほど、小さな codebook でもうまく表現できるからです。

4. Non-Exhaustive Search : IVFADC

3.4節の ADC は exhaustive な検索です。n 個のベクトルすべてを毎回スキャンしなければならず、画像1枚あたり数百〜数千個の SIFT が抽出され、数十億の descriptor をインデックスしなければならない環境では負担が大きすぎます。

論文では、inverted file と ADC を組み合わせた IVFADC を提案します。coarse quantizer でデータを Voronoi cell に分割してインデックスの小さな一部だけに高速にアクセスし、その中で residual を PQ でエンコードすることで精度まで少し引き上げます。

IVFADC indexing system。上は indexing の流れ、下は query の流れ

4.1. Coarse quantizer と residual encoding

Coarse quantizer $q_c$ は k-means で学習された一般的な vector quantizer です。SIFT 基準で centroid 数 $k'$ は通常 1,000 〜 1,000,000 の範囲で、第3章で見た product quantizer の $2^{64}$ より小さい値です。

核心は、ベクトル $y$ をそのまま PQ でエンコードするのではなく、residual をエンコードするということです。

residual は Voronoi cell 内での offset に相当します。元のベクトルよりエネルギーがはるかに小さく、同じコード長でより正確な近似が可能です。ベクトルは次のように近似されます。

保存表現は tuple $(q_c(y), q_p(r(y)))$ です。二進表現にたとえると、coarse quantizer が上位ビット(MSB)、product quantizer が**下位ビット(LSB)**を担当します。

距離の推定は、query $x$ と $\ddot{y}$ の距離として計算されます。

これを効率的に計算するために、subquantizer の分解を使用します。

ADC と同様に、各 subquantizer $q_{p_j}$ について partial residual $u_j(x - q_c(y))$ と centroid $c_{j,i}$ の距離を事前に計算して LUT に保存します。

Product quantizer は、学習データの residual の集合で unique な PQ を1つ学習します。学習ベクトルが互いに異なる coarse cell に属していても、residual の分布をすべての Voronoi cell にわたって marginalize した結果で学習します。

cell ごとに別々の PQ を置くと、codebook のメモリが $k' \times d \times k^*$ 個の floating point 値となり非現実的になります。

学習アルゴリズム

Train_IVFADC(training_set, k', m, k*)
1   // Step 1: coarse codebook 학습 (원본 벡터로 k-means)
2   coarse_codebook ← k-means(training_set, k')
3   //  → k'개의 coarse centroid c_1, ..., c_k'
4   //  → 이걸로 q_c 함수가 정의됨 (벡터 → 가장 가까운 c_i의 인덱스)
5
6   // Step 2: 학습 데이터의 residual 계산
7   residuals ← { y - q_c(y) : y ∈ training_set }
8
9   // Step 3: residual로 단일 product quantizer 학습 (3.3절 Train_PQ)
10  pq_codebooks ← Train_PQ(residuals, m, k*)
11  //  → m개 subspace codebook (C_1, ..., C_m)
12  //  → 이걸로 q_p 함수가 정의됨 (벡터 → m개 인덱스 = code)
13
14  return (coarse_codebook, pq_codebooks)

4.2. インデックスのデータ構造

Inverted file は list の配列 $L_1, \ldots, L_{k'}$ として実装されます。データセット $Y$ に対して、centroid $c_i$ に該当する list は:

list の entry は identifier と code の2つのフィールドで構成されます。

identifier は inverted file 構造のためにかかるオーバーヘッドです。ベクトルの種類によっては unique である必要がない場合もあります。例: 画像を local descriptor で表現する場合は image identifier が vector identifier を代替でき、同じ画像のすべてのベクトルが同じ identifier を持ちます。100万画像のデータセットなら 20-bit で十分です。

Indexing 手順(ベクトル $y$ 1本):

1. y を $q_c(y)$ に quantize
2. residual $r(y) = y - q_c(y)$ を計算
3. $r(y)$ を $q_p(r(y))$ に quantize。product quantizer の立場では、各 $u_j(y)$ を $q_j(u_j(y))$ に割り当てることと同じです ($j = 1, \ldots, m$)。
4. $q_c(y)$ に該当する inverted list に identifier + PQ コードを entry として追加。

Index_IVFADC(database: [(id_1, y_1), ..., (id_n, y_n)], coarse_codebook, pq_codebooks)
1   // k'개 빈 list 초기화
2   L_1, ..., L_k' ← empty
3
4   for each (id, y) in database:
5       // Step 1: coarse quantize → 어느 list?
6       i ← argmin_{1..k'} ||y - c_i||²        // c_i는 coarse_codebook[i]
7
8       // Step 2: residual 계산
9       r ← y - c_i
10
11      // Step 3: residual을 PQ로 인코딩 → code
12      code ← Encode_PQ(r, pq_codebooks)      // 곧 q_p(r), m byte 반환
13
14      // Step 4: list L_i에 (id, code) entry 추가
15      L_i.append((id, code))
16
17  return (L_1, ..., L_k')

4.3. 検索アルゴリズム

検索の核心は、inverted file のおかげで Y の小さな部分集合だけで距離推定を行うことです。query $x$ の $q_c(x)$ に該当する list $L_i$ だけをスキャンします。

しかし、$x$ に最も近い NN が同じ centroid に quantize されず、隣の centroid に属する可能性があります。この問題を解決するために multiple assignment 戦略を使用します。query $x$ を w 個のインデックスに割り当て(coarse codebook における $x$ の w-NN)、該当するすべての inverted list をスキャンします。database ベクトルには multiple assignment を適用しません。メモリがそのまま w 倍に増えるためです。

Search 手順(query $x$):

1. $x$ を codebook $q_c$ の w-NN に quantize。以降のステップは w 個の assignment すべてに適用されます(便宜上、residual を $r(x)$ と総称します)。
2. 各 subquantizer $j$ と各 centroid $c_{j,i}$ に対して squared distance $d(u_j(r(x)), c_{j,i})^2$ を計算。LUT を埋める。
3. inverted list のすべての indexed ベクトルに対して $r(x)$ との squared distance を計算。ステップ2で計算した subvector-to-centroid 距離を活用して m 個の looked-up value を合算(式 2)。
4. 推定距離に基づいて K-NN を選択。固定 capacity の Maxheap で効率的に実装 — これまでに見た K 個の最小値を保持し、新しい距離を計算したとき Maxheap の最大距離より小さい場合にのみ entry を追加します。

IVFADC_Search(x: query, w, K, coarse_codebook, pq_codebooks, lists)
1   // Step 1: query를 모든 coarse centroid와 비교 → 가까운 w개 list 선택
2   for i = 1 to k':
3       coarse_dist[i] ← ||x - c_i||²              // c_i는 coarse_codebook[i]
4   top_w_indices ← argsort(coarse_dist)[:w]
5
6   H ← Maxheap(capacity=K)
7
8   for each i in top_w_indices:
9       r_x ← x - c_i                              // query residual
10
11      // Step 2: LUT 채우기 (m × k* 엔트리)
12      //         pq_codebooks의 centroid 좌표를 *읽어서* 거리 미리 계산
13      for j = 1 to m:
14          for n = 0 to k*-1:
15              LUT[j][n] ← ||u_j(r_x) - c_{j,n}||²   // c_{j,n}은 pq_codebooks[j][n]
16
17      // Step 3: list L_i 스캔, code의 인덱스로 LUT lookup
18      for each (id, code) in L_i:
19          d² ← 0
20          for j = 1 to m:
21              d² ← d² + LUT[j][code[j]]          // j번째 subspace 거리 lookup
22          if d² < H.max():
23              H.push((d², id))
24
25  // Step 4: Maxheap에서 K개 추출
26  return sorted(H)[:K]

4.4. パラメータの意味

IVFADC のパラメータが検索性能にどう影響するかを整理すると、次のとおりです。

論文の推奨設定は $k^* = 256, m = 8$(つまり64ビットコード)です。$k'$ は SIFT 1M の実験で 1024〜8192 の値を試しており、データセットが大きいほど大きな $k'$ が有利になります。

IVF-ADC のインデックスおよび検索アルゴリズムの図解

5. 実験結果

論文は SIFT(128次元)、GIST(960次元)の2つのデータセットで検証を行いました。

実験環境はシングルコアで、学習/database/query はそれぞれ別々の set で構成されます。

5.1. Code length vs Accuracy trade-off

SDC の recall@100 vs code length (SIFT) ADC の recall@100 vs code length (SIFT)

SIFT データセット基準では、同じコード長で、少数の大きな subquantizer の方が多数の小さな subquantizer より良い性能を示します。たとえば64ビットのコードを作る場合、$(m=8, k^*=256)$ の方が $(m=16, k^*=16)$ より正確です。

ADC は SDC より一貫して優れていました。$m=8$ 基準で、ADC の $k^*=64$ が SDC の $k^*=256$ と同じ精度を達成しました。

5.2. State of the art との比較

PQ 論文は2種類の比較を別々に行います。

• 同じコード長のメモリ節約系アルゴリズムとの精度比較
• 元のベクトルを保持するツリーベース検索(FLANN)との速度-精度 trade-off

1) recall@R 比較 (vs SH, HE)

SIFT 64-bit codes における recall@R 比較 GIST 64-bit codes における recall@R 比較

どちらのグラフも、SDC/ADC は $m=8, k^*=256$、IVFADC は $k'=1024$ で測定しています。HE の曲線は SIFT のグラフにのみあり、こちらも $k'=1024$ です。

$recall@R$ は、全 query のうち $top-R$ の中に真の nearest neighbor が入っている割合です。

64ビットコード基準で、同じメモリ節約陣営の2つの baseline と比較しました。

• Spectral Hashing(SH) [Weiss et al. 2008]
• Hamming Embedding(HE) [Jégou et al. 2008]

PQ 系(SDC/ADC/IVFADC)はすべて spectral hashing を大差で上回りました。同じ recall に到達するために、ADC は spectral hashing より一桁少ない結果を verify するだけで済みました。

最も良い性能は IVFADC から得られ、これは exhaustive 検索を避けながらも精度をさらに引き上げたためです。

2) search time vs accuracy 比較 (vs FLANN)

検索品質(1-recall@1: 正解の NN が1位になる割合)と検索時間の間の trade-off

FLANN は短いコードのアルゴリズムではなくツリーで検索を高速化するライブラリなので、同じ recall@R 曲線で比較しても意味がなく、実際の検索時間と *1-recall@1(正解の NN が1位になる割合)*の trade-off で比較する方が自然です。

この比較での IVFADC は、shortlist の $R$ 個を実際の距離で並べ替える verification 段階を加えた変種です。IVFADC は同程度の精度でより速いか、同程度の時間でより正確であり、さらに重要な違いはメモリでした。インデックス構造のサイズは IVFADC が 25MB 未満、FLANN が 250MB 以上です。ただしこの実験では両者とも再ランキング用の元のベクトルを RAM に置いており、論文も構造のサイズはベクトル自体のメモリに比べれば小さいと付け加えています。

5.3. Complexity vs Speed trade-off

GIST データセット (500 queries, 64-bit codes) における各手法の検索時間と recall@100。IVFADC は k’ と w を変えながら測定

exhaustive 陣営の SDC、ADC、SH は時間が 16〜23ms と同程度ですが、recall は ADC が SH の5倍です。LUT の実数距離が、Hamming の整数距離より豊富な情報を含むためです。

IVFADC は w=1 のとき、コード比較の回数を100万から約2千回へと数百倍削減し、時間も10倍速くなる代わりに recall が低下します。w を大きくすると recall が回復し、w=8 なら exhaustive ADC より速く、かつより正確な動作点が存在します。

$k'$ は、データセットが小さければ 1K〜8K 程度が、大きくなるほど数万〜100万程度が有利です。ただし $k'⋅D>n/k'$ になると、coarse quantizer 自体が bottleneck になります。

IVFADC は $k', w$ の2つのパラメータで速度と精度の trade-off を描くことができます。実務では、許容される時間 budget 内で recall が最大になる点を選べば十分です。

5.4. 大規模実験: 20億ベクトル

データセットサイズに応じた検索時間 (HE vs IVFADC)

大規模実験は、100万枚の画像から抽出した約20億の SIFT descriptor をインデックスしたものです。同一の 20,000-word coarse codebook と64ビット signature、$w=1$ の条件で、IVFADC と HE を比較しました(クエリは10枚の画像から抽出した3万個の descriptor です)。

小さなデータセットでは、IVFADC は追加の quantization ステップのためにやや遅くなります。しかしデータセットが大きくなるほど inverted list 内部の距離計算が dominant になり、2つの手法のベクトルあたりの処理時間はほぼ同じになります。

HE は8回の table lookup で Hamming distance を計算し、IVFADC も8回の table lookup で PQ の距離を計算します。論文は、floating-point lookup の合算は binary 演算よりそれほど高くつかないと観察しています。

6. PQ の限界

6.1. 限界: 次元グルーピングに敏感

3.7節で見たように、PQ はどの次元を同じ subvector にまとめるかによって性能が大きく変わります。

SIFT、GIST のように明確な意味的グループがある descriptor では structured order で良い結果を出せますが、意味の分からない一般的なベクトル(例: word embedding、学習された feature)には直接適用しにくいです。

6.2. 限界: データ分布による性能のばらつき

PQ は、各 subvector が同程度のエネルギーを持ち、subspace が互いに直交的であるときに最もよく機能します (3.3節の仮定)。

SIFT/GIST 以外のデータセットでは効果が変わる可能性があります。その後登場した学習された embedding (word2vec、BERT、CLIP など)は、次元ごとの分散が非常に不均等で、隣接する次元が意味的に無関係な場合が多く、PQ をそのまま適用すると精度が低下する可能性があります。この段落は論文以後の観察であり、筆者の見解です。

6.3. 限界: residual の分布の違い

IVFADC はすべての cell で1つの同一な product quantizer を使用します。

これはすべての cell の residual 分布が似ているという仮定を前提にしていますが、論文自身も cell ごとの別々の PQ の方がおそらくより正確だろうと推測しています。cell ごとに別々の PQ を学習すれば精度は上がりますが、$k'$ 個の codebook をすべて保存しなければならず、メモリ使用が非現実的になります。

7. まとめ

PQ は、圧縮という観点から ANN 検索を解決したアルゴリズムです。

グラフベースのアルゴリズムは、訪問するベクトル数を減らして速度を得ます。PQ が減らしたのは、ベクトル1本のサイズです。128次元の SIFT なら 512B の元データが 8B のコードになり、その圧縮が距離計算を壊さないように空間を部分空間の積に分解して、小さな codebook 複数個で $2^{64}$ 個の centroid の表現力を確保しました。

ここに inverted file structure を組み合わせた IVFADC は、スキャン範囲も $n$ 個から $n \times w / k'$ 個へと減らしました。20億ベクトルを単一マシンでインデックスできるようにしたこの組み合わせは、今なお大規模ベクトル検索の標準 baseline の座を守っています。

8. 参考文献

• Product Quantization for Nearest Neighbor Searchdoi.org
• Spectral Hashingproceedings.neurips.cc
• Hamming Embedding and Weak Geometric Consistency for Large Scale Image Searchinria.hal.science
• Fast Approximate Nearest Neighbors with Automatic Algorithm Configurationcs.ubc.ca