Optimized high order product quantization for approximate nearest neighbors search

Abstract

Product quantization is now considered as an effective approach to solve the approximate nearest neighbor (ANN) search. A collection of derivative algorithms have been developed. However, the current techniques ignore the intrinsic high order structures of data, which usually contain helpful information for improving the computational precision. In this paper, aiming at the complex structure of high order data, we design an optimized technique, called optimized high order product quantization (O-HOPQ) for ANN search. In O-HOPQ, we incorporate the high order structures of the data into the process of designing a more effective subspace decomposition way. As a result, spatial adjacent elements in the high order data space are grouped into the same subspace. Then, O-HOPQ generates its spatial structured codebook, by optimizing the quantization distortion. Starting from the structured codebook, the global optimum quantizers can be obtained effectively and efficiently. Experimental results show that appropriate utilization of the potential information that exists in the complex structure of high order data will result in significant improvements to the performance of the product quantizers. Besides, the high order structure based approaches are effective to the scenario where the data have intrinsic complex structures.

Keywords

product quantization / high order structured data / tensor theory / approximate nearest neighbor search

References

[1] Wang J, Wang J, Yu N, Li S. Order preserving hashing for approximate nearest neighbor search. In: Proceedings of the ACM Conference on Multimedia. 2013, 133–142

[2] Hu D, Zhang G, Yang Y, Jin Z, Cai D, He X. A unified approximate nearest neighbor search scheme by combining data structure and hashing. In: Proceedings of AAAI Conference on Artificial Intelligence. 2013, 681–687

[3] Torralba A, Fergus R, Freeman W T. 80 million tiny images: a large data set for nonparametric object and scene recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 22(1): 1958–1970

[4] Luo W, Qu Z, Pan F, Huang J. A survey of passive technology for digital image forensics. Frontiers of Computer Science, 2007, 1(2): 166–179

[5] Sivic J, Zisserman A. Video google: a text retrieval approach to object matching in videos. In: Proceedings of the IEEE International Conference on Computer Vision. 2003, 1470–1477

[6] Boiman O, Shechtman E, Irani M. In defense of nearest-neighbor based image classification. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2008, 1–8

[7] Han B, Zhao X, Tao D, Li X, Hu Z, Hu H. Dayside aurora classification via BIFs-based sparse representation using manifold learning. International Journal of Computer Mathematics, 2014, 91(11): 2415–2426

[8] Khalili S, Simeone O, Haimovich A. Cloud radio-multistatic radar: joint optimization of code vector and backhaul quantization. IEEE Signal Processing Letters, 2015, 22(4): 494–498

[9] Qin C, Chang C C, Chiu Y P. A novel joint data-hiding and compression scheme based on SMVQ and image inpainting. IEEE Transactions on Image Processing, 2014, 23(3): 969–978

[10] Ge T, He K, Ke Q, Sun J. Optimized product quantization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(4): 744–755

[11] Brandt J. Transform coding for fast approximate nearest neighbor search in high dimensions. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2010, 1815–1822

[12] Gong Y, Lazebnik S, Gordo A, Perronnin F. Iterative quantization: a procrustean approach to learning binary codes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2011, 817–824

[13] Jegou H, Douze M, Schmid C. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1): 117–128

[14] Heo J P, Lin Z, Yoon S. Distance encoded product quantization. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014, 2139–2146

[15] Ge T, He K, Ke Q, Sun J. Optimized product quantization for approximate nearest neighbor search. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013, 2946–2953

[16] Datar M, Immorlica N, Indyk P, Mirrokni V S. Locality sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Symposium on Computational Geometry. 2004, 253–262

[17] Yan C C, Xie H, Zhang B, Ma Y, Dai Q, Liu Y. Fast approximate matching of binary codes with distinctive bits. Frontiers of Computer Science, 2015, 9(5): 741–750

[18] Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of ACM Symposium on Theory of Computing. 1998, 604–613

[19] Weiss Y, Torralba A, Fergus R. Spectral hashing. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. 2009, 1753–1760

[20] Kulis B, Darrell T. Learning to hash with binary reconstructive embeddings. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. 2009, 1042–1050

[21] Norouzi M, Blei D. Minimal loss hashing for compact binary codes. In: Proceedings of the IEEE International Conference on Machine Learning. 2011, 353–360

[22] Liu W, Wang J, Ji R. Supervised hashing with kernels. In: Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition. 2012, 2074–2081

[23] Weiss Y, Fergus R, Torralba A. Multidimensional spectral hashing. In: Proceedings of the IEEE European Conference on Computer Vision. 2012, 304–353

[24] He K, Wen F, Sun J. K-means hashing: an affinity-preserving quantization method for learning binary compact codes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013, 2938–2945

[25] Li Z, Liu X, Wu J, Su H. Adaptive binary quantization for fast nearest neighbor search. In: Proceedings of the Biennial European Conference on Artificial Intelligence. 2016, 64–72

[26] Liu X, Du B, Deng C, Liu M, Lang B. Structure sensitive hashing with adaptive product quantization. IEEE Transactions on Cybernetics, 2016, 46(10): 2252–2264

[27] Wang Z, Feng J, Yan S, Xi H. Linear distance coding for image classification. IEEE Transactions on Image Processing, 2013, 22(2): 537–548

[28] Sun X, Wang C, Xu C, Zhang L. Indexing billions of images for sketchbased retrieval. In: Proceedings of the ACM Conference on Multimedia. 2013, 233–242

[29] Rusińol M, Aldavert D, Toledo R, Lladós J. Efficient segmentation-free keyword spotting in historical document collections. Pattern Recognition, 2015, 48(2): 545–555

[30] Jiang Y, Jiang Y, Wang J. VCDB: a large-scale database for partial copy detection in videos. In: Proceedings of the European Conference on Computer Vision. 2014, 357–371

[31] Luo J, Zhou W, Wu J. Image categorization with resource constraints: introduction, challenges and advances. Frontiers of Computer Science, 2017, 11(1): 13–26

[32] Revaud J, Douze M, Schmid C, Jégou H. Event retrieval in large video collections with circulant temporal encoding. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013, 2459–2466

[33] Inoue N, Shinoda K. Neighbor-to-neighbor search for fast coding of feature vectors. In: Proceedings of the IEEE International Conference on Computer Vision. 2013, 1233–1240

[34] Norouzi M, Fleet D J. Cartesian k-means. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013, 3017–3024

[35] Kalantidis Y, Avrithis Y. Locally optimized product quantization for approximate nearest neighbor search. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014, 2329–2336

[36] Zhang T, Du C, Wang J. Composite quantization for approximate nearest neighbor search. In: Proceedings of the IEEE International Conference on Machine Learning. 2014, 838–846

[37] Matsui Y, Yamasaki T, Aizawa K. PQTable: fast exact asymmetric distance neighbor search for product quantization using hash tables. In: Proceedings of the IEEE International Conference on Computer Vision. 2015, 1940–1948

[38] Gray R. Vector quantization. IEEE ASSP Magazine, 1984, 1(2): 4–9

[39] Kolda T, Bader B. Tensor decompositions and applications. SIAM Review, 2009, 51(3): 455–500

[40] Bader B W, Kolda T G. Algorithm 862: matlab tensor classes for fast algorithm prototyping. ACM Transactions on Mathematical Software, 2006, 32(4): 635–653

[41] Folland G B. Real Analysis: Modern Techniques and Their Applications. John Wiley and Sons, 2013

[42] Hodges D, Danielson D. Nonlinear beam kinematics by decomposition of the rotation tensor. Journal of Applied Mechanics, 1987, 54(2): 258–262

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature