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.

In the re-evaluated paper, Xie et al. proposed a new fast search algorithm for vector quantization encoding, which optimized the priority checking order of variance and norm inequality in order to speed up the encoding procedure. CPU time of different encoding algorithms is given to support their algorithm. However, first, some of the experimental data in the re-evaluated paper are unreasonable and unrepeatable. And second, as an improved algorithm of equal-average equal-variance equal-norm nearest neighbor fast search algorithm, the re-evaluated algorithm in fact cannot achieve a better performance than the existing improved equal-average equal-variance nearest neighbor fast search algorithm. In this paper, these two problems are analyzed, re-evaluated, and discussed in detail.

This paper proposes a decorrelation scheme based on product quantization, termed Reference-Vector Removed Product Quantization (RvRPQ), for approximate nearest neighbor (ANN) search. The core idea is to capture the redundancy among database vectors by representing them with compactly encoded reference-vectors, which are then subtracted from the original vectors to yield residual vectors. We provide a theoretical derivation for obtaining the optimal reference-vectors. This preprocessing step significantly improves the quantization accuracy of the subsequent product quantization applied to the residuals. To maintain low online computational complexity and control memory overhead, we apply vector quantization to the reference-vectors and allocate only a small number of additional bits to store their indices. Experimental results show that RvRPQ substantially outperforms state-of-the-art ANN methods in terms of retrieval accuracy, while preserving high search efficiency.