Hash Bit Selection Using Markov Process for Approximate Nearest Neighbor Search

ABSTRACT

Hashing for nearest neighbor search has attracted great attentions in the past years. Many hashing methods have been successfully applied in real-world applications like the mobile product search. The performance of these applications usually highly relies on the quality of hash bits. However, it still lacks of a general method that can provide good hash bits for different scenarios. In this paper, we propose a novel method that can select compact, independent and informative hash bits using the Markov Process. Our method can serve as a unified framework compatible with different hashing methods. We design two algorithms, BS-CMP and BS-DMP, and formulate the selection problem as the subgraph discovery on a graph. Experiments are conducted for two important selection scenarios when applying hash techniques, i.e., hashing using different hashing algorithms and hashing with multiple features. The result indicates that our proposed bit selection approaches outperform naive selection methods significantly under aforementioned two scenarios.

References

1. J. L. Doob. Stochastic processes, volume 101. New York Wiley, 1953.
2. S. N. Ethier and T. G. Kurtz. Markov processes: characterization and convergence, volume 282. Wiley. com, 2009.
3. J. He, J. Feng, X. Liu, T. Cheng, T.-H. Lin, H. Chung, and S.-F. Chang. Mobile product search with bag of hash bits and boundary reranking. In IEEE CVPR, pages 3005--3012. IEEE, 2012.
4. J. He, R. Radhakrishnan, S.-F. Chang, and C. Bauer. Compact hashing with joint optimization of search accuracy and time. In IEEE CVPR, pages 753--760. IEEE, 2011.
5. J.-P. Heo, Y. Lee, J. He, S.-F. Chang, and S.-E. Yoon. Spherical hashing. In IEEE CVPR, pages 2957--2964. IEEE, 2012.
6. A. Joly and O. Buisson. Random maximum margin hashing. In IEEE CVPR, pages 873--880. IEEE, 2011.
7. B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In IEEE ICCV in 2009, pages 2130--2137. IEEE, 2009.
8. X. Liu, J. He, and B. Lang. Reciprocal hash tables for nearest neighbor search. In AAAI, 2013.
9. X. Liu, J. He, B. Lang, and S.-F. Chang. Hash bit selection: a unified solution for selection problems in hashing. In IEEE CVPR, 2013.
10. Y. Mu, X. Chen, X. Liu, T.-S. Chua, and S. Yan. Multimedia semantics-aware query-adaptive hashing with bits reconfigurability. IJMIR, 1(1):59--70, 2012.
11. M. Pavan and M. Pelillo. Dominant sets and pairwise clustering. IEEE Trans. PAMI, 29(1):167--172, 2007.
12. Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, pages 1753--1760, 2008.

Index Terms

• Computing methodologies

  • Machine learning

• Information systems

  • Information retrieval

    • Document representation