Fast Search of Binary Codes with Distinctive Bits

详细信息    查看全文

• 作者：Yanping Ma (21)
  Hongtao Xie (22)
  Zhineng Chen (23)
  Qiong Dai (22)
  Yinfei Huang (24)
  Guangrong Ji (21)
  
• 关键词：binary codes ; approximate nearest neighbor search ; binary indexing
• 刊名：Lecture Notes in Computer Science
• 出版年：2014
• 出版时间：2014
• 年：2014
• 卷：8879
• 期：1
• 页码：274-283
• 全文大小：307 KB
• 参考文献：1. Zhang, W., Gao, K., Zhang, Y., Li, J.: Efficient Approximate Nearest Neighbor Search with Integrated Binary Codes. In: ACM MM, pp. 1189鈥?192 (2011)
  2. Chu, W.-T., Li, C.-J., Tseng, S.-C.: Travelmedia: an intelligent management system for media captured in travel. JVCI聽22, 93鈥?04 (2011)
  3. Torralba, A., Fergus, R., Weiss, Y.: Small codes and large image databases for recognition. In: IEEE CVPR (2008)
  4. Zhang, L., Zhang, Y., Tang, J., Gu, X., Li, J., Tian, Q.: Topology Preserving Hashing for Similarity Search. In: ACM MM (2013)
  5. Xie, H., Zhang, Y., Tan, J., Guo, L., Li, J.: Contextual Query Expansion for Image Retrieval. IEEE Trans. on Multimedia聽16(4) (2014)
  6. Salakhutdinov, R., Hinton, G.: Semantic Hashing. International Journal of Approximate Reasoning (2009)
  7. Strecha, C., Bronstein, A., Bronstein, M., Fua, P.: LDAHash: improved matching with smaller descriptors. IEEE Transactions on PAMI聽34(1), 66鈥?8 (2012) CrossRef
  8. Rublee, E., Rabaud, V., Konolige, K., Bradski, G.: ORB: an efficient alternative to SIFT or SURF. In: IEEE ICCV, pp. 2564鈥?571 (2011)
  9. Norouzi, M., Punjani, A., Fleet, D.J.: Fast search in hamming space with multi-index hashing. In: IEEE CVPR (2012)
  10. Muja, M., Lowe, D.G.: Fast matching of binary features. In: CRV (2012)
  11. Muja, M., Lowe, D.G.: http://people.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN
  12. Zitnick, C.L.: Binary coherent edge descriptors. In: Daniilidis, K., Maragos, P., Paragios, N. (eds.) ECCV 2010, Part II. LNCS, vol.聽6312, pp. 170鈥?82. Springer, Heidelberg (2010) CrossRef
  13. Weiss, Y., Torralba, A., Fergus, R.: Spectral Hashing. In: Advances in Neural Information Processing Systems (2008)
  14. Jegou, H., Douze, M., et al.: Product Quantization for Nearest Neighbor Search. IEEE Transactions on PAMI聽33(1), 117鈥?28 (2011) CrossRef
  15. Aly, M., Munich, M., Perona, P.: Distributed kd-trees for retrieval from very large image collections. In: BMVC (2011)
  16. Babenko, A., Lempitsky, V.: The inverted multi-index. In: IEEE CVPR (2012)
  17. SilpaAnan, C., Hartley, R.: Optimized KD-trees for fast image descriptor matching. In: CVPR (2008)
  18. Gionis, A., Indyk, P., Motwani, R.: Similarity search in high dimensions via hashing. In: Proceedings of the International Conference on Very Large Data Bases (1999)
  19. Broder, A.Z.: On the resemblance and containment of documents. In: IEEE Compression and Complexity of Sequences, pp. 21鈥?9 (1997)
  20. Park, H.S., Jun, C.H.: A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications聽36(2), 3336鈥?341 (2009) CrossRef
  21. Zhang, L., Zhang, Y., Tang, J., Lu, K., Tian, Q.: Binary Code Ranking with Weighted Hamming Distance. In: IEEE CVPR (2013)
  22. Bland, J.M., Altman, D.G.: Statistics notes: measurement error (1996)
  23. Jegou, H., Douze, M., Schmid, C.: Improving bag-of-features for large scale image search. Int. J. Comput. Vis.聽87(3), 316鈥?36 (2010) CrossRef
  
• 作者单位：Yanping Ma (21)
  Hongtao Xie (22)
  Zhineng Chen (23)
  Qiong Dai (22)
  Yinfei Huang (24)
  Guangrong Ji (21)
  
  21. School of Information Science and Engineering, Ocean University of China, Qingdao, China, 266100
  22. National Engineering Laboratory for Information Security Technologies, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, 100093
  23. Interactive Digital Media Technology Research Center, Institute of Automation, Chinese Academy of Sciences, Beijing, China, 100190
  24. Shanghai Stock Exchange, Shanghai, China, 200120
  
• ISSN：1611-3349

文摘

Although distance between binary codes can be computed fast in hamming space, linear search is not practical for large scale dataset. Therefore attention has been paid to the efficiency of performing approximate nearest neighbor search, in which Hierarchical Clustering Trees (HCT) is the state-of-the-art method. However, HCT builds index with the whole binary codes, which degrades search performance. In this paper, we first propose an algorithm to compress binary codes by extracting distinctive bits according to the standard deviation of each bit. Then, a new index is proposed using com-pressed binary codes based on hierarchical decomposition of binary spaces. Experiments conducted on reference datasets and a dataset of one billion binary codes demonstrate the effectiveness and efficiency of our method.