IVF ускоряет поиск, пропуская бóльшую часть базы, но каждый вектор остаётся без сжатия. Один миллиард SIFT дескрипторов — 512 ГБ RAM. Product Quantization (PQ), предложенная Жегу, Дузом и Шмидом в 2011 году, сжимает каждый вектор до 8 байт, а расстояния между сжатыми версиями остаются осмысленными.
Идея — как в GIF. 24-битный RGB пиксель — любой из 16,7 млн цветов. GIF выбирает палитру из 256 цветов и заменяет каждый пиксель 8-битным индексом. Память падает втрое, картинка всё ещё похожа. Вектор — тот же пиксель, только длинный. Нужна палитра (codebook) представительных центроидов, каждый дескриптор заменяется индексом ближайшего.
Сколько бит на индекс? Чтобы различать k центроидов, нужно ceil(log2(k)) бит. k=256 → 8 бит (1 байт), k=2^64 → 64 бита (8 байт). Цель статьи — ужать 128-мерный SIFT (512 байт) до 64 бит, то есть 0,5 бита на размерность. Один плоский словарь потребовал бы k=2^64 ≈ 1,8×10^19 центроидов. Это невозможно: хранить такой codebook — 9,4 зеттабайт, больше всех облачных хранилищ Земли. Для обучения нужно ~30·2^64 векторов — таких данных нет. При запросе пришлось бы сравнивать каждый вектор с 18 квинтиллионами центроидов.
Решение — разбить вектор на m подвекторов и для каждого учить свой маленький словарь. Формально: делим x на m подвекторов u_j ∈ R^(D/m) и учим субквантователь q_j на каждый блок. Product Quantizer — кортеж их выходов: q(x) = (q_1(u_1(x)), ..., q_m(u_m(x))). Настройка из статьи: D=128, m=8, k=256 центроидов на блок. Эффективный словарь — 256^8 ≈ 2^64 (те же 18 квинтиллионов комбинаций), но храним всего m·k = 2048 центроидов в R^16. Codebook занимает 128 КБ — помещается в L2 кэш. Каждый закодированный вектор — m·log2(k*) = 8×8 = 64 бита = 8 байт. Сжатие 64x, и кодбук реально умещается на машине.