iccv iccv2013 iccv2013-159 iccv2013-159-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Jing Wang, Jingdong Wang, Gang Zeng, Rui Gan, Shipeng Li, Baining Guo
Abstract: In this paper, we propose a new data structure for approximate nearest neighbor search. This structure augments the neighborhoodgraph with a bridge graph. We propose to exploit Cartesian concatenation to produce a large set of vectors, called bridge vectors, from several small sets of subvectors. Each bridge vector is connected with a few reference vectors near to it, forming a bridge graph. Our approach finds nearest neighbors by simultaneously traversing the neighborhood graph and the bridge graph in the best-first strategy. The success of our approach stems from two factors: the exact nearest neighbor search over a large number of bridge vectors can be done quickly, and the reference vectors connected to a bridge (reference) vector near the query are also likely to be near the query. Experimental results on searching over large scale datasets (SIFT, GIST andHOG) show that our approach outperforms stateof-the-art ANN search algorithms in terms of efficiency and accuracy. The combination of our approach with the IVFADC system [18] also shows superior performance over the BIGANN dataset of 1 billion SIFT features compared with the best previously published result.
[1] K. Aoyama, K. Saito, H. Sawada, and N. Ueda. Fast approximate similarity search based on degree-reduced neighborhood graphs. In KDD, pages 1055– 1063, 201 1. 1, 2
[2] S. Arya and D. M. Mount. Approximate nearest neighbor queries in fixed dimensions. In SODA, pages 271–280, 1993. 1, 2, 4
[3] S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J. ACM, 45(6):891–923, 1998. 1
[4] A. Babenko and V. S. Lempitsky. The inverted multi-index. In CVPR, pages 3069–3076, 2012. 2, 3, 4, 5, 6, 7
[5] J. S. Beis and D. G. Lowe. Shape indexing using approximate nearestneighbour search in high-dimensional spaces. In CVPR, pages 1000–1006, 1997. 1
[6] J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509–517, 1975. 1, 2
[7] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In ICML, pages 97–104, 2006. 1
[8] M. Brown and D. G. Lowe. Recognising panoramas. In ICCV, pages 1218– 1227, 2003. 1
[9] S. Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. In STOC, pages 537–546, 2008. 1
[10] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In Symposium on Computational Geometry, pages 253–262, 2004. 1, 2
[11] L. Fei-Fei, R. Fergus, and P. Perona. Learning generative visual models from few training examples: an incremental bayesian approach tested on 101 object categories. In CVPR 2004 Workshop on Generative-Model Based Vision, 2004. 4
[12] J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30] matches in logarithmic expected time. ACM Trans. Math. Softw., 3(3):209–226, 1977. 1 A. Frome, Y. Singer, F. Sha, and J. Malik. Learning globally-consistent local distance functions for shape-based image retrieval and classification. In ICCV, pages 1–8, 2007. 1 Y. Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In CVPR, pages 817–824, 2011. 1 K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In IJCAI, pages 13 12– 1317, 2011. 1 J. Hays and A. A. Efros. Scene completion using millions of photographs. ACM Trans. Graph., 26(3):4, 2007. 1 Y. Hwang, B. Han, and H.-K. Ahn. A fast nearest neighbor search algorithm by nonlinear embedding. In CVPR, pages 3053–3060, 2012. 1 H. J ´egou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1): 117–128, 2011. 1, 2, 3, 5, 6, 7 H. J ´egou, R. Tavenard, M. Douze, and L. Amsaleg. Searching in one billion vectors: Re-rank with source coding. In ICASSP, pages 861–864, 201 1. 2, 4, 6, 7 Y. Jia, J. Wang, G. Zeng, H. Zha, and X.-S. Hua. Optimizing kd-trees for scalable visual descriptor indexing. In CVPR, pages 3392–3399, 2010. 1, 4 B. Kulis and T. Darrells. Learning to hash with binary reconstructive embeddings. In NIPS, pages 577–584, 2009. 1 B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In ICCV, 2009. 1 L. Liang, C. Liu, Y.-Q. Xu, B. Guo, and H.-Y. Shum. Real-time texture synthesis by patch-based sampling. ACM Trans. Graph. , 20(3): 127–150, 2001 . 1 T. Liu, A. W. Moore, A. G. Gray, and K. Yang. An investigation of practical approximate nearest neighbor algorithms. In NIPS, 2004. 1, 4 Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe lsh: Efficient indexing for high-dimensional similarity search. In VLDB, pages 950– 961, 2007. 1 A. W. Moore. The anchors hierarchy: Using the triangle inequality to survive high dimensional data. In UAI, pages 397–405, 2000. 1 M. Muja and D. G. Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. In VISSAPP (1), pages 33 1–340, 2009. 1, 4 D. Nist e´r and H. Stew e´nius. Scalable recognition with a vocabulary tree. In CVPR (2), pages 2161–2168, 2006. 1, 2 J. Philbin, O. Chum, M. Isard, J. Sivic, and A. Zisserman. Object retrieval with large vocabularies and fast spatial matching. In CVPR, 2007. 1 M. Raginsky and S. Lazebnik. Locality sensitive binary codes from shiftinvariant kernels. In NIPS, 2009. 1
[31] H. Samet. Foundations of multidimensional and metric data structures. Elsevier, Amsterdam, 2006. 1, 2
[32] T. B. Sebastian and B. B. Kimia. Metric-based shape retrieval in large databases. In ICPR (3), pages 291–296, 2002. 1, 2
[33] C. Silpa-Anan and R. Hartley. Optimised kd-trees for fast image descriptor matching. In CVPR, 2008. 1
[34] J. Sivic and A. Zisserman. Efficient visual search of videos cast as text retrieval. IEEE Trans. Pattern Anal. Mach. Intell., 31(4):591–606, 2009. 2
[35] N. Snavely, S. M. Seitz, and R. Szeliski. Photo tourism: exploring photo collections in 3D. ACM Trans. Graph., 25(3):835–846, 2006. 1
[36] A. B. Torralba, R. Fergus, and W. T. Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE Trans. Pattern Anal. Mach. Intell., 30(1 1): 1958–1970, 2008. 2, 4
[37] W. Tu, R. Pan, and J. Wang. Similar image search with a tiny bag-of-delegates representation. In ACM Multimedia, pages 885–888, 2012. 2
[38] J. Wang and S. Li. Query-driven iterated neighborhood graph search for large scale indexing. In ACM Multimedia, pages 179–188, 2012. 1, 2, 4
[39] J. Wang, J. Wang, X.-S. Hua, and S. Li. Scalable similar image search by joint indices. In ACM Multimedia, pages 1325–1326, 2012. 2
[40] J. Wang, J. Wang, Q. Ke, G. Zeng, and S. Li. Fast approximate k-means via cluster closures. In CVPR, pages 3037–3044, 2012. 5
[41] J. Wang, J. Wang, N. Yu, and S. Li. Order preserving hashing for approximate nearest neighbor search. In ACM Multimedia, 2013. 1
[42] J. Wang, J. Wang, G. Zeng, Z. Tu, R. Gan, and S. Li. Scalable k-nn graph construction for visual descriptors. In CVPR, pages 1106–1 113, 2012. 4, 7
[43] J. Wang, N. Wang, Y. Jia, J. Li, G. Zeng, H. Zha, and X.-S. Hua. Trinaryprojection trees for approximate nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. , 2013. 1, 4
[44] Y. Weiss, A. B. Torralba, and R. Fergus. Spectral hashing. In NIPS, pages 1753–1760, 2008. 1
[45] H. Xu, J. Wang, Z. Li, G. Zeng, S. Li, and N. Yu. Complementary hashing for approximate nearest neighbor search. In ICCV, pages 1631–1638, 2011. 1
[46] P. N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In SODA, pages 311–321, 1993. 1, 4 2135