Fast approximate matching of binary codes with distinctive bits

Abstract

Although the distance between binary codes can be computed fast in Hamming space, linear search is not practical for large scale datasets. Therefore attention has been paid to the efficiency of performing approximate nearest neighbor search, in which hierarchical clustering trees (HCT) are widely used. However, HCT select cluster centers randomly and build indexes with the entire binary code, this degrades search performance. In this paper, we first propose a new clustering algorithm, which chooses cluster centers on the basis of relative distances and uses a more homogeneous partition of the dataset than HCT has to build the hierarchical clustering trees. Then, we present an algorithm to compress binary codes by extracting distinctive bits according to the standard deviation of each bit. Consequently, a new index is proposed using compressed binary codes based on hierarchical decomposition of binary spaces. Experiments conducted on reference datasets and a dataset of one billion binary codes demonstrate the effectiveness and efficiency of our method.

Keywords

binary codes / approximate nearest neighbor search / hierarchical clustering index

References

[1] Zhang W, Gao K, Zhang Y, Li J. Efficient approximate nearest neighbor search with integrated binary codes. In: Proceedings of ACM International Conference on Multimedia. 2011, 1189−1192

[2] Chu W, Li C, Tseng S. Travelmedia: an intelligent management system for media captured in travel. Journal of Visual Communication and Image Representation, 2011, 22(1): 93−104

[3] Wang M, Li H, Tao D, Lu K, Wu X. Multimodal graph-based reranking for Web image search. IEEE Transactions on Image Processing, 2012, 21(11): 4649−4661

[4] Wang M, Li G, Lu Z, Gao Y, Chua T. When amazon meets google: product visualization by exploring multiple Web sources. ACM Transactions on Internet Technology, 2013, 12(4): 12

[5] Zhang Y, Yan C, Dai F, Ma Y. Efficient parallel framework for H.264/AVC deblocking filter on many-core platform. IEEE Transactions on Multimedia, 2012, 14(3): 510−524

[6] Yan C, Zhang Y, Xu J, Dai F, Li L, Dai Q, Wu F. A highly parallel framework for HEVC coding unit partitioning tree decision on manycore processors. IEEE Signal Processing letters, 2014, 21(5): 573−576

[7] Yan C, Zhang Y, Xu J, Dai F, Zhang J, Dai Q, Wu F. Efficient parallel framework for HEVC motion estimation on many-core processors. IEEE Transactions on Circuits and Systems for Video Technology, 2014, 24(12): 2077−2089

[8] Torralba A, Fergus R, Weiss Y. Small codes and large image databases for recognition. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2008, 1−8

[9] Zhang L, Zhang Y, Tang J, Gu X, Li J, Tian Q. Topology preserving hashing for similarity search. In: Proceedings of ACM International Conference on Multimedia. 2013, 123−132

[10] Xie H, Zhang Y, Tan J, Guo L, Li J. Contextual query expansion for image retrieval. IEEE Transactions on Multimedia, 2014, 16(4): 1104−1114

[11] Salakhutdinov R, Hinton G. Semantic hashing. International Journal of Approximate Reasoning, 2009, 50(7): 969−978

[12] Strecha C, Bronstein A, Bronstein M, Fua P. LDAHash: improved matching with smaller descriptors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(1): 66−78

[13] Rublee E, Rabaud V, Konolige K, Bradski G. ORB: an efficient alternative to SIFT or SURF. In: Proceedings of IEEE International Conference on Computer Vision. 2011, 2564−2571

[14] Norouzi M, Punjani A, Fleet D J. Fast search in hamming space with multi-index hashing. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2012: 3108−3115

[15] Muja M, Lowe D G. Fast matching of binary features. In: Proceedings of Computer and Robot Vision. 2012: 404−410

[16] Muja M, Lowe D G. Flann, fast library for approximate nearest neighbors. https://www.cs.ubc.ca/FLANN

[17] Zitnick C L. Binary coherent edge descriptors. Computer Vision− ECCV 2010. Springer Berlin Heidelberg, 2010, 170−182

[18] Weiss Y, Torralba A, Fergus R. Spectral hashing. In: Proceedings of Advances in Neural Information Processing Systems. 2008, 1753−1760

[19] Yeung R W. Information Theory and Network Coding. Springer, 2008

[20] Ou M, Cui P, Wang F, Wang J, Zhu W, Yang S. Comparing apples to oranges: a scalable solution with heterogeneous hashing. In: Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2013, 230−238

[21] Wei Y, Song Y, Zhen Y, Liu B, Yang Q. Scalable heterogeneous translated hashing. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and DataMining. 2014, 791−800

[22] Liu S, Cui P, Zhu W, Yang S, Tian Q. Social embedding image distance learning. In: Proceedings of the ACM International Conference on Multimedia. 2014, 617−626

[23] Zhang L, Zhang Y, Tang J, Tang J, Lu K, Tian Q. Binary code ranking with weighted hamming distance. In: Proceedings of 2013 IEEE Conference on Computer Vision and Pattern Recognition. 2013, 1586−1593

[24] 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

[25] Gong Y, Lazebnik S. Iterative quantization: A procrustean approach to learning binary codes. In: Proceedings of 2011 IEEE Conference on Computer Vision and Pattern Recognition. 2011, 817−824

[26] Heo J P, Lee Y, He J, Chang S, Yoon S. Spherical hashing. In: Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). 2012, 2957−2964

[27] Li P, Wang M, Cheng J, Xu C, Lu H. Spectral hashing with semantically consistent graph for image indexing. IEEE Transactions on Multimedia, 2013, 15(1): 141−152

[28] Esmaeili M M, Ward R K, Fatourechi M. A fast approximate nearest neighbor search algorithm in the hamming space. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(12): 2481−2488

[29] Zhang X, Qin J, Wang W, Hmsearch: An efficient hamming distance query processing algorithm. In: Proceedings of the 25th International Conference on Scientific and Statistical Database Management. 2013, 19

[30] Aly M, Munich M, Perona P. Distributed kd-trees for retrieval from very large image collections. In: Proceedings of British Machine Vision Conference. 2011

[31] Babenko A, Lempitsky V. The inverted multi-index. In: Proceedings of 2012 IEEE Conference on Computer Vision and Pattern Recognition. 2012, 3069−3076

[32] Silpa-Anan C, Hartley R. Optimised KD-trees for fast image descriptor matching. In: Proceedings of IEEE Conference on Computer Vision and Pattern Recognition. 2008, 1−8

[33] Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing. In: Proceedings of the International Conference on Very Large Data Bases. 1999, 99: 518−529

[34] Broder, A.Z. On the resemblance and containment of documents. In: Proceedings of IEEE Compression and Complexity of Sequences. 1997, 21−29

[35] Park H S, Jun C H. A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications, 2009, 36(2): 3336−3341

[36] Bland J M, Altman D G. Statistics notes: measurement error. BMJ, 1996, 312(7047): 1654

[37] Jégou H, Douze M, Schmid C. Improving bag-of-features for large scale image search. International Journal of Computer Vision, 2010, 87(3): 316−336

[38] Yan C, Zhang Y, Dai F, Wang X, Li L, Dai Q. Parallel deblocking filter for HEVC on many-core processor. Electronics Letters, 2014, 50(5): 367−368

[39] Yan C, Zhang Y, Dai F, Li L. Highly parallel framework for HEVC motion estimation on many-core platform. In: Proceedings of Data Compression Conference. 2013, 63−72

[40] Yan C, Dai F, Zhang Y, Ma Y. Parallel deblocking filter for H.264/AVC implemented on Tile64 Platform. In: Proceedings of International Conference on Multimedia and Expo. 2011, 1−6

[41] Yan C, Zhang Y, Dai F, Zhang J, Li L, Dai Q. Efficient parallel HEVC intra prediction on many-core processor. Electronics Letters, 2014, 50(11): 805−806

RIGHTS & PERMISSIONS

2015 Higher Education Press and Springer-Verlag Berlin Heidelberg