Composite Quantization for Approximate Nearest Neighbor Search

Ting Zhang, Chao Du, Jingdong Wang
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):838-846, 2014.

Abstract

This paper presents a novel compact coding approach, 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 vector and to represent the vector by a short code composed of the indices of the selected elements. To efficiently compute the approximate distance of a query to a database vector using the short code, we introduce an extra constraint, constant inter-dictionary-element-product, resulting in that approximating the distance only using the distance of the query to each selected element is enough for nearest neighbor search. Experimental comparison with state-of-the-art algorithms over several benchmark datasets demonstrates the efficacy of the proposed approach.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-zhangd14, title = {Composite Quantization for Approximate Nearest Neighbor Search}, author = {Zhang, Ting and Du, Chao and Wang, Jingdong}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {838--846}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/zhangd14.pdf}, url = {https://proceedings.mlr.press/v32/zhangd14.html}, abstract = {This paper presents a novel compact coding approach, 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 vector and to represent the vector by a short code composed of the indices of the selected elements. To efficiently compute the approximate distance of a query to a database vector using the short code, we introduce an extra constraint, constant inter-dictionary-element-product, resulting in that approximating the distance only using the distance of the query to each selected element is enough for nearest neighbor search. Experimental comparison with state-of-the-art algorithms over several benchmark datasets demonstrates the efficacy of the proposed approach.} }
Endnote
%0 Conference Paper %T Composite Quantization for Approximate Nearest Neighbor Search %A Ting Zhang %A Chao Du %A Jingdong Wang %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-zhangd14 %I PMLR %P 838--846 %U https://proceedings.mlr.press/v32/zhangd14.html %V 32 %N 2 %X This paper presents a novel compact coding approach, 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 vector and to represent the vector by a short code composed of the indices of the selected elements. To efficiently compute the approximate distance of a query to a database vector using the short code, we introduce an extra constraint, constant inter-dictionary-element-product, resulting in that approximating the distance only using the distance of the query to each selected element is enough for nearest neighbor search. Experimental comparison with state-of-the-art algorithms over several benchmark datasets demonstrates the efficacy of the proposed approach.
RIS
TY - CPAPER TI - Composite Quantization for Approximate Nearest Neighbor Search AU - Ting Zhang AU - Chao Du AU - Jingdong Wang BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-zhangd14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 838 EP - 846 L1 - http://proceedings.mlr.press/v32/zhangd14.pdf UR - https://proceedings.mlr.press/v32/zhangd14.html AB - This paper presents a novel compact coding approach, 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 vector and to represent the vector by a short code composed of the indices of the selected elements. To efficiently compute the approximate distance of a query to a database vector using the short code, we introduce an extra constraint, constant inter-dictionary-element-product, resulting in that approximating the distance only using the distance of the query to each selected element is enough for nearest neighbor search. Experimental comparison with state-of-the-art algorithms over several benchmark datasets demonstrates the efficacy of the proposed approach. ER -
APA
Zhang, T., Du, C. & Wang, J.. (2014). Composite Quantization for Approximate Nearest Neighbor Search. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):838-846 Available from https://proceedings.mlr.press/v32/zhangd14.html.

Related Material