Optimized Product Quantization

TLDR

Product quantization efficiently compresses high‑dimensional vectors by decomposing the space into a Cartesian product of subspaces and quantizing each separately, enabling an exponentially large codebook at low memory and time cost, yet the optimal space decomposition remains an open problem. This work aims to optimize product quantization by jointly minimizing quantization distortion over space decomposition and codebooks. We propose two optimization strategies—an iterative alternating‑minimization of sub‑problems and a Gaussian‑based analytical approach—and evaluate the resulting quantizers on compact encoding for exhaustive ranking, inverted multi‑indexing for non‑exhaustive search, and image retrieval. Across all three applications, the optimized product quantizers consistently outperform existing methods.

Abstract

Product quantization (PQ) is an effective vector quantization method. A product quantizer can generate an exponentially large codebook at very low memory/time cost. The essence of PQ is to decompose the high-dimensional vector space into the Cartesian product of subspaces and then quantize these subspaces separately. The optimal space decomposition is important for the PQ performance, but still remains an unaddressed issue. In this paper, we optimize PQ by minimizing quantization distortions w.r.t the space decomposition and the quantization codebooks. We present two novel solutions to this challenging optimization problem. The first solution iteratively solves two simpler sub-problems. The second solution is based on a Gaussian assumption and provides theoretical analysis of the optimality. We evaluate our optimized product quantizers in three applications: (i) compact encoding for exhaustive ranking [1], (ii) building inverted multi-indexing for non-exhaustive search [2], and (iii) compacting image representations for image retrieval [3]. In all applications our optimized product quantizers outperform existing solutions.