iccv iccv2013 iccv2013-83 iccv2013-83-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Zhongming Jin, Yao Hu, Yue Lin, Debing Zhang, Shiding Lin, Deng Cai, Xuelong Li
Abstract: Recently, hashing techniques have been widely applied to solve the approximate nearest neighbors search problem in many vision applications. Generally, these hashing approaches generate 2c buckets, where c is the length of the hash code. A good hashing method should satisfy the following two requirements: 1) mapping the nearby data points into the same bucket or nearby (measured by xue long l i opt . ac . cn @ a(a)b(b) the Hamming distance) buckets. 2) all the data points are evenly distributed among all the buckets. In this paper, we propose a novel algorithm named Complementary Projection Hashing (CPH) to find the optimal hashing functions which explicitly considers the above two requirements. Specifically, CPHaims at sequentiallyfinding a series ofhyperplanes (hashing functions) which cross the sparse region of the data. At the same time, the data points are evenly distributed in the hypercubes generated by these hyperplanes. The experiments comparing with the state-of-the-art hashing methods demonstrate the effectiveness of the proposed method.
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In Communications of the ACM, 2008.
[2] L. Arge, M. Berg, H. Haverkort, and K. Yi. The priority rtree: a practically efficient and worst-case optimal r-tree. In SIGMOD, 2004.
[3] A.Turpin and F.Scholer. User performance versus precision measures for simple search tasks. In SIGIR, 2006.
[4] J. Bentley. Multidimensional binary search trees used for associative searching. In Communications of the ACM, 1975.
[5] K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft. When is ”nearest neighbor” meaningful? In ICDT, 1999.
[6] C. D.Manning, P. Raghavan, and H. Schutze. An Introduction to Information Retrieval. Cambridge University Press, 2008.
[7] Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR, 2011.
[8] J. He, R. Radhakrishnan, S. F.Chang, and C. Bauer. Compact hashing with joint optimization of search accuracy and time. In CVPR, 2011.
[9] J.-P. Heo, Y. Lee, J. He, S. F.Chang, and S. E.Yoon. Spherical hashing. In CVPR, 2012.
[10] P. Jain, B. Kulis, and K. Grauman. Fast similarity search for learned metrics. TPAMI, 2009.
[11] A. Joly and O. Buisson. A posteriori multi-probe locality sensitive hashing. In ACM Multimedia, 2008.
[12] A. Joly and O. Buisson. Random maximum margin hashing. In CVPR, 2011.
[13] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing. TPAMI, 2012.
[14] Y. Lin, R. Jin, D. Cai, S. Yan, and X. Li. Compressed hashing. In CVPR, 2013.
[15] W. Liu, J. Wang, R. Ji, Y. Jiang, and S. F.Chang. Supervised hashing with kernels. In CVPR, 2012.
[16] W. Liu, J. Wang, S. Kumar, and S. F.Chang. Hashing with graphs. In ICML, 2011.
[17] Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe lsh: Efficient indexing for high-dimensional similarity search. In VLDB, 2007.
[18] Y. Mu, J. Shen, and S. Yan. Weakly-supervised hashing in kernel space. In CVPR, 2010.
[19] Y. Nesterov. Introductory lectures on convex optimization: A basic course. Kluwer Academic Publishers, 2003.
[20] M. Norouzi and D. J.Fleet. Minimal loss hashing for compact binary codes. In ICML, 2011.
[21] R. O.Duda, P. E.Hart, and D. G.Stock. Pattern Classification 2nd Edition. John Wiley & Sons, Inc, 2001 .
[22] R. Panigrahy. Entropy based nearest neighbor search in high dimensions. In SODA, 2006.
[23] J. S.Beis and D. G.Lowe. Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In CVPR, 1997.
[24] J. Wang, S. Kumar, and S.-F. Chang. Sequential projection learning for hashing with compact codes. In ICML, 2010.
[25] J. Wang, S. Kumar, and S. F.Chang. Semi-supervised hashing for large scale search. TPAMI, 2012.
[26] X.-J. Wang, L. Zhang, F. Jing, and W.-Y. Ma. Annosearch: Image auto-annotation by search. In CVPR, 2006.
[27] Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, 2008.
[28] C. Wu, J. Zhu, D. Cai, C. Chen, and J. Bu. Semisupervised nonlinear hashing using bootstrap sequential projection learning. TKDE, 2013.
[29] H. Xu, J. Wang, Z. Li, G. Zeng, S. Li, and N. Yu. Complementary hashing for approximate nearest neighbor search. In ICCV, 2011. 264