A New Cell-Level Search Based Non-Exhaustive Approximate Nearest Neighbor (ANN) Search Algorithm in the Framework of Product Quantization
Open Access
- 27 February 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Access
- Vol. 7, 37059-37070
Abstract
Non-exhaustive search is widely used in the approximate nearest neighbor (ANN) search. In this paper, we propose a new cell-level search based non-exhaustive ANN search algorithm in the framework of product quantization (PQ) called Cell-level PQ to speed up the ANN search. The cell-level search is introduced and by searching all the PQ cells of the query vector on cell level, the length of candidate list can be significantly reduced with negligible computational costs. Instead of using the high time-consuming coarse quantizers, which are necessary in all of the existing non-exhaustive ANN search algorithms such as inverted files (IVF) and inverted multi-index (IMI), our proposed Cell-level PQ reuses the PQ cells of query vector to reject database vectors so that the ANN search in the framework of PQ can be efficiently speeded up. In addition, because our proposed Cell-level PQ does not need to store the auxiliary indexes of coarse quantizers for each database vector, no extra memory consumption is required. Experimental results on different databases demonstrated that our proposed Cell-level PQ can significantly speed up the ANN search in the framework of PQ, meanwhile the search accuracy is almost the same as that of standard PQ.Keywords
Funding Information
- National Laboratory of Pattern Recognition (201800030)
- Chinese Academy of Sciences (LSIT201606D)
- Major Science Program of Xiaoshan District, Hangzhou, Zhejiang (2018225)
This publication has 16 references indexed in Scilit:
- Product tree quantization for approximate nearest neighbor search2015
- Large-scale multi-task image labeling with adaptive relevance discovery and feature hashingSignal Processing, 2015
- The Inverted Multi-IndexIEEE Transactions on Pattern Analysis and Machine Intelligence, 2014
- Fast and Accurate Image Matching with Cascade Hashing for 3D Reconstruction2014
- Ranking consistency for image matching and object retrievalPattern Recognition, 2014
- Product Quantization for Nearest Neighbor SearchIEEE Transactions on Pattern Analysis and Machine Intelligence, 2010
- Distinctive Image Features from Scale-Invariant KeypointsInternational Journal of Computer Vision, 2004
- Video Google: a text retrieval approach to object matching in videos2003
- Modeling the Shape of the Scene: A Holistic Representation of the Spatial EnvelopeInternational Journal of Computer Vision, 2001
- An Algorithm for Vector Quantizer DesignIEEE Transactions on Communications, 1980