Consider $\mathbb{R}^n$ equipped with the standard dot product $\langle \cdot, \cdot \rangle$ and $m$ vectors there: $v_1, v_2, \ldots, v_m$. We want to build a data structure that allows queries of the following format: given $x \in \mathbb{R}^n$ output $\min_i \langle x, v_i \rangle$. Is it possible to go beyond the trivial $O(nm)$ query time? For example if $n = 2$, then it is immediate to get $O(\log^2 m)$.The only thing I can come up with is the following. It is an immediate consequence of Johnson-Lindenstrauss lemma that for every $\varepsilon > 0$ and a distribution $\mathcal{D}$ on $\mathbb{R}^n$ there is a linear mapping $f \colon \mathbb{R}^n \to \mathbb{R}^{O(\log m)}$ (which can be evaluated in $O(n \log m)$ time) such that $\mathrm{Pr}_{x \sim \mathcal{D}}\left[\forall i \quad \langle x, v_i \rangle - \varepsilon (\|x\| + \|v_i\|)^2 \leq \langle f(x), f(v_i)\rangle \leq \langle x, v_i \rangle + \varepsilon (\|x\| + \|v_i\|)^2 \right] \geq 1 - \varepsilon$. So, in time $O((n + m) \log m)$ we can compute something that is in some sense close to $\min_i \langle x, v_i \rangle$ for most $x$'s (at least if the norms $\|x\|$ and $\|v_i\|$ are small).UPD The abovementioned bound can be somewhat sharpened to the query time $O(n + m)$ if we use locality-sensitive hashing. More precisely, we choose $k := O(\frac{1}{\varepsilon^2})$ independent Gaussian vectors $r_1, r_2, \ldots, r_k$. Then we map $\mathbb{R}^n$ to $\{0,1\}^k$ as follows: $v \mapsto (\langle r_1, v \rangle \geq 0, \langle r_2, v \rangle \geq 0, \ldots, \langle r_k, v \rangle \geq 0)$. Then we can estimate the angle between two vectors within an additive error $\varepsilon$ by computing $\ell_1$-distance in the image of this mapping. Thus, we can estimate dot products within an additive error $\varepsilon \|x\| \|v_i\|$ in $O(\frac{1}{\varepsilon^2})$ time.
A data structure for minimum dot product queries
ds.data structures;cg.comp geom;linear algebra;metrics