Fast Neighborhood Graph Search Using Cartesian Concatenation
Authors:
- Jing WangJWJing Wang
- Jingdong WangJWJingdong Wang
- Gang ZengGZGang Zeng
- Rui GanRGRui Gan
- Shipeng LiSLShipeng Li
- Baining GuoBGBaining Guo
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15505499,p. 2128-2135
Abstract
In this paper, we propose a new data structure for approximate nearest neighbor search. This structure augments the neighborhood graph 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, GISTand HOG) show that our approach outperforms state-of-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.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Scalable similar image search by joint indices2012
- Similar image search with a tiny bag-of-delegates representation2012
- Iterative quantization: A procrustean approach to learning binary codes2011
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- Optimised KD-trees for fast image descriptor matching2008
- 80 Million Tiny Images: A Large Data Set for Nonparametric Object and Scene RecognitionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008
- Efficient Visual Search of Videos Cast as Text RetrievalIEEE Transactions on Pattern Analysis and Machine Intelligence, 2008
- Scene completion using millions of photographsACM Transactions on Graphics, 2007
- Learning Globally-Consistent Local Distance Functions for Shape-Based Image Retrieval and Classification2007
- Photo tourismACM Transactions on Graphics, 2006