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.
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: