数据依赖的多索引哈希算法

doi:10.3969/j.issn.1001-2400.2015.04.026

Abstract

Abstract:

The multi-index hashing (MIH) is the state-of-the-art method for indexing binary codes. However, it is based on the dataset codes uniform distribution assumption, and will lower efficiency in dealing with non-uniformly distributed codes. In this paper, we propose a data-oriented multi-index hashing method. We first compute the correlations between bits and learn adaptive projection vector for each binary substring. Then, instead of using substrings as direct indices into hash tables, we project them with corresponding projection vectors to generate new indices. With adaptive projection, the indices in each hash table are nearly uniformly distributed. Besides, we put forward an entropy based measurement to evaluate the distribution of data items in each hash table. Experiments conducted on reference large scale datasets show that compared to the MIH the time performance of our method can be 36.9％～87.4％ better .

Key words: nearest neighbor search, binary codes, indexing, multi-index Hashing

CLC Number:

TP391

MA Yanping;JI Guangrong;ZOU Hailin;XIE Hongtao. Data-oriented multi-index Hashing[J].J4, 2015, 42(4): 159-164.

References

［1］ Zhang W, Gao K, Zhang Y D, et al. Efficient Approximate Nearest Neighbor Search with Integrated Binary Codes［C］//Proceedings of the ACM Multimedia Conference and Co-located Worksops. New York: ACM, 2011: 1189-1192.
［2］ Xie H T, Zhang Y D, Gao K, et al. Contextual Query Expansion for Image Retrieval［J］. IEEE Transactions on Multimedia, 2014, 16(4): 1104-1114.
［3］何周灿, 王庆, 杨恒. 图像特征匹配中一种快速关键维过滤搜索算法［J］. 西安电子科技大学学报, 2010, 37(3): 534-540.
He Zhoucan, Wang Qing, Yang Heng. Key Dimension Filtering Based Search Algorithm of B+Tree for Image Feature Matching［J］. Journal of Xidian University, 2010, 37(3): 534-540.
［4］ Xie H T, Zhang Y D, Gao K, et al. Robust Common Visual Pattern Discovery Using Graph Matching［J］. Journal of Visual Communication and Image Representation, 2013, 24(5): 635-646.
［5］ Zhang L, Zhang Y D, Tian J H, et al. Topology Preserving Hashing for Similarity Search ［C］//Proceedings of the ACM International Multimedia Conference. New York: ACM, 2013: 123-132.
［6］ Salakhutdinov R, Hinton G. Semantic Hashing［J］. International Journal of Approximate Reasoning, 2009, 50(7): 969-978.
［7］ Strecha C, Bronstein A, Bronstein M, et al. LDAHash: Improved Matching With Smaller Descriptors［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 34(1): 66-78.
［8］ Rublee E, Rabaud V, Konolige K, et al. ORB: an Efficient Alternative to SIFT or SURF［C］//IEEE International Conference on Computer Vision. Piscataway: IEEE, 2011: 2564-2571.
［9］ Norouzi M, Punjani A, Fleet D J. Fast Search in Hamming Space with Multi-index Hashing［C］//IEEE Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE, 2012: 3108-3115.
［10］ Weiss Y, Torralba A, Fergus R. Spectral Hashing［J］. Advances in Neural Information Processing Systems, 2008, 21: 1753-1760.
［11］ Wan J, Tong S, Zhang Y D, et al. Data Driven Multi-index Hashing［C］//IEEE International Conference on Image Processing. Piscataway: IEEE Computer Society, 2013: 2670-2673.
［12］ Jolliffe I T. Principal Component Analysis［M］. Second Edition. New York: Springer, 2002.
［13］ Jegou H, Douze M, Schmid C. Product Quantization for Nearest Neighbor Search［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(1): 117-128.
［14］ Lowe D G. Distinctive Image Features from Scale-Invariant Key Points［J］. International Journal of Computer Vision, 2004, 60(2): 91-110.

[1]	YUAN Tong;LIU Zhijing;LIU Hui. Optimizing the parallel adaptive indexing algorithm on multi-core CPUs [J]. Journal of Xidian University, 2016, 43(5): 57-62.
[2]	WANG Xiumei;DING Lijie;GAO Xinbo. Linear embedding Hashing method in preserving similarity [J]. J4, 2016, 43(1): 94-98.
[3]	CUI Jiang-tao;GUO Yong;LI Guang-xin. Efficient video indexing method using dynamic distance measure for the principal component [J]. J4, 2009, 36(6): 1086-1091.
[4]	CUI Jiang-tao(1);SUN Jun-ding(1;2);ZHOU Li-hua(1). An efficient high-dimensional image indexing method for relevance feedback [J]. J4, 2006, 33(1): 62-65.
[5]	CUI Jiang-tao;SUN Jun-ding;ZHOU Li-hua. A multi-resolution indexing method for high-dimensional image databases using the wavelet transform [J]. J4, 2005, 32(3): 370-373.

Data-oriented multi-index Hashing

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 5

Metrics

Comments

Recommended 10