# Maximum Inner Product Search (Maximum Inner Product Search)

Jump to navigation
Jump to 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 |