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 = {Ting Zhang and Chao Du and Jingdong Wang}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {838--846}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 838--846 %U http://proceedings.mlr.press %V 32 %N 2 %W PMLR %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 PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-zhangd14 PB - PMLR SP - 838 DP - PMLR EP - 846 L1 - http://proceedings.mlr.press/v32/zhangd14.pdf UR - http://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 PMLR 32(2):838-846

Related Material