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})$.	2016	https://arxiv.org/pdf/1510.06452.pdf	link
Stable Matching Verification	assume: OVH 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})$	2016	https://arxiv.org/pdf/1510.06452.pdf	link