nips nips2013 nips2013-326 nips2013-326-reference knowledge-graph by maker-knowledge-mining

326 nips-2013-The Power of Asymmetry in Binary Hashing

Source: pdf

Author: Behnam Neyshabur, Nati Srebro, Ruslan Salakhutdinov, Yury Makarychev, Payman Yadollahpour

Abstract: When approximating binary similarity using the hamming distance between short binary hashes, we show that even if the similarity is symmetric, we can have shorter and more accurate hashes by using two distinct code maps. I.e. by approximating the similarity between x and x as the hamming distance between f (x) and g(x ), for two distinct binary codes f, g, rather than as the hamming distance between f (x) and f (x ). 1

reference text

[1] M. Datar, N. Immorlica, P. Indyk, and V.S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pages 253–262. ACM, 2004.

[2] W. Dong and M. Charikar. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. SIGIR, 2008.

[3] Y. Gong, S. Lazebnik, A. Gordo, and F. Perronnin. Iterative quantization: A procrustean approach to learning binary codes for large-scale image retrieval. TPAMI, 2012.

[4] A. Gordo and F. Perronnin. Asymmetric distances for binary embeddings. CVPR, 2011.

[5] B. Kulis and T. Darrell. Learning to hash with binary reconstructive embeddings. NIPS, 2009.

[6] W. Liu, R. Ji J. Wang, Y.-G. Jiang, and S.-F. Chang. Supervised hashing with kernels. CVPR, 2012.

[7] W. Liu, J. Wang, S. Kumar, and S.-F. Chang. Hashing with graphs. ICML, 2011.

[8] M. Norouzi and D. J. Fleet. Minimal loss hashing for compact binary codes. ICML, 2011.

[9] M. Norouzi, D. J. Fleet, and R. Salakhutdinov. Hamming distance metric learning. NIPS, 2012.

[10] M. Raginsky and S. Lazebnik. Locality-sensitive binary codes from shift-invariant kernels. NIPS, 2009.

[11] R. Salakhutdinov and G. Hinton. Semantic hashing. International Journal of Approximate Reasoning, 2009.

[12] N. Snavely, S. M. Seitz, and R.Szeliski. Photo tourism: Exploring photo collections in 3d. In Proc. SIGGRAPH, 2006.

[13] A. Torralba, R. Fergus, and Y. Weiss. Small codes and large image databases for recognition. CVPR, 2008.

[14] J. Wang, S. Kumar, and S. Chang. Sequential projection learning for hashing with compact codes. ICML, 2010.

[15] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. NIPS, 2008. 9