FARGO: Fast Maximum Inner Product Search via Global Multi-Probing

01/01/2023

Understanding Maximum Inner Product Search: From Theory to Practice

As machine learning and artificial intelligence continue to advance, the ability to efficiently search through high-dimensional vector spaces has become increasingly crucial. One fundamental challenge in this domain is the Maximum Inner Product Search (MIPS) problem, which involves finding vectors in a dataset that maximize their inner product with a given query vector. This operation is central to numerous applications including recommendation systems, multi-class label prediction, similar-item retrieval, structural SVM, and deep learning.

Traditional approaches to MIPS using space partitioning trees become exponentially slower as dimensionality increases, making them impractical for modern applications that often deal with hundreds or thousands of dimensions. While Locality-Sensitive Hashing (LSH) has proven effective for approximate nearest neighbor search, it cannot be directly applied to MIPS due to the unique properties of inner product similarity. The need for an efficient, scalable solution to MIPS has never been more pressing as organizations process increasingly large-scale, high-dimensional datasets.

This paper introduces FARGO, a novel framework that revolutionizes how we approach the MIPS problem. We present a comprehensive analysis of current MIPS solutions, their limitations, and how FARGO overcomes these challenges through innovative techniques including global multi-probing and random XBOX transformation. Our framework not only achieves superior accuracy and efficiency compared to existing methods but also provides practical solutions for real-world applications dealing with high-dimensional data at scale.

Get the Whitepaper