Maximum inner-product search

{{Short description|Search problem}}

Maximum inner-product search (MIPS) is a search problem, with a corresponding class of search algorithms which attempt to maximise the inner product between a query and the data items to be retrieved. MIPS algorithms are used in a wide variety of big data applications, including recommendation algorithms and machine learning.{{cite arXiv |last1=Abuzaid |first1=Firas |last2=Sethi |first2=Geet |last3=Bailis |first3=Peter |last4=Zaharia |first4=Matei |date=2019-03-14 |title=To Index or Not to Index: Optimizing Exact Maximum Inner Product Search |class=cs.IR |eprint=1706.01449 }}

Formally, for a database of vectors $x\_i$ defined over a set of labels $S$ in an inner product space with an inner product $\backslash langle\; \backslash cdot,\; \backslash cdot\; \backslash rangle$ defined on it, MIPS search can be defined as the problem of determining

:$\backslash underset\{i\; \backslash in\; S\}\{\backslash operatorname\{arg\backslash ,max\}\}\backslash \; \backslash langle\; x\_i,\; q\; \backslash rangle$

for a given query $q$.

Although there is an obvious linear-time implementation, it is generally too slow to be used on practical problems. However, efficient algorithms exist to speed up MIPS search.Steve Mussmann, Stefano Ermon.

Learning and Inference via Maximum Inner Product Search.

In Proc. 33rd International Conference on Machine Learning (ICML), 2016.

Under the assumption of all vectors in the set having constant norm, MIPS can be viewed as equivalent to a nearest neighbor search (NNS) problem in which maximizing the inner product is equivalent to minimizing the corresponding distance metric in the NNS problem.{{Cite journal |last1=Shrivastava |first1=Anshumali |last2=Li |first2=Ping |date=2015-07-12 |title=Improved asymmetric locality sensitive hashing (ALSH) for Maximum Inner Product Search (MIPS) |url=https://dl.acm.org/doi/abs/10.5555/3020847.3020931 |journal=Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence |series=UAI'15 |location=Arlington, Virginia, USA |publisher=AUAI Press |pages=812–821 |arxiv=1410.5410 |isbn=978-0-9966431-0-8}} Like other forms of NNS, MIPS algorithms may be approximate or exact.{{Cite book |last1=Keivani |first1=Omid |last2=Sinha |first2=Kaushik |last3=Ram |first3=Parikshit |title=2017 International Joint Conference on Neural Networks (IJCNN) |chapter=Improved maximum inner product search with better theoretical guarantees |date=May 2017 |chapter-url=https://ieeexplore.ieee.org/document/7966218 |pages=2927–2934 |doi=10.1109/IJCNN.2017.7966218|isbn=978-1-5090-6182-2 |s2cid=8352165 }}

MIPS search is used as part of DeepMind's RETRO algorithm.{{Cite web |date=2022-07-01 |title=RETRO Is Blazingly Fast |url=http://mitchgordon.me/ml/2022/07/01/retro-is-blazing.html |access-date=2022-07-04 |website=Mitchell A. Gordon |language=en}}