# Maximum Inner Product Search (Maximum Inner Product Search)

## Description

Given a new query $q$, MIPS targets at retrieving the datum having the largest inner product with $q$ from the database $A$. Formally, the MIPS problem is formulated as below:

$p = \arg \max \limits_{a \in A} a \top q$

## Parameters

No parameters found.

## Table of Algorithms

Currently no algorithms in our database for the given problem.

## Reductions TO Problem

Problem Implication Year Citation Reduction
Boolean d-Attribute Stable Matching assume: OVH
then: for an $\epsilon > {0}$ there is a $c$ such that finding a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon})$.
then: for an $\epsilon > {0}$ there is a $c$ such that verifying a stable matching in the boolean $d$-attribute model with $d = c\log n$ dimensions requires time $\Omega(n^{2-\epsilon}). 2016 https://arxiv.org/pdf/1510.06452.pdf link Stable Pair Checking assume: OVH then: for any$\epsilon > {0}$, there is a$c$such that determining whether a given pair is part of any or all stable matchings in the boolean$d$-attribute model with$d = c\log n$dimensions requires time$\Omega(n^{2-\epsilon})$2016 https://arxiv.org/pdf/1510.06452.pdf link Stable Pair Checking assume: NSETH then: for any$\epsilon > {0}$there is a$c$such that determining whether a gaiven pair is part of any or all stable matching in the boolean$d$-attribute model with$d = c\log n$dimensions requires co-nondeterministic time$\Omega(n^{2-\epsilon})$2016 https://arxiv.org/pdf/1510.06452.pdf link Stable Pair Checking assume: NSETH then: for any$\epsilon > {0}$there is a$c$such that determining whether a gaiven pair is part of any or all stable matching in the boolean$d$-attribute model with$d = c\log n$dimensions requires nondeterministic time$\Omega(n^{2-\epsilon})\$