K-Subspaces Quantization for Approximate Nearest Neighbour Search
Keywords:
Approximate Nearest Neighbour Search, Binary Codes, Large-Scale Retrieval, Subspace Clustering, Vector QuantizationAbstract
Approximate Nearest Neighbour (ANN) search has become a popular approach for performing fast and efficient retrieval on very large-scale datasets in recent years, as the size and dimension of data grow continuously. In this paper, we propose a novel vector quantization method for ANN search which enables faster and more accurate retrieval on publicly available datasets. We define vector quantization as a multiple affine subspace learning problem and explore the quantization centroids on multiple affine subspaces. We propose an iterative approach to minimize the quantization error in order to create a novel quantization scheme, which outperforms the state-of-the-art algorithms. The computational cost of our method is also comparable to that of the competing methods
References
[1] P. Indyk and R. Motwani, “Approximate nearest neighbors: towards removing the curse of dimensionality,” Proc. thirtieth Annu. ACM Symp. Theory Comput., pp. 604–613, 1998.
[2] J. Wang, H. T. Shen, J. Song, and J. Ji, “Hashing for Similarity Search: A Survey,” in arXiv preprint, 2014, p. :1408.2927.
[3] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, “Locality-Sensitive Hashing Scheme Based on P-stable Distributions,” in SCG, 2004, p. 253.
[4] K. Terasawa and Y. Tanaka, “Spherical LSH for Approximate Nearest Neighbor Search on Unit Hypersphere,” in WADS, 2007, pp. 27–38.
[5] X. He, D. Cai, S. Yan, and H. Zhang, “Neighborhood Preserving Embedding,” in ICCV, 2005.
[6] H. Jegou, M. Douze, C. Schmid, and P. Perez, “Aggregating local descriptors into a compact image representation,” in CVPR, 2010, pp. 3304–3311.
[7] J. Heo, Y. Lee, and J. He, “Spherical hashing,” in CVPR, 2012.
[8] A. Gordo, F. Perronnin, Y. Gong, and S. Lazebnik, “Asymmetric distances for binary embeddings.,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 36, no. 1, pp. 33–47, Jan. 2014.
[9] W. Dong, M. Charikar, and K. Li, “Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces,” in SIGIR, 2008, p. 123.
[10] S. Lloyd, “Least squares quantization in PCM,” IEEE Trans. Inf. Theory, vol. 28, no. 2, pp. 129–137, 1982.
[11] A. K. Jain, “Data clustering: 50 years beyond K-means,” Pattern Recognit. Lett., vol. 31, no. 8, pp. 651–666, 2010.
[12] H. Jégou, M. Douze, and C. Schmid, “Product quantization for nearest neighbor search.,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 33, no. 1, pp. 117–28, Jan. 2011.
[13] Y. Gong and S. Lazebnik, “Iterative quantization: A procrustean approach to learning binary codes,” in CVPR, 2011, pp. 817–824.
[14] J. Brandt, “Transform coding for fast approximate nearest neighbor search in high dimensions,” in CVPR, 2010, pp. 1815–1822.
[15] T. Ge, K. He, Q. Ke, and J. Sun, “Optimized Product Quantization.,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 36, pp. 1–12, Dec. 2014.
[16] M. Norouzi and D. J. Fleet, “Cartesian K-Means,” in CVPR, 2013, pp. 3017–3024.
[17] J.-P. Heo, Z. Lin, and S.-E. Yoon, “Distance Encoded Product Quantization,” in CVPR, 2014, pp. 2139–2146.
[18] Y. Kalantidis and Y. Avrithis, “Locally Optimized Product Quantization for Approximate Nearest Neighbor Search,” in CVPR, 2014.
[19] J. Wang, J. Wang, J. Song, X.-S. Xu, H. T. Shen, and S. Li, “Optimized Cartesian K-Means,” IEEE Trans. Knowl. Data Eng., vol. 27, no. 1, pp. 180–192, Jan. 2015.
[20] A. Babenko and V. Lempitsky, “Additive Quantization for Extreme Vector Compression,” in CVPR, 2014, pp. 931–938.
[21] T. Zhang, D. Chao, and J. Wang, “Composite Quantization for Approximate Nearest Neighbor Search,” in ICML, 2014.
[22] A. Babenko and V. Lempitsky, “Tree Quantization for Large-Scale Similarity Search and Classification,” in CVPR, 2015.
[23] R. M. Gray and D. L. Neuhoff, “Quantization,” IEEE Trans. Inf. Theory, vol. 44, no. 6, pp. 2325–2383, 1998.
[24] N. Kambhatla and T. K. Leen, “Dimension Reduction by Local Principal Component Analysis,” Neural Comput., vol. 9, no. 7, pp. 1493–1516, Oct. 1997.
[25] V. Gassenbauer, J. Křivánek, K. Bouatouch, C. Bouville, and M. Ribardière, “Improving Performance and Accuracy of Local PCA,” Comput. Graph. Forum, vol. 30, no. 7, pp. 1903–1910, Sep. 2011.
[26] P. Agarwal and N. Mustafa, “k-Means Projective Clustering,” in SIGMOD, 2004, pp. 155–165.
[27] C. M. Bishop, “Bayesian PCA,” in NIPS, 1999, vol. 11, pp. 382–388.
[28] E. C. Ozan, S. Kiranyaz, and M. Gabbouj, “M-PCA Binary Embedding For Approximate Nearest Neighbor Search,” in BigDataSE, 2015.
[29] M. Gallagher, “Proportionality, disproportionality and electoral systems,” Electoral Studies, vol. 10. pp. 33–51, 1991.
[30] A. Babenko and V. Lempitsky, “The inverted multi-index,” in CVPR, 2012, vol. 14, no. 1–3, pp. 3069–3076.
[31] H. Jégou, R. Tavenard, M. Douze, and L. Amsaleg, “Searching in one billion vectors: Re-rank with source coding,” ICASSP, no. 3, pp. 861–864, 2011.
Downloads
Published
How to Cite
Issue
Section
License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.
