Maximum inner-product search explained

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.[1]

Formally, for a database of vectors

xi

defined over a set of labels

S

in an inner product space with an inner product

\langle,\rangle

defined on it, MIPS search can be defined as the problem of determining

\underset{i\inS}{\operatorname{argmax}}\langlexi,q\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.[2]

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.[3] Like other forms of NNS, MIPS algorithms may be approximate or exact.[4]

MIPS search is used as part of DeepMind's RETRO algorithm.[5]

See also

Notes and References

  1. Abuzaid . Firas . Sethi . Geet . Bailis . Peter . Zaharia . Matei . 2019-03-14 . To Index or Not to Index: Optimizing Exact Maximum Inner Product Search . cs.IR . 1706.01449 .
  2. Steve Mussmann, Stefano Ermon.Learning and Inference via Maximum Inner Product Search.In Proc. 33rd International Conference on Machine Learning (ICML), 2016.
  3. Shrivastava . Anshumali . Li . Ping . 2015-07-12 . Improved asymmetric locality sensitive hashing (ALSH) for Maximum Inner Product Search (MIPS) . Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence . UAI'15 . Arlington, Virginia, USA . AUAI Press . 812–821 . 1410.5410 . 978-0-9966431-0-8.
  4. Book: Keivani . Omid . Sinha . Kaushik . Ram . Parikshit . 2017 International Joint Conference on Neural Networks (IJCNN) . Improved maximum inner product search with better theoretical guarantees . May 2017 . https://ieeexplore.ieee.org/document/7966218 . 2927–2934 . 10.1109/IJCNN.2017.7966218. 978-1-5090-6182-2 . 8352165 .
  5. Web site: 2022-07-01 . RETRO Is Blazingly Fast . 2022-07-04 . Mitchell A. Gordon . en.