Local Orthogonal Decomposition for Maximum Inner Product Search
This work provides an incremental improvement for efficient similarity search in large-scale datasets, benefiting applications like recommendation systems and information retrieval.
The paper tackles the problem of improving maximum inner product search efficiency by proposing a local orthogonal decomposition method that connects the vector quantization and product quantization steps in IVFADC frameworks, achieving consistently higher recall than previous methods under the same bitrates.
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.