An Accurate and Fast Method for Maximum Inner Product Search

What is it about?

The Maximum Inner Product Search (MIPS) problem has received increasing attention due to its wide applications in Recommendation Systems and Deep Neural Network Acceleration. In this paper, we propose a novel hashing scheme H2-ALSH for high-dimensional MIPS. We propose a novel Query Normalized First (QNF) transformation to reduce the distortion error significantly. Moreover, we design a new homocentric hypersphere partition strategy to increase search efficiency and accuracy with a limited data range. Our theoretical studies show that H2-ALSH enjoys a guarantee of search accuracy. Experimental results over four real datasets demonstrate that H2-ALSH significantly outperforms the state-of-the-art schemes. Code is available at https://github.com/HuangQiang/H2_ALSH.

Featured Image

Photo by Carl Barcelo on Unsplash

Photo by Carl Barcelo on Unsplash

Why is it important?

With asymmetric transformations, the problem can be reduced to the classic Nearest Neighbor Search (NNS) problem and leverages the Locality-Sensitive Hashing (LSH) to find sub-linear time solutions. However, existing asymmetric transformations such as L2-ALSH and XBOX suffer from significant distortion error in reducing MIPS to NNS, such that the results of MIPS might be arbitrarily bad. This work proposes a novel QNF transformation and a new homocentric hypersphere partitioning strategy to significantly reduce the distortion error. H2-ALSH enjoys a guarantee of search accuracy and works with any approximation ratio 0 < c < 1.

Perspectives