text: Inverted file and asymmetric distance computation (IVFADC) have been successfully applied to approximate nearest neighbor search and subsequently maximum inner product search. In such a framework, vector quantization is used for coarse partitioning while product quantization is used for quantizing residuals. In the original IVFADC as well as all of its variants, after residuals are computed, the second production quantization step is completely independent of the first vector quantization step. In this work, we seek to exploit the connection between these two steps when we perform non-exhaustive search. More specifically, we decompose a residual vector locally into two orthogonal components and perform uniform quantization and multiscale quantization to each component respectively. The proposed method, called local orthogonal decomposition, combined with multiscale quantization consistently achieves higher recall than previous methods under the same bitrates. We conduct comprehensive experiments on large scale datasets as well as detailed ablation tests, demonstrating effectiveness of our method.
  @cite_15: We present a simple vector quantizer that combines low distortion with fast search and apply it to approximate nearest neighbor (ANN) search in high dimensional spaces. Leveraging the very same data structure that is used to provide non-exhaustive search, i.e., inverted lists or a multi-index, the idea is to locally optimize an individual product quantizer (PQ) per cell and use it to encode residuals. Local optimization is over rotation and space decomposition, interestingly, we apply a parametric solution that assumes a normal distribution and is extremely fast to train. With a reasonable space and time overhead that is constant in the data size, we set a new state-of-the-art on several public datasets, including a billion-scale one.
summary: Rotations and codebooks are often applied in IVFADC variations, but there are significant costs associated with them. In the most extreme cases, Locally Optimized Product Quantization (LOPQ) @cite_15 learns a separate rotation matrix and codebook for each partition. This leads to an extra memory cost of @math and @math more multiplications for each query at search time. where @math is the number of VQ partitions we search. When @math and @math increase, the overhead become quickly noticeable and may become even more expensive than ADC itself. For example, when @math , @math , @math , performing the rotation once is as expensive as performing 6,400 ADC computations under an optimized implementation. In practice, it is often desirable to avoid per partition rotation or codebooks, but learn global codebooks and rotation.