Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey

Fei Lun-ke; Qin Jian-yang; Teng Shao-hua; Zhang Wei; Liu Dong-ning; Hou Yan

doi:10.12052/gdutxb.190123

English Version Journal Login

您当前的位置：

首页 >

文章列表页 >

Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey

更新时间：2026-05-27

- Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey
- Vol. 37, Issue 3, Pages: 23-35(2020)
- 作者机构：
  
  广东工业大学计算机学院,广东,广州,510006
- 作者简介：
- 基金信息：
- DOI：10.12052/gdutxb.190123
  CLC： TP391
- Online First：12 May 2020，
  
  Published：2020
- 稿件说明：
移动端阅览
费伦科, 秦建阳, 滕少华, 张巍, 刘冬宁, 侯艳. 近似最近邻大数据检索哈希散列方法综述[J]. 广东工业大学学报, 2020, 37(3): 23-35.

Fei Lun-ke, Qin Jian-yang, Teng Shao-hua, et al. Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey[J]. 2020, 37(3): 23-35.
费伦科, 秦建阳, 滕少华, 张巍, 刘冬宁, 侯艳. 近似最近邻大数据检索哈希散列方法综述[J]. 广东工业大学学报, 2020, 37(3): 23-35. DOI： 10.12052/gdutxb.190123.

Fei Lun-ke, Qin Jian-yang, Teng Shao-hua, et al. Hashing for Approximate Nearest Neighbor Search on Big Data: A Survey[J]. 2020, 37(3): 23-35. DOI： 10.12052/gdutxb.190123.

摘要

近似最近邻检索已成为人工智能时代海量数据快速检索主要技术之一。作为高效的近似最近邻检索方法

哈希散列方法受到广泛关注并且层出不穷。到目前为止还没有文献对主流哈希散列方法进行全面地分析和总结。鉴于此

本文首先系统地介绍哈希散列的基本知识

包括距离计算、损失函数、离散约束和外样本计算等。然后

深入对比分析主流哈希散列算法优缺点

并在主流数据库上进行性能评估。最后

总结哈希散列技术目前存在的问题

并提出若干潜在的哈希散列研究方向。本文对设计高效的哈希散列方法具有重要借鉴意义。

Abstract

Approximate Nearest Neighbor (ANN) search has served as one of the most important technologies for efficient retrieval of large-scale data in the era of artificial intelligence. As a promising solution to the ANN

hashing has received a lot of attention due to its high efficiency and extensive works have been presented in the literature. However

so far

there is no work with attempt to comprehensively analyze and overview the state-of-the-art hashing methods. To address this

the basics of hashing

including distance calculation

loss function

discrete constraint and out-of-sample learning

are first systematically introduced. Then

the state-of-the-art hashing based methods are comparatively studied and experiments on the widely used databases are conducted to evaluate their performance. Finally

the key problems of hashing methods are summarized and some potential research directions are pointed out. It is believed that this endeavor could provide other researches with a useful guideline in designing effective and efficient hashing methods.

关键词

Keywords

references

RUI Y, HUANG T S, CHANG S F. Image retrieval: current techniques, promising directions, and open issues [J]. Journal of Visual Communication and Image Representation, 1999, 10(1): 39-62.

HAR-PELED S, INDYK P, MOTWANI R. Approximate nearest neighbor: towards removing the curse of dimensionality [J]. Theory of Computing, 2012, 8(14): 321-350.

WEBER R, SCHEK H J, BLOTT S. A quantitative analysis and performance study for similarity- search methods in high-dimensional spaces[C]// International Conference on Very Large Data Bases. San Francisco: VLDB, 1998: 194-205.

FRIEDMAN J H, BENTLEY J L, FINKEL R A. An algorithm for finding best matches in logarithmic expected time [J]. ACM Transactions on Mathematical Software, 1977, 3(3): 209-226.

UHLMANN J K. Satisfying general proximity / similarity queries with metric trees [J]. Information Processing Letters, 1991, 40(4): 175-179.

JIANG K, WU G S. Overview of information retrieval technology for Web [J]. Computer Engineering, 2005, 31(24): 7-9.

JÉGOU H, DOUZE M, SCHMID C. Product quantization for nearest neighbor search [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2010, 33(1): 117-128.

KULIS B, DARRELL T. Learning to hash with binary reconstructive embeddings[C]// Advances in Neural Information Processing Systems. Vancouver: NIPS, 2009: 1042-1050

LIU W, WANG J, JI R R, et al. Supervised hashing with kernels[C]// Computer Vision Pattern Recognition. Providence: IEEE, 2012: 2074-2081.

WANG J, KUMAR S, CHANG S F. Sequential projection learning for hashing with compact codes[C]// International Conference on International Conference on Machine Learning. Haifa: ICML, 2010: 1127-1134.

XU B, BU J, LIN Y, et al. Harmonious hashing[C]// International Joint Conference on Artificial Intelligence. Beijing: IJCAI, 2014: 1820-1826.

HE J, LIU W, CHANG S F. Scalable similarity search with optimized kernel hashing[C]// International Conference on Knowledge Discovery Data Mining. Boston: ACM SIGKDD, 2010: 1129-1138.

WEISS Y, TORRALBA A, FERGUS R. Spectral hashing[C]// Advances in Neural Information Processing Systems. Vancouver: NIPS, 2009: 1753–1760.

CARREIRA P M. The elastic embedding algorithm for dimensionality reduction[C]// International Conference on Machine Learning. Haifa: ICML, 2010: 167-174.

SHAKHNAROVICH G, VIOLA P, DARRELL T. Fast pose estimation with parameter-sensitive hashing[C]// International Conference on Computer Vision. Nice: IEEE, 2003: 750.

GONG Y, LAZEBNIK S, GORDO A, et al . Iterative quantization: a procrustean approach to learning binary codes for large-scale image retrieval [J ] . IEEE Transactions on Pattern Analysis Machine Intelligence, 2013, 35(12): 2916-2929.

WOLD S, ESBENSEN K, GELADI P. Principal component analysis [J]. Chemometrics Intelligent Laboratory Systems, 1987, 2(1): 37-52.

LIU W, MU C, KUMAR S, et al. Discrete graph hashing[C]// Advances in Neural Information Processing Systems. Montreal: NIPS, 2014: 3419-3427.

LIU W, WANG J, KUMAR S, et al. Hashing with graphs[C]// International Conference on Machine Learning. Bellevue: ICML, 2011: 1-8.

ZHU X, HUANG Z, CHENG H, et al . Sparse hashing for fast multimedia search [J ] . ACM Transactions on Information Systems, 2013, 31(2): 1-24.

HARDOON D R, SZEDMAK S, SHAWE T J. Canonical correlation analysis: an overview with application to learning methods [J]. Neural Computation, 2004, 16(12): 2639-2664.

GIONIS A, INDYK P, MOTWANI R. Similarity search in high dimensions via hashing[C]// International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers, 1999: 518-529.

DATAR M, IMMORLICA N, INDYK P, et al. Locality-sensitive hashing scheme based on p-stable distributions[C]// Symposium on Computational Geometry. Brooklyn: SCG, 2004: 253-262.

KULIS B, GRAUMAN K. Kernelized locality-sensitive hashing for scalable image search[C]// International Conference on Computer Vision. Kyoto: IEEE, 2009: 2130- 2137.

林悦. 基于哈希算法的高维数据的最近邻检索[D]. 杭州: 浙江大学, 2013.

SU Y J, YU H, LEI C, et al . PCA hashing for image data retrieval [J ] . Application Research of Computers, 2018, 35(10): 3147-3150.

BODÓ Z, CSATÓ L. Linear spectral hashing [J]. Neurocomputing, 2014, 141: 117-123.

XIA L C, JIANG J G, QI M B. A large-scale image retrieval method based on improved spectral hashing [J]. Journal of Hefei University of Technology (Natural Science), 2016, 39(8): 1049-1054.

KIM S, CHOI S. Multi-view anchor graph hashing[C]// International Conference on Acoustics, Speech and Signal Processing. Vancouver: IEEE, 2013: 3123-3127.

吕成钢. 面向大规模图片搜索的基于锚图哈希的半监督度量学习算法[D]. 南京: 南京邮电大学, 2018.

TAKEBE H, UEHARA Y, UCHIDA S. Efficient anchor graph hashing with data-dependent anchor selection [J]. IEICE Transactions on Information and Systems, 2015, E98-(11): 2030-2033.

ZHAO S, LI Y S. Image retrieval based on random rotation locality preserving hashing [J]. Advanced Engineering Sciences, 2019, 51(2): 144-150.

CARREIRA P M A, RAZIPERCHIKOLAEI R. Hashing with binary autoencoders[C]// Computer Vision Pattern Recognition. Boston: IEEE, 2015: 557-566.

KONG W, LI W J. Isotropic hashing[C]// International Conference on Neural Information Processing Systems. Vancouver: NIPS, 2012: 1646-1654.

XIA Y, HE K, KOHLI P, et al. Sparse projections for high-dimensional binary codes[C]// Computer Vision Pattern Recognition. Boston: IEEE, 2015: 3332-3339.

徐盼盼. 基于哈希学习的图像检索方法研究[D].沈阳: 沈阳工业大学, 2019.

ZHENG M, BU J, CHEN C, et al . Graph regularized sparse coding for image representation [J ] . IEEE Transactions on Image Processing, 2011, 20(5): 1327-1336.

DING G, ZHOU J, GUO Y, et al . Large-scale image retrieval with sparse embedded hashing [J ] . Neurocomputing, 2017, 257: 24-36.

LAI Z H, CHEN Y D, WU J, et al . Jointly sparse hashing for image retrieval [J ] . IEEE Transactions on Image Processing, 2018, 27(12): 6147-6158.

HU M, YANG Y, SHEN F M, et al . Hashing with angular reconstructive embeddings [J ] . IEEE Transactions on Image Processing, 2018, 27(2): 545-555.

HU D, NIE F P, LI X L. Discrete spectral hashing for efficient similarity retrieval [J]. IEEE Transactions on Image Processing, 2019, 28(3): 1080-1091.

LECUN Y, BOTTOU L, BENGIO Y, et al . Gradient-based learning applied to document recognition [J ] . Proceedings of the IEEE, 1998, 86(11): 2278-2324.

KRIZHEVSKY A, HINTON G. Learning multiple layers of features from tiny images[R].[S.l.: s.n.], 2009.

KINNUNEN T, KAMARAINEN J, LENSU L, et al. Making visual object categorization more challenging: randomized Caltech-101 data set[C]// International Conference on Pattern Recognition. Istanbul: IEEE, 2010: 476- 479.

XIAO J, HAYS J, EHINGER K A, et al. SUN database: large-scale scene recognition from abbey to zoo[C]// Computer Vision Pattern Recognition. San Francisco: IEEE, 2010: 3485-3492.

WOLF L, HASSNER T, MAOZ I. Face recognition in unconstrained videos with matched background similarity[C]// Computer Vision Pattern Recognition. Colorado: IEEE, 2011: 529-534.

CHUA T S, TANG J, HONG R, et al. NUS-WIDE: a real-world web image database from National University of Singapore[C]// International Conference on Image Video Retrieval. Santorini: CIVR, 2009: 48.

TORRALBA A, MURPHY K P, FREEMAN W T, et al. Context-based vision system for place and object recognition[C]// International Conference on Computer Vision. Nice: IEEE, 2008: 273-280.

LOWE D G. Object recognition from local scale-invariant features[C]// International Conference on Computer Vision. Kerkyra: IEEE, 1999: 1150-1157.

GONG Y, WANG L, GUO R, et al. Multi-scale orderless pooling of deep convolutional activation features[C]// European Conference on Computer Vision. Zurich: ECCV, 2014: 392-407.

OJALA T, PIETIKAINEN M, MAENPAA T. Multiresolution gray-scale and rotation invariant texture classification with local binary patterns [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(7): 971-987.

LI X, HU D, NIE F P. Large graph hashing with spectral rotation[C]//Thirty-First AAAI Conference on Artificial Intelligence. San Francisco: AAAI, 2017: 2203-2209.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Ground Deformation Monitoring and Influencing Factors Analysis in Fuzhou City Based on PSI Technology

Research on Foreign Object Detection in Power Transmission Lines Based on the AAGV-YOLOX Model

Robust Design for Artificial Noise-assisted UAV Terahertz Secure Communication

Bimodal Iterative Cross-attention Fusion Ensemble Framework

Efficient Temporal Modeling for RGB-T Tracking

Related Author

No data

Related Institution

No data

AI问答

⁰