Density Peak Hashing

International Journal of Computer Science and Engineering

© 2020 by SSRG - IJCSE Journal

Volume 7 Issue 8

Year of Publication : 2020

Authors : Zhen Wang, Fuzhen Sun, Baomin Shao

10.14445/23488387/IJCSE-V7I8P101

How to Cite?

Zhen Wang, Fuzhen Sun, Baomin Shao, "Density Peak Hashing," SSRG International Journal of Computer Science and Engineering , vol. 7,  no. 8, pp. 1-7, 2020. Crossref, https://doi.org/10.14445/23488387/IJCSE-V7I8P101

Abstract:

Hashing algorithms can map the floating-point data into compact binary code, and it can fast respond to the ANN search task according to the Hamming distance. The main idea of hashing algorithms is to cluster the data points into different groups and assign binary codes. Generally, many
existing hashing algorithms adopt the K-means clustering algorithm to divide the data points into different clusters. K-means clustering algorithm learns the clustering results according to the Euclidean distances among data points, and clusters the data points with small distances to a center into
the same group. Therefore, the K-means clustering algorithm is not applicable to the data with the nonspherical distribution. To solve this problem, this
paper proposes to compute the clustering groups based on density peaks and learns the binary codes according to the obtained cluster groups, which can make the encoding results well adaptive to data distribution. Furthermore, a two-step mechanism is adopted to learn the linear hashing functions which can recompute the above binary encoding results. To effectively reduce the training time complexity in this paper, only cluster centers are involved in the training process. While learning the hashing functions, the cluster centers’ binary codes are demanded to preserve the Hamming space's
Euclidean similarity relationship. Thus, the data pairs’ Hamming distances can approximate their Euclidean distance. The comparative ANN search experiments in three image datasets show that the proposed density peak hashing (DPH) can achieve an excellent performance.

Keywords:

Hashing algorithms, Approximate nearest neighbor search, Density peak, Binary code

References:

[1] 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.
[2] 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.
[3] 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.
[4] R. Kang, Y. Cao, M. Long, J. Wang and P. S. Yu, "Maximum-Margin Hamming Hashing," in Proc. ICCV’19, 2019, pp. 8251.
[5] X. Luo, P. F. Zhang, Z. Huang, L. Nie, and X. S. Xu, "Discrete Hashing with Multiple Supervision," IEEE Transactions on Image Processing, vol. 28, pp. 2962-2975, Jan. 2019.
[6] G. Wu, J. Han, Y. Guo, L. Liu, and G. Ding, "Unsupervised Deep Video Hashing via Balanced Code for Large-Scale Video Retrieval," IEEE Transactions on Image Processing, vol. 28, pp. 1993-2007, 2019.
[7] C. Yue, B. Liu, M. Long, and J. Wang, "HashGAN: Deep Learning to Hash with Pair Conditional Wasserstein GAN," in Proc. CVPR, 2018, pp. 1287-1296.
[8] H. Liu, R. Ji, J. Wang, and C. Shen, "Ordinal Constraint Binary Coding for Approximate Nearest Neighbor Search," IEEE Transactions on Pattern Analysis & Machine Intelligence, vol. PP, pp. 1-1, 2018.
[9] 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.
[10] Y. Weiss, A. Torralba and R. Fergus, "Spectral hashing," in Proc. NIPS, 2008, pp. 1753-1760.
[11] Y. Gong and S. Lazebnik, "Iterative Quantization: A procrustean approach to learning binary codes," in Proc. CVPR, 2011, pp. 817-824.
[12] K. He, F. Wen and J. Sun, "K-means hashing: an affinitypreserving quantization method for learning binary compact codes," in Proc. CVPR, 2013, pp. 2938-2945.
[13] W. Liu, J. Wang, S. Kumar and S. F. Chang, "Hashing with graphs," in Proc. ICML’ 28, 2011, pp. 1-8.
[14] Y. Matsushita and T. Wada, "Principal component hashing: An accelerated approximate nearest neighbor search," in Proc. PSIVT, 2019, pp. 374-385.
[15] A. Rodriguez and A. Laio, "Clustering by fast search and find of density peaks," Science, vol. 344, pp. 1492-1496, Jun 2014.
[16] A. Oliva and A. Torralba, "Modeling the shape of the scene: A holistic representation of the spatial envelope," International journal of computer vision, vol. 42, pp. 145-175, May, 2001.
[17] X. Wang, Y. Shi, and K. M. Kitani, "Deep Supervised Hashing with Triplet Labels," in Proc. ACCV, 2016, pp. 70-84.
[18] F. Cakir and S. Sclaroff, "Adaptive Hashing for Fast Similarity Search," in Proc. CVPR, 2015, pp. 1044-1052.
[19] Pooja Goyal, Sushil Kumar, Komal Kumar Bhatia, "Hashing And Clustering Based Novelty Detection" SSRG International Journal of Computer Science and Engineering 6.6 (2019): 1-9.