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.

Approximate Nearest Neighbour Search, Binary Codes, Large-Scale Retrieval, Subspace Clustering, Vector Quantization.

[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.