Spherical Bitwise Weighted Hamming Distance Method

© 2020 by IJCTT Journal
Volume-68 Issue-7
Year of Publication : 2020
Authors : Zhen Wang, Baomin Shao
DOI :  10.14445/22312803/IJCTT-V68I7P108

How to Cite?

Zhen Wang, Baomin Shao, "Spherical Bitwise Weighted Hamming Distance Method," International Journal of Computer Trends and Technology, vol. 68, no. 7, pp. 49-55, 2020. Crossref, https://doi.org/10.14445/22312803/IJCTT-V68I7P108

In recent years, hashing algorithms which can map floating point data into compact binary code are adopted to achieve the approximate nearest neighbor (ANN) search task in the Hamming space. However, binary codes are discrete integer value, which makes the data pairs with different binary codes would share the same Hamming distance. To solve the above problem, spherical bitwise weighted Hamming distance (SBWHD) method is proposed to assign different weight values to each binary bit. Thus, the weighted Hamming distance can be utilized to distinguish the ranking orders among the data points which have the same Hamming distance to the query sample. As the ANN search task mainly focus on the samples at the top position of retrieval results, SBWHD learns the hashing and bitwise weight functions which obey a spherical distribution. During the training process, the similarity threshold is considered as radius and the nearest neighbors are put inside the spherical. To further guarantee the ANN search performance, both the Hamming distance and the weighted Hamming distance are required to approximate the corresponding Euclidean distance. During the training process, SBWHD simultaneously learns the hashing functions and bitwise weight functions by an iterative optimization mechanism. When the algorithm converges, the bitwise weights can effectively improve the ANN search performance obtained based on the binary codes. The final comparative experiments in three large scale datasets prove that the ANN search performance of SBWHD is superior.

approximate nearest neighbor search, binary code, hashing algorithm, bitwise weight method.

[1] R. Kang, Y. Cao, M. Long, J. Wang and P. S. Yu, "Maximum-Margin Hamming Hashing," in Proc. ICCV’19, 2019, pp. 8251.
[2] Z. Wang, F. Sun, L. Zhang and P. P. Liu, "Minimal residual ordinal loss hashing with an adaptive optimization mechanism," EURASIP Journal on Image and Video Processing, vol. 2020, pp.1-11, Mar. 2020.
[3] Z. Wang, F. Sun, L. Zhang and L. Wang, "Top position sensitive ordinal relation preserving bitwise weight for image retrieval," Algorithms, vol. 13, pp. 18, Jan. 2020.
[4] Z. Wang, L. Zhang, F. Sun, L. Wang and S. Liu, "Relative similarity preserving bitwise weights generated by an adaptive mechanism," Multimedia Tools and Applications, vol. 78, pp. 24453-24472, Jan. 2019.
[5] M. Datar, N. Immorlica, P. Indyk and V. S. Mirrokni, "Locality-sensitive hashing scheme based on p-stable distributions" in Proc. [C]. SCG’20, 2004, pp. 253-262.
[6] Y. Weiss, A. Torralba and R. Fergus, "Spectral hashing," in Proc. NIPS, 2008, pp. 1753-1760.
[7] Y. Gong and S. Lazebnik, "Iterative Quantization: A procrustean approach to learning binary codes," in Proc. CVPR, 2011, pp. 817-824.
[8] W. Liu, J. Wang, S. Kumar and S. F. Chang, "Hashing with graphs," in Proc. ICML’ 28, 2011, pp. 1-8.
[9] K. He, F. Wen and J. Sun, "K-means hashing: an affinity-preserving quantization method for learning binary compact codes," in Proc. CVPR, 2013, pp. 2938-2945.
[10] M. Norouzi and D. J. Fleet, "Minimal loss hashing for compact binary codes," in Proc. ICML’28, 2011, pp. 353-360.
[11] J. Wang, W. Liu, A. X. Sun and Y. G. Jiang, "Learning hash codes with listwise supervision," in Proc. ICCV, 2013, pp. 3032-3039.
[12] J. Wang, J. Wang, N. Yu, and S. Li, "Order preserving hashing for approximate nearest neighbor search," in Proc. ICM’21, 2013, pp. 133-142.
[13] L. Zhang, Y. Zhang, J. Tang, K. Lu and Q. Tian, "Binary code ranking with weighted hamming distance," in Proc. CVPR, 2013, pp. 1586-1593.
[14] T. Ji, X. Liu, C. Deng, L. Huang, and B. Lang, "Query-Adaptive Hash Code Ranking for Fast Nearest Neighbor Search," in Proc. ICM, 2014, pp. 1005-1008.
[15] H. Fu, X. Kong, and Z. Wang, "Binary code reranking method with weighted hamming distance," Multimedia Tools and Applications, vol. 75, pp. 1391-1408, 2016.
[16] X. Wang, Y. Shi, and K. M. Kitani, "Deep Supervised Hashing with Triplet Labels," in Proc. ACCV, 2016, pp. 70-84.
[17] F. Cakir and S. Sclaroff, "Adaptive Hashing for Fast Similarity Search," in Proc. CVPR, 2015, pp. 1044-1052.
[18] Dr. M E Purushoththaman, Dr. Bhavani Buthtkuri, "Effective Multiple Verification Process Ensuring Security And Data Accuracy In Cloud Environment Storage" SSRG International Journal of Computer Science and Engineering 6.7 (2019)