A New Cell-Level Search Based Non-Exhaustive Approximate Nearest Neighbor (ANN) Search Algorithm in the Framework of Product Quantization

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 by searching all the PQ cells of the query vector on the cell level, and the length of the 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 (IVFs) 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. The experimental results on different databases demonstrate that our proposed cell-level PQ can significantly speed up the ANN search in the framework of PQ, and meanwhile, the search accuracy is almost the same as that of the standard PQ.

Keywords

• Approximate nearest neighbor search
• vector-level search
• cell-level search
• product quantization
• partial distance search