Optimized high order product quantization for approximate nearest neighbors search

doi:10.1007/s11704-018-7049-5

Front. Comput. Sci.

2020, Vol. 14

Issue (2) : 259-272 https://doi.org/10.1007/s11704-018-7049-5

RESEARCH ARTICLE

Optimized high order product quantization for approximate nearest neighbors search

Linhao LI^1,²(

), Qinghua HU²

¹. School of Artificial Intelligence, Hebei University of Technology, Tianjin 300401, China
². Tianjin Key Lab of Machine Learning, School of Computer Science and Technology, Tianjin University, Tianjin 300072, China

Download: PDF(850 KB)
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Linhao LI

Just Accepted Date: 09 October 2017 Online First Date: 17 September 2019 Issue Date: 16 October 2019

Cite this article:

Linhao LI,Qinghua HU. Optimized high order product quantization for approximate nearest neighbors search[J]. Front. Comput. Sci., 2020, 14(2): 259-272.

URL:

https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7049-5
https://academic.hep.com.cn/fcs/EN/Y2020/V14/I2/259

1	J Wang, J Wang, N Yu, S Li. Order preserving hashing for approximate nearest neighbor search. In: Proceedings of the ACM Conference on Multimedia. 2013, 133–142 https://doi.org/10.1145/2502081.2502100
2	D Hu, G Zhang, Y Yang, Z Jin, D Cai, X He. 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	A Torralba, R Fergus, W T Freeman. 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 https://doi.org/10.1109/TPAMI.2008.128
4	W Luo, Z Qu, F Pan, J Huang. A survey of passive technology for digital image forensics. Frontiers of Computer Science, 2007, 1(2): 166–179 https://doi.org/10.1007/s11704-007-0017-0
5	J Sivic, A Zisserman. Video google: a text retrieval approach to object matching in videos. In: Proceedings of the IEEE International Conference on Computer Vision. 2003, 1470–1477 https://doi.org/10.1109/ICCV.2003.1238663
6	O Boiman, E Shechtman, M Irani. In defense of nearest-neighbor based image classification. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2008, 1–8 https://doi.org/10.1109/CVPR.2008.4587598
7	B Han, X Zhao, D Tao, X Li, Z Hu, H Hu. Dayside aurora classification via BIFs-based sparse representation using manifold learning. International Journal of Computer Mathematics, 2014, 91(11): 2415–2426 https://doi.org/10.1080/00207160.2013.831084
8	S Khalili, O Simeone, A Haimovich. Cloud radio-multistatic radar: joint optimization of code vector and backhaul quantization. IEEE Signal Processing Letters, 2015, 22(4): 494–498 https://doi.org/10.1109/LSP.2014.2363939
9	C Qin, C C Chang, Y P Chiu. A novel joint data-hiding and compression scheme based on SMVQ and image inpainting. IEEE Transactions on Image Processing, 2014, 23(3): 969–978 https://doi.org/10.1109/TIP.2013.2260760
10	T Ge, K He, Q Ke, J Sun. Optimized product quantization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(4): 744–755 https://doi.org/10.1109/TPAMI.2013.240
11	J Brandt. 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 https://doi.org/10.1109/CVPR.2010.5539852
12	Y Gong, S Lazebnik, A Gordo, F Perronnin. Iterative quantization: a procrustean approach to learning binary codes. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2011, 817–824 https://doi.org/10.1109/CVPR.2011.5995432
13	H Jegou, M Douze, C Schmid. Product quantization for nearest neighbor search. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1): 117–128 https://doi.org/10.1109/TPAMI.2010.57
14	J P Heo, Z Lin, S Yoon. Distance encoded product quantization. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014, 2139–2146 https://doi.org/10.1109/CVPR.2014.274
15	T Ge, K He, Q Ke, J Sun. Optimized product quantization for approximate nearest neighbor search. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013, 2946–2953 https://doi.org/10.1109/CVPR.2013.379
16	M Datar, N Immorlica, P Indyk, V S Mirrokni. Locality sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Symposium on Computational Geometry. 2004, 253–262 https://doi.org/10.1145/997817.997857
17	C C Yan, H Xie, B Zhang, Y Ma, Q Dai, Y Liu. Fast approximate matching of binary codes with distinctive bits. Frontiers of Computer Science, 2015, 9(5): 741–750 https://doi.org/10.1007/s11704-015-4192-0
18	P Indyk, R Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of ACM Symposium on Theory of Computing. 1998, 604–613 https://doi.org/10.1145/276698.276876
19	Y Weiss, A Torralba, R Fergus. Spectral hashing. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. 2009, 1753–1760
20	B Kulis, T Darrell. Learning to hash with binary reconstructive embeddings. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems. 2009, 1042–1050
21	M Norouzi, D Blei. Minimal loss hashing for compact binary codes. In: Proceedings of the IEEE International Conference on Machine Learning. 2011, 353–360
22	W Liu, J Wang, R Ji. Supervised hashing with kernels. In: Proceedings of the IEEE International Conference on Computer Vision and Pattern Recognition. 2012, 2074–2081
23	Y Weiss, R Fergus, A Torralba. Multidimensional spectral hashing. In: Proceedings of the IEEE European Conference on Computer Vision. 2012, 304–353 https://doi.org/10.1007/978-3-642-33715-4_25
24	K He, F Wen, J Sun. 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 https://doi.org/10.1109/CVPR.2013.378
25	Z Li, X Liu, J Wu, H Su. Adaptive binary quantization for fast nearest neighbor search. In: Proceedings of the Biennial European Conference on Artificial Intelligence. 2016, 64–72
26	X Liu, B Du, C Deng, M Liu, B Lang. Structure sensitive hashing with adaptive product quantization. IEEE Transactions on Cybernetics, 2016, 46(10): 2252–2264 https://doi.org/10.1109/TCYB.2015.2474742
27	Z Wang, J Feng, S Yan, H Xi. Linear distance coding for image classification. IEEE Transactions on Image Processing, 2013, 22(2): 537–548 https://doi.org/10.1109/TIP.2012.2218826
28	X Sun, C Wang, C Xu, L Zhang. Indexing billions of images for sketchbased retrieval. In: Proceedings of the ACM Conference on Multimedia. 2013, 233–242 https://doi.org/10.1145/2502081.2502281
29	M Rusińol, D Aldavert, R Toledo, J Lladós. Efficient segmentation-free keyword spotting in historical document collections. Pattern Recognition, 2015, 48(2): 545–555 https://doi.org/10.1016/j.patcog.2014.08.021
30	Y Jiang, Y Jiang, J Wang. VCDB: a large-scale database for partial copy detection in videos. In: Proceedings of the European Conference on Computer Vision. 2014, 357–371 https://doi.org/10.1007/978-3-319-10593-2_24
31	J Luo, W Zhou, J Wu. Image categorization with resource constraints: introduction, challenges and advances. Frontiers of Computer Science, 2017, 11(1): 13–26 https://doi.org/10.1007/s11704-016-5514-6
32	J Revaud, M Douze, C Schmid, H Jégou. 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 https://doi.org/10.1109/CVPR.2013.318
33	N Inoue, K Shinoda. Neighbor-to-neighbor search for fast coding of feature vectors. In: Proceedings of the IEEE International Conference on Computer Vision. 2013, 1233–1240 https://doi.org/10.1109/ICCV.2013.156
34	M Norouzi, D J Fleet. Cartesian k-means. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2013, 3017–3024 https://doi.org/10.1109/CVPR.2013.388
35	Y Kalantidis, Y Avrithis. Locally optimized product quantization for approximate nearest neighbor search. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2014, 2329–2336 https://doi.org/10.1109/CVPR.2014.298
36	T Zhang, C Du, J Wang. Composite quantization for approximate nearest neighbor search. In: Proceedings of the IEEE International Conference on Machine Learning. 2014, 838–846
37	Y Matsui, T Yamasaki, K Aizawa. 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 https://doi.org/10.1109/ICCV.2015.225
38	R Gray. Vector quantization. IEEE ASSP Magazine, 1984, 1(2): 4–9 https://doi.org/10.1109/MASSP.1984.1162229
39	T Kolda, B Bader. Tensor decompositions and applications. SIAM Review, 2009, 51(3): 455–500 https://doi.org/10.1137/07070111X
40	B W Bader, T G Kolda. Algorithm 862: matlab tensor classes for fast algorithm prototyping. ACM Transactions on Mathematical Software, 2006, 32(4): 635–653 https://doi.org/10.1145/1186785.1186794
41	G B Folland. Real Analysis: Modern Techniques and Their Applications. John Wiley and Sons, 2013
42	D Hodges, D Danielson. Nonlinear beam kinematics by decomposition of the rotation tensor. Journal of Applied Mechanics, 1987, 54(2): 258–262 https://doi.org/10.1115/1.3173004

[1]

Article highlights

Download

[1]	Chenggang Clarence YAN,Hongtao XIE,Bing ZHANG,Yanping MA,Qiong DAI,Yizhi LIU. Fast approximate matching of binary codes with distinctive bits[J]. Front. Comput. Sci., 2015, 9(5): 741-750.

Viewed

Full text

Abstract

Cited

Shared

Discussed