# A Greedy Approach for Budgeted Maximum Inner Product Search

arXiv: https://arxiv.org/abs/1610.03317 · HTML: https://mlsanity.com/paper/1610.03317/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Oct 2016.

## Built on by (most cited first, 11 of 11)

- [Breaking the Linear Iteration Cost Barrier for Some Well-known Conditional Gradient Methods Using MaxIP Data-structures](https://mlsanity.com/paper/2111.15139/) (2021)
- [Sublinear Least-Squares Value Iteration via Locality Sensitive Hashing](https://mlsanity.com/paper/2105.08285/) (2021)
- [Linear Bandit Algorithms with Sublinear Time Complexity](https://mlsanity.com/paper/2103.02729/) (2021)
- [Flashlight: Scalable Link Prediction with Effective Decoders](https://mlsanity.com/paper/2209.10100/) (2022)
- [Efficient Link Prediction via GNN Layers Induced by Negative Sampling](https://mlsanity.com/paper/2310.09516/) (2023)
- [FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2206.11408/) (2022)
- [PEFA: Parameter-Free Adapters for Large-scale Embedding-based Retrieval Models](https://mlsanity.com/paper/2312.02429/) (2023)
- [Faster Maximum Inner Product Search in High Dimensions](https://mlsanity.com/paper/2212.07551/) (2022)
- [SAH: Shifting-aware Asymmetric Hashing for Reverse k-Maximum Inner Product Search](https://mlsanity.com/paper/2211.12751/) (2022)
- [Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders](https://mlsanity.com/paper/2405.03651/) (2024)
- [Isometry pursuit](https://mlsanity.com/paper/2411.18502/) (2024)

## Abstract (arXiv)

Maximum Inner Product Search (MIPS) is an important task in many machine learning applications such as the prediction phase of a low-rank matrix factorization model for a recommender system. There have been some works on how to perform MIPS in sub-linear time recently. However, most of them do not have the flexibility to control the trade-off between search efficient and search quality. In this paper, we study the MIPS problem with a computational budget. By carefully studying the problem structure of MIPS, we develop a novel Greedy-MIPS algorithm, which can handle budgeted MIPS by design. While simple and intuitive, Greedy-MIPS yields surprisingly superior performance compared to state-of-the-art approaches. As a specific example, on a candidate set containing half a million vectors of dimension 200, Greedy-MIPS runs 200x faster than the naive approach while yielding search results with the top-5 precision greater than 75%.