This paper studies the compact coding approach to approximate nearest
neighbor search. We introduce a composite quantization framework. It uses the
composition of several ($M$) elements, each of which is selected from a
different dictionary, to accurately approximate a $D$-dimensional vector, thus
yielding accurate search, and represents the data vector by a short code
composed of the indices of the selected elements in the corresponding
dictionaries. Our key contribution lies in introducing a near-orthogonality
constraint, which makes the search efficiency is guaranteed as the cost of the
distance computation is reduced to $O(M)$ from $O(D)$ through a distance table
lookup scheme. The resulting approach is called near-orthogonal composite
quantization. We theoretically justify the equivalence between near-orthogonal
composite quantization and minimizing an upper bound of a function formed by
jointly considering the quantization error and the search cost according to a
generalized triangle inequality. We empirically show the efficacy of the
proposed approach over several benchmark datasets. In addition, we demonstrate
the superior performances in other three applications: combination with
inverted multi-index, quantizing the query for mobile search, and inner-product
similarity search.

本文研究了一种用于近似最近邻搜索的紧凑编码方法，介绍了一种复合量化框架，其中包括使用不同字典中选定的若干元素的组合来准确近似 D 维向量，以此表示数据向量，实现准确搜索，从而实现距离计算成本从 O（D）降至 O（M）的近正交复合量化方法。