To Index or Not to Index: Optimizing Exact Maximum Inner Product Search

By Firas Abuzaid, Geet Sethi, Peter Bailis, Matei A. Zaharia. 2017

27 citations recorded by the source corpus.

Exact Maximum Inner Product Search (MIPS) is an important task that is widely pertinent to recommender systems and high-dimensional similarity search. The brute-force approach to solving exact MIPS is computationally expensive, thus spurring recent development of novel indexes and pruning techniques for this task. In this paper, we show that a hardware-efficient brute-force approach, blocked matrix multiply (BMM), can outperform the state-of-the-art MIPS solvers by over an order of magnitude, for some—but not all—inputs. In this paper we also present a novel MIPS solution, MAX-IMUS, that takes advantage of hardware efficiency and pruning of the search space. Like BMM, MAXIMUS is faster than other solvers by up to an order of magnitude, but again only for some inputs. Since no single solution offers the best runtime performance for all inputs, we introduce a new data-dependent optimizer, OPTIMUS, that selects online with minimal overhead the best MIPS solver for a given input. Together, OPTIMUS and MAXIMUS outperform state-of-the-art MIPS solvers by 3.2× on average, and up to 10.9×, on widely studied MIPS datasets.

Subfields: Computer Networks and Communications, Computer Vision and Pattern Recognition, Information Retrieval & Search

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Computer Vision and Pattern Recognition

In Information Retrieval & Search

Citations in the corpus

ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT (2020, background): “, [1, 15]) to retrieve the top-k results directly from a large document collection, substantially improving recall over models that only re-rank the output of term-based retrieval.”
Socratic Models: Composing Zero-Shot Multimodal Reasoning with Language (2022, background): “latent representations of video frames) to provide sub-linear querying mechanism for the incoming text snippet (see: (Abuzaid et al. 2019)).”
Deep entity matching with pre-trained language models (2020, methodology): “Advanced blocking consists of two steps: computing the representation of each record with Sentence-BERT [34] (Encoding) and similarity search by blocked matrix multiplication [1] (Search).”