Skip to main content
Log in

Incremental hashing with sample selection using dominant sets

  • Original Article
  • Published:
International Journal of Machine Learning and Cybernetics Aims and scope Submit manuscript

Abstract

In the world of big data, large amounts of images are available in social media, corporate and even personal collections. A collection may grow quickly as new images are generated at high rates. The new images may cause changes in the distribution of existing classes or the emergence of new classes, resulting in the collection being dynamic and having concept drift. For efficient image retrieval from an image collection using a query, a hash table consisting of a set of hash functions is needed to transform images into binary hash codes which are used as the basis to find similar images to the query. If the image collection is dynamic, the hash table built at one time step may not work well at the next due to changes in the collection as a result of new images being added. Therefore, the hash table needs to be rebuilt or updated at successive time steps. Incremental hashing (ICH) is the first effective method to deal with the concept drift problem in image retrieval from dynamic collections. In ICH, a new hash table is learned based on newly emerging images only which represent data distribution of the current data environment. The new hash table is used to generate hash codes for all images including old and new ones. Due to the dynamic nature, new images of one class may not be similar to old images of the same class. In order to learn new hash table that preserves within-class similarity in both old and new images, incremental hashing with sample selection using dominant sets (ICHDS) is proposed in this paper, which selects representative samples from each class for training the new hash table. Experimental results show that ICHDS yields better retrieval performance than existing dynamic and static hashing methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Hong L, Ji RR, Wang JD, Shen CH (2019) Ordinal constraint binary coding for approximate nearest neighbor search. IEEE Trans Pattern Anal Mach Intell 41(4):941–955

    Article  Google Scholar 

  2. Huang LK, Yang Q, Zheng WS (2013) Online hashing. In: International joint conference on artificial intelligence, pp 1422–1428

  3. Leng C, Wu JX, Cheng J, Bai X, Lu HQ (2015) Online sketching hashing. Proc IEEE Comput Soc Conf Comput Vis Pattern Recognit 7–12:2503–2511

    Google Scholar 

  4. Ng WWY, Tian X, Lv YM, Yeung DS, Pedrycz W (2017) Incremental hashing for semantic image retrieval in nonstationary environments. IEEE Trans Cybern 47(11):3814–3826

    Google Scholar 

  5. Mayur D, Indyk P, Immorlica N, Mirrokni VS (2004) Locality-sensitive hashing scheme based on P-stable distributions. In: Proceedings of the annual symposium on computational geometry, pp 253–262

  6. Brian K, Grauman K (2012) Kernelized locality-sensitive hashing. IEEE Trans Pattern Anal Mach Intell 34(6):1092–1104

    Article  Google Scholar 

  7. Yair W, Torralba A, Fergus R (2009) Spectral hashing. In: International conference on neural information processing systems, pp 1753–1760

  8. Gong YC, Svetlana L, Albert G, Florent P (2013) Iterative quantization: a procrustean approach to learning binary codes for large-scale image retrieval. IEEE Trans Pattern Anal Mach Intell 35(12):2916–2929

    Article  Google Scholar 

  9. Shen FM, Liu W, Zhang ST, Yang Y, Shen HT (2015) Learning binary codes for maximum inner product search. In: IEEE international conference on computer vision, pp 4148–4156

  10. Liu XL, Mu YD, Zhang DC, Lang B, Li XL (2015) Large-scale unsupervised hashing with shared structure learning. IEEE Trans Cybern 45(9):1811–1822

    Article  Google Scholar 

  11. Lopamudra M, Sathya RN, Vamsi IK, Tyler H, Vikas S (2015) An NMF perspective on binary hashing. In: IEEE international conference on computer vision, pp 4184–4192

  12. Liu XL, Huang L, Deng C, Lang B, Tao DC (2016) Query-adaptive hash code ranking for large-scale multi-view visual search. IEEE Trans Image Process 25(10):4514–4524

    Article  MathSciNet  Google Scholar 

  13. Liu W, Wang J, Ji RR, Jiang YG, Chang SF (2012) Supervised hashing with kernels. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp 2074–2081

  14. Song DJ, Liu W, Ji RR, David MA, John RS (2015) Top rank supervised binary coding for visual search. In: IEEE international conference on computer vision, pp 1922–1930

  15. Shen FM, Shen CH, Liu W, Shen HT (2015) Supervised discrete hashing. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp 37–45

  16. Gui J, Liu TL, Sun ZN, Tao DC, Tan TN (2018) Fast supervised discrete hashing. IEEE Trans Pattern Anal Mach Intell 40(2):490–496

    Article  Google Scholar 

  17. Cheng KW, Li WJ, Zhou ZH (2016) Column sampling based discrete supervised hashing. In: Thirtieth AAAI conference on artificial intelligence, pp 1230–1236

  18. Jiang QY, Cui X, Li WJ (2018) Deep discrete supervised hashing. IEEE Trans Image Process 27(12):5996–6009

    Article  MathSciNet  Google Scholar 

  19. Wang J, Kumar S, Chang SF (2012) Semi-supervised hashing for large-scale search. IEEE Trans Pattern Anal Mach Intell 34(12):2393–2406

    Article  Google Scholar 

  20. Wang J, Kumar S, Chang SF (2010) Sequential projection learning for hashing with compact codes. In: Proceedings of the international conference on machine learning, pp 127–1134

  21. Wu CX, Zhu JK, Cai D, Chen C, Bu JJ (2013) Semi-supervised nonlinear hashing using bootstrap sequential projection learning. IEEE Trans Knowl Data Eng 25(6):1380–1393

    Article  Google Scholar 

  22. Ng WWY, Lv YM, Zeng ZQ, Yeung DS, Chan PPK (2017) Sequential conditional entropy maximization semi-supervised hashing for semantic image retrieval. Int J Mach Learn Cybern 8(2):571–586

    Article  Google Scholar 

  23. Li P, Cheng J, Lu HQ (2013) Hashing with dual complementary projection learning for fast image retrieval. Neurocomputing 120:83–89

    Article  Google Scholar 

  24. Zhang CH, Zheng WS (2017) Semi-supervised multi-view discrete hashing for fast image search. IEEE Trans Image Process 26(6):2604–2617

    Article  MathSciNet  Google Scholar 

  25. Ng WWY, Zhou XC, Tian X, Wang XZ, Yeung DS (2018) Bagging–boosting-based semi-supervised multi-hashing with query-adaptive re-ranking. Neurocomputing 27:916–923

    Article  Google Scholar 

  26. Ng WWY, Li JC, Feng SY, Yeung DS, Chan PPK (2015) Sensitivity based image filtering for multi-hashing in large scale image retrieval problems. Int J Mach Learn Cybern 6(5):777–794

    Article  Google Scholar 

  27. Zhang J, Peng YX (2019) SSDH: semi-supervised deep hashing for large scale image retrieval. IEEE Trans Circuits Syst Video Technol 29(1):212–225

    Article  MathSciNet  Google Scholar 

  28. Huang LK, Yang Q, Zheng WS (2018) Online hashing. IEEE Trans Neural Netw Learn Syst 29(6):2309–2322

    Article  MathSciNet  Google Scholar 

  29. Cakir F, He S, Bargal A, Sclaroff S (2017) MIHash: online hashing with mutual information. In: IEEE international conference on computer vision, pp 437–445

  30. Weng ZY, Zhu YS (2019) Online supervised sketching hashing for large-scale image retrieval. IEEE Access 7:88369–88379

    Article  Google Scholar 

  31. Cakir F, Sclaroff S (2015) Online supervised hashing. IEEE Int Conf Image Process 2015:2606–2610

    Google Scholar 

  32. Cakir F, Sclaroff S (2015) Adaptive hashing for fast similarity search. In: IEEE international conference on computer vision, pp 1044–1052

  33. Ng WWY, Tian X, Pedrycz W, Wang XZ, Yeung DS (2019) Incremental hash-bit learning for semantic image retrieval in nonstationary environments. IEEE Trans Cybern 49(11):3844–3858

    Article  Google Scholar 

  34. Liu XL, He JF, Lang B, Chang SF (2013) Hash bit selection: a unified solution for selection problems in hashing. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, pp 1570–1577

  35. Jhuo IH, Weng L, Cheng WH, Lee DT (2016) A feature fusion framework for hashing. In: International conference on pattern recognition, pp 2288–2293

  36. Pavan M, Pelillo M (2003) A new graph-theoretic approach to clustering and segmentation. In: Proceedings of the IEEE computer society conference on computer vision and pattern recognition, vol 1, pp I–I

  37. Pavan M, Pelillo M (2007) Dominant sets and pairwise clustering. IEEE Trans Pattern Anal Mach Intell 29(1):167–172

    Article  Google Scholar 

  38. Jiang XX, Ng WWY, Tian X, Kwong S, Wang H (2019). Incremental hashing with undersampling. In: IEEE international conference on systems, man, and cybernetics, pp 616–622

Download references

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China under Grants 61876066, 61772344, and 61672443, the Guangzhou Science and Technology Plan Project under Grant 201804010245, Guangdong Province Science and Technology Plan Project (Collaborative Innovation and Platform Environment Construction) 2019A050510006, EU Horizon 2020 Programme (700381, ASGARD), and the Hong Kong RGC General Research Funds under Grants 9042489 (CityU 11206317), 9042816 (CityU 11209819) and 9042322 (CityU 11200116).

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Xing Tian.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Ng, W.W.Y., Jiang, X., Tian, X. et al. Incremental hashing with sample selection using dominant sets. Int. J. Mach. Learn. & Cyber. 11, 2689–2702 (2020). https://doi.org/10.1007/s13042-020-01145-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13042-020-01145-z

Keywords

Navigation