Composite Quantization for Approximate Nearest Neighbor Search

This paper presents a novel compact coding ap-proach, composite quantization, for approximate nearest neighbor search. The idea is to use the composition of several elements selected from the dictionaries to accurately approximate a vec-tor and to represent the vector by a short code composed of the indices of the selected ele-ments. To efficiently compute the approximate distance of a query to a database vector using the short code, we introduce an extra constraint, con-stant inter-dictionary-element-product, resulting in that approximating the distance only using the distance of the query to each selected ele-ment is enough for nearest neighbor search. Ex-perimental comparisonwith state-of-the-art algo-rithms over several benchmark datasets demon-strates the efficacy of the proposed approach. 1