1. 개요

Product Quantization(PQ)은 고차원 벡터를 여러 subvector로 나누고, 각 부분 공간을 작은 codebook으로 양자화해 하나의 벡터를 짧은 코드로 압축하는 nearest neighbor search 기법입니다. 핵심은 원본 벡터를 모두 RAM에 올리지 않고도, 압축된 코드 위에서 거리 계산을 근사해 대규모 검색의 메모리 병목을 줄이는 것입니다.

대규모 벡터 검색은 추천 시스템, 이미지 검색, 의미 기반 문서 검색 등에서 반복되는 문제입니다. NSW와 HNSW가 이 문제를 그래프 탐색을 빠르게 하는 방향에서 접근한다면, PQ는 벡터 자체를 짧은 코드로 압축해서 거리 계산을 압축된 코드 위에서 근사하는 방향에서 접근합니다. Product Quantization for Nearest Neighbor Search 논문(Jégou, Douze, Schmid, 2011)은 이 접근을 ANN 검색에 체계적으로 적용한 대표 논문입니다.

핵심 질문은 다음과 같습니다.

• 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가 하는 일은 두 단계로 나뉩니다.

1. 입력을 받아 가장 가까운 codeword의 인덱스를 결정
2. 그 인덱스에서 다시 codeword 값을 복원

원본을 그대로 저장하는 대신 인덱스만 저장하면 메모리가 크게 줄어듭니다. codeword가 256개라면 인덱스는 1 byte면 충분합니다. 이 압축이 손실(lossy) 인 이유는, 원본의 정확한 값을 codeword라는 대표점으로 대체하기 때문입니다.

다루는 데이터에 따라 quantizer 종류가 나뉩니다.

PQ(Product Quantization) 가 다루는 vector quantization 에서는 codeword가 벡터 공간 안의 한 점이고, 데이터의 cluster 중심이라는 의미로 쓰이기 때문에 centroid 라고 부릅니다. quantizer의 품질은 원본과 codeword 사이 거리 제곱의 평균 인 MSE (Mean Squared Error) 로 측정합니다.

2.2. SIFT와 GIST Descriptor

PQ 논문이 실험에서 사용하는 두 종류의 이미지 descriptor입니다. 둘은 데이터 분포 특성이 달라 PQ의 차원 그룹핑 전략에도 영향을 줍니다. (3.7 참고)

SIFT, GIST descriptor 설명

SIFT (Scale-Invariant Feature Transform) 는 local descriptor입니다. 이미지에서 키포인트(코너, 엣지 같은 특징적 지점)를 검출하고, 각 키포인트 주변에서 그라디언트 히스토그램을 모은 128차원 벡터를 만듭니다. 이미지 1장당 수백~수천 개 의 벡터가 나옵니다. 회전 및 스케일 변화에 강건한 대신, 벡터 수가 폭발합니다. 논문 실험 기준 SIFT는 natural order가 이미 공간적으로 인접한 셀을 묶어 그룹핑에 둔감한 반면, GIST는 natural order가 다소 임의적이라 어떤 차원을 묶느냐가 성능을 크게 좌우합니다.

두 descriptor 모두 orientation histogram들을 이어 붙여 만든 구조지만, natural order(앞에서부터 차례로 자르기)가 의미 단위를 잘 묶어주는 정도 가 다릅니다. SIFT는 natural order가 이미 공간적으로 인접한 셀을 묶어 그룹핑에 둔감한 반면, GIST는 natural order가 다소 임의적이라 어떤 차원을 묶느냐가 성능을 크게 좌우합니다.

2.3. Hamming Embedding

Hamming embedding은 고차원 실수 벡터를 짧은 binary code로 매핑하는 기법입니다.

매핑된 두 코드 사이의 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 하나가 inverted list 하나에 대응됩니다.

좌측은 coarse centroid(★)가 공간을 Voronoi cell로 분할한 모습이고, 우측은 각 cell의 벡터들이 inverted list로 저장된 모습입니다. query는 가장 가까운 centroid의 list 하나만 스캔

이 논문에서 product quantizer 하나만으로는 모든 데이터를 매번 scan해야 하는 한계를 inverted file로 해결합니다. coarse quantizer로 어느 영역인지(상위 비트)를 정하고, product quantizer로 그 안의 residual(하위 비트)을 압축하는 2단계 계층 구조가 IVFADC입니다.

3. PQ 논문 정리

3.1. 논문 개요

논문이 등장한 시점, ANN 검색 분야에는 다음과 같은 흐름이 있었습니다.

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 수를 늘리는 시도들이 있었습니다.

세 대안 모두 세 가지 문제(학습 데이터 / 시간 / 메모리)를 동시에 풀지 못합니다. PQ는 이 셋을 모두 해결하면서 전혀 새로운 자리를 차지합니다.

3.1.3. PQ의 자리: "semi-structured" quantizer

Quantizer를 구조성에 따라 세 부류로 나눌 수 있습니다.

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 의 두 가지 장점

장점 1 — Distinct distance의 다양성: $b$ 비트 Hamming 코드가 거리값을 $b+1$ 가지 정수로만 표현하는 반면, PQ-ADC는 LUT(Look-Up Table)에 실수 거리가 들어가므로 사실상 연속적인 거리값을 만들어냅니다. 같은 코드 길이로 훨씬 정확한 ranking이 가능해집니다.

장점 2 — Expected squared distance 추정: PQ는 실제 거리값의 추정치를 제공합니다. 단순한 순위뿐 아니라 얼마나 가까운가까지 알려줍니다. 이게 두 가지 응용에서 중요합니다.

• ε-radius 검색: "거리가 ε 이내인 모든 벡터를 찾아라" → 실제 거리값이 필요
• Lowe's distance ratio criterion: SIFT 매칭에서 1순위 거리 / 2순위 거리 비율로 매칭 신뢰성을 판단하는 표준 기법 → 거리값 자체가 필요

Hamming embedding은 순위 만 줄 뿐 이런 거리값을 못 제공합니다. PQ는 추가 비용 없이 거리값을 함께 제공합니다.

3.1.5. Hamming 진영의 속도 강점도 동등

Hamming embedding이 인기였던 이유는 table lookup을 이용한 매우 빠른 거리 계산입니다. 그런데 PQ-ADC도 같은 수의 table lookup(8번 lookup + 7번 덧셈)으로 거리를 계산합니다.

속도는 같은데 정확도는 훨씬 좋다 — 이게 PQ가 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가 만족해야 하는 두 조건 을 명시합니다.

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가 두 조건을 (near-optimal하게) 만족 시키므로 이를 학습 도구로 사용합니다.

3.2.2. Cell distortion

cell별 distortion 도 정의합니다 — cell $\mathcal{V}_i$ 한정의 평균 제곱 오차입니다.

전체 MSE는 cell별 distortion의 확률 가중 평균 으로 표현됩니다.

3.2.3. 메모리 비용

마지막으로, 인덱스 값 하나를 저장하는 비용은 $\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 수는 다음과 같습니다.

같은 $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을 위해 원본을 보관해야 하므로 첫 번째 줄에 해당합니다. PQ는 코드 위에서 직접 거리 추정하기 때문에 두 번째 줄로 충분합니다. 이 64배 차이가 수십억 벡터를 단일 머신에 인덱싱할 수 있게 만든 결정적인 차이입니다.

"큰 codebook 하나" 대신 "작은 codebook 여러 개의 곱" 으로 같은 표현력을 지수적으로 적은 자원으로 얻고, 벡터까지 짧은 코드로 압축 해서 RAM에 올립니다.

각 subquantizer는 $k^*$가 작기 때문에 평범한 Lloyd's algorithm으로 충분히 학습할 수 있습니다. 그리고 각 벡터는 각 subquantizer의 인덱스 $m$ 개를 모은 짧은 코드로 표현됩니다. $m=8, k^=256$* *이면 한 벡터가 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 논문은 두 가지 방법을 제시합니다.

SDC와 ADC. SDC는 query도 quantize하고, ADC는 query는 그대로 두고 database 벡터만 quantize

Symmetric Distance Computation (SDC): query $x$와 database 벡터 $y$ 모두 quantize 한 뒤, 두 centroid 사이 거리로 근사합니다.

Asymmetric Distance Computation (ADC): query는 quantize 하지 않고, database 벡터만 quantize 합니다.

언뜻 보면 SDC가 대칭적이라 자연스러워 보이지만, ADC가 거의 항상 더 정확합니다. 이유는 단순합니다. ADC는 query 쪽에 quantization 오차가 없기 때문입니다.

ADC의 또 하나의 장점은 LUT(Look-Up Table)을 query마다 한 번만 미리 계산 해두면 된다는 점입니다. query가 들어오면 각 subquantizer $j$마다 다음 표를 미리 계산합니다.

그 뒤 database 벡터 하나의 거리를 계산할 때는 그 벡터의 코드 $(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

ADC 알고리즘 LUT 를 사용한 거리 계산 알고리즘 도식화

전체 비용이 거의 같으므로, query 쪽 메모리를 줄여야 하는 특수한 경우가 아니라면 ADC를 쓰는 것이 권장됩니다.

3.5. 거리 추정의 통계적 보장

PQ가 단순한 휴리스틱이 아닌 원리적인 근사임을 보여주는 결과가 있습니다. ADC의 거리 추정 오차가 quantizer의 MSE로 통계적으로 bound 된다 는 것입니다.

여기서 $\text{MSDE}$(Mean Squared Distance Error)는 추정 거리와 실제 거리의 제곱 오차의 평균이고, $\text{MSE}$는 quantizer 자체의 평균 제곱 오차입니다.

3.5.1. 증명 단계

핵심 도구는 삼각부등식입니다. 임의의 세 점 $x, y, q(y)$에 대해:

이게 삼각부등식의 한 형태인데, 직관적으로는 "어떤 한 점을 살짝 옮겼을 때, 다른 점과의 거리 변화는 옮긴 거리만큼만 가능하다" 입니다. ADC는 $\tilde{d}(x, y) = d(x, q(y))$ 로 정의되므로, 좌변은 우리가 알고 싶은 거리 추정 오차입니다.

세 점 x, y, q(y)에 대한 삼각부등식. ADC 추정 오차(검정변 - 파란점선)는 y의 quantization error (빨간실선) 이하로 bound 됩니다.

양변을 제곱하면:

$\text{MSDE}$ 정의에 $(1)$을 대입하고 $x$에 대한 적분을 정리하면:

SDC의 경우 query와 database 벡터 양쪽 모두 quantize 되므로 삼각부등식을 두 번 적용해야 하고, 결과는 $\text{MSDE}_{\text{SDC}}(q) \leq 2 \cdot \text{MSE}(q)$ 가 됩니다. ADC가 SDC보다 본질적으로 더 정확한 수학적 이유가 이 bound 차이에 있습니다.

• k-means(Lloyd's algorithm)로 quantizer를 학습하면 MSE가 작아진다 (3.2절 optimality conditions)
• MSE가 작으면 MSDE도 작다 (위 증명)
• MSDE가 작으면 NN 검색의 ranking이 진짜 거리에 가깝다

3.6. ADC의 bias 분석과 보정

3.5 절에서 $MSDE$ bound는 $MSE$ 을 다뤘지만, ADC 추정 거리는 평균적으로 실제 거리를 과소평가(underestimate) 합니다.

1000개 벡터 집합에서 SIFT vector 한 개를 query로 사용한 일반적인 검색 결과

3.6.1. 보정 공식의 유도

이 bias를 정확히 보정 을 위해 y가 cell $\mathcal{V}_i$ 에 있다는 조건 하의 expected squared distance 를 직접 계산합니다.

논문에서 $x - y$ 를 $c_i$ 를 거치는 형태로 분해합니다.

세 항을 적분하면 cross term이 정확히 0이 됩니다. Lloyd's 두 번째 optimality condition 덕분입니다.

centroid가 cell의 평균 이라는 조건이 cross term을 정확히 0으로 만들어 보정 공식을 깔끔하게 만들어줍니다. 남는 두 항은:

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). 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$ 가 큰 셀)의 벡터에 페널티 를 주는 효과가 되어 진짜로 가까운 벡터를 놓치게 됩니다.

3.7. 차원 그룹핑의 영향

PQ의 가장 단순한 구현은 벡터를 앞에서부터 순서대로 잘라 subvector를 만드는 것입니다. 그런데 이 grouping 방식이 성능에 의외로 큰 영향을 미칩니다.

논문이 SIFT와 GIST에서 확인한 결과는 다음과 같습니다.

($recall@100$, $k^*=256$ 기준)

GIST descriptor에서 natural order에서 structured order로 바꾸는 것만으로 recall@100이 0.338에서 0.652로 두 배가 됩니다. 같은 코드 길이로 같은 알고리즘을 돌렸는데 차원을 어떻게 묶느냐에 따라 성능이 극적으로 변한 것입니다.

SIFT나 GIST 같은 descriptor는 orientation histogram들을 이어붙여 만든 구조입니다. natural order로 자르면 한 histogram의 bin들이 여러 subvector에 흩뿌려질 수 있고, random order는 더 심합니다. structured order는 같은 의미를 가진 dimension들(예: 같은 orientation을 나타내는 bin들)을 한 subvector에 묶어줍니다. 의미적으로 관련된 차원이 한 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 하나를 학습합니다. 학습 벡터들이 서로 다른 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 두 필드로 구성됩니다.

identifier는 inverted file 구조 때문에 드는 오버헤드입니다. 벡터의 종류에 따라 unique할 필요가 없을 수도 있습니다. 예: 이미지를 local descriptor로 표현할 때는 image identifier가 vector identifier를 대체할 수 있어 — 같은 이미지의 모든 벡터가 같은 identifier를 갖습니다. 100만 이미지 데이터셋이면 20-bit면 충분합니다.

Indexing 절차 (벡터 $y$ 한 개):

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비트 코드) 그리고 SIFT 기준 $k' \in [1024, 8192]$ 입니다.

IVF-ADC 인덱스 및 검색 알고리즘 도식화

5. 실험 결과

논문은 SIFT(128차원), GIST(960차원) 두 데이터셋에서 검증을 수행했습니다.

실험 환경은 단일 코어이며, 학습/database/query 각각 별도의 set으로 구성됩니다.

5.1. Code length vs Accuracy trade-off

SDC의 recall@100 vs code length

ADC의 recall@100 vs code length

같은 코드 길이에서 적은 수의 큰 subquantizer가 많은 수의 작은 subquantizer보다 좋은 성능을 보입니다. 예를 들어 64비트 코드를 만들 때 $(m=8, k^*=256)$ 이 $(m=16, k^*=16)$ *보다 정확합니다.

ADC가 SDC보다 일관되게 우수했습니다. 같은 정확도를 ADC $k^*=64$ 가 SDC $k^*=256$과 비슷하게 달성했습니다.

5.2. State of the art와의 비교

PQ 논문은 두 종류의 비교를 별도로 진행합니다.

• 같은 코드 길이의 메모리 절약 알고리즘들과의 정확도 비교
• 원본 벡터를 들고 있는 트리 기반 검색 (FLANN)과의 속도-정확도 trade-off

1) recall@R 비교 (vs SH, HE)

SIFT 64-bit codes에서의 recall@R 비교 (Parameters: m=8 and k^∗=256 for SDC/ADC, k’ =1024 for HE and IVFADC)

GIST 64-bit codes에서의 recall@R 비교 (Parameters: m=8 and k^∗=256 for SDC/ADC, k’ =1024 for HE and IVFADC)

$recall@R$ 는 전체 query 중 $top-R$ 안에 진짜 nearest neighbor가 들어 있는 비율입니다.

64비트 코드 기준으로 같은 메모리 절약 진영 의 두 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)과 검색 시간 사이의 trade-off

FLANN은 짧은 코드 알고리즘이 아니라 트리로 검색을 가속하는 라이브러리 이므로 같은 recall@R 곡선으로 비교하는 게 의미가 없고, 실제 검색 시간과 Top-1 정답률( $1-recall@1$ ) 의 trade-off로 비교하는 게 더 자연스럽습니다.

IVFADC는 비슷한 정확도에서 더 빠르거나, 비슷한 시간에서 더 정확 했고, 더 중요한 차이는 메모리였습니다. IVFADC의 인덱스는 25MB 미만, FLANN은 250MB 이상. 이는 FLANN이 re-ranking을 위해 원본 벡터를 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)하지만 ADC가 SH보다 recall 5배 — LUT의 실수 거리가 Hamming 정수 거리보다 풍부한 정보를 담음.
• IVFADC (w=1) 는 코드 비교를 100만 → 약 2천 번으로 수백 배 감소, 시간도 10배 빠름. 다만 recall이 떨어짐.
• w를 키우면 recall 회복: w=8일 때 exhaustive ADC보다 빠르면서도 더 정확한 동작점이 존재.
• $k'$ 선택 : 데이터셋이 작으면 작은 $k'$ (1K~8K), 클수록 큰 $k'$ *(수만~100만)*가 유리. 단, $k'⋅D>n/k'*$ 가 되면 coarse quantizer 자체가 bottleneck.

IVFADC는 $k', w$ 두 파라미터로 속도와 정확도의 trade-off를 그릴 수 있습니다. 실무에서는 허용 시간 budget 내에서 recall이 최대 인 점을 선택합니다.

5.4. 대규모 실험: 20억 벡터

데이터셋 크기에 따른 검색 시간 (HE vs IVFADC)

대규모 실험은 백만 개 이미지에서 추출한 약 20억 SIFT descriptor를 인덱싱한 것입니다. 동일한 20,000-word coarse codebook과 64비트 signature 조건에서 IVFADC와 HE를 비교했습니다.

작은 데이터셋에서는 IVFADC가 추가 quantization 단계 때문에 약간 느립니다. 그러나 데이터셋이 커질수록 inverted list 내부의 거리 계산이 dominant 해지면서 두 방법의 벡터당 처리 시간이 거의 같아집니다.

HE는 8번의 table lookup으로 Hamming distance를 계산하고, IVFADC도 8번의 table lookup으로 PQ 거리를 계산합니다. floating-point 연산이 binary 연산만큼 빨라진다는 것이 PQ의 핵심 효율성입니다.

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에서 하나의 동일한 product quantizer 를 사용합니다.

이는 모든 cell의 residual 분포가 비슷하다 는 가정을 깔고 있는데, 실제로는 cell마다 residual 분포가 꽤 다릅니다. cell마다 별도의 PQ를 학습하면 정확도는 올라가지만, $k'$ 개의 codebook을 모두 저장해야 해서 메모리 사용이 비현실적이 됩니다

7. 마무리

PQ는 압축이라는 관점에서 ANN 검색을 해결한 알고리즘입니다.

그래프 기반 알고리즘이 어떻게 빨리 탐색할 것인가에 집중했다면, PQ는 어떻게 작게 표현할 것인가에 집중했습니다. 그리고 그 압축이 거리 계산을 망가뜨리지 않도록, 공간을 부분 공간의 곱으로 분해해 작은 codebook 여러 개의 곱으로 큰 표현력을 얻는 길을 찾았습니다.

여기에 inverted file structure를 결합한 IVFADC는 압축으로 메모리를 줄이고, 분할로 시간을 줄이는 두 가지 효과를 한 시스템에 합쳤습니다. 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