<p>Consider the special case where you just want to determine if your query vector is orthogonal to some vector in your preprocessed collection. (That is, you want to determine if $\min_i \langle x, v_i \rangle = 0$, where the vectors under discussion have non-negative coefficients.) This case is already very interesting.</p>

<p>Suppose you can answer queries in $n^{O(1)} m^{1-\delta}$ time for some $\delta &gt; 0$, with $m^{O(1)} n^{O(1)}$ preprocessing (the polynomial's degrees should not depend on $m$ or $n$ or $\delta$). </p>

<p>In the paper "A new algorithm for optimal 2-constraint satisfaction and its implications", I observed that such a data structure would actually allow you to solve CNF-SAT in $2^{\alpha v}$ time for some $\alpha &lt; 1$, where $v$ is the number of variables. This would refute the "Strong Exponential Time Hypothesis" that k-SAT requires essentially $2^n$ time for unbounded $k$.</p>

<p>To see why, suppose the preprocessing time is bounded by $(nm)^c$. Consider a CNF formula $F$ with $v$ variables and $n$ clauses. We split the set of variables into two parts $P_1$ and $P_2$ of size $v(1-1/(2c))$ and $v/(2c)$, respectively. List all possible assignments to the variables in the parts (getting $2^{v(1-1/(2c))}$ and $2^{v/(2c)}$ assignments, respectively). Associate each of these partial assignments $A_i$ with an $n$-bit vector $w_i$ where $w_i[j]=1$ iff the $j$th clause of $F$ is not satisfied by $A_i$. So we have two lists of exponentially many bit vectors.</p>

<p>Notice that $F$ is satisfiable iff there is a vector $w_1$ from an assignment on $P_1$ and a vector $w_2$ from an assignment on $P_2$ such that $\langle w_1, w_2 \rangle = 0$.</p>

<p>Now let $m=2^{v/(2c)}$, and preprocess the assumed data structure with all vectors from part $P_2$. This takes $n2^{v/2}$ time, by assumption. Run the query algorithm on all vectors from assignments on part $P_1$. By assumption this takes $2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$. Let $\alpha = 1 - \delta/(2c)$.</p>

<p>Perhaps it is possible to get efficient preprocessing and $n^{O(1)} m^{1-1/(\log \log m)}$ query time with existing techniques. The best known CNF-SAT algorithms don't rule it out. (They get something like $2^{n-n/\log n}$.) But to compute $\min_i \langle x, v_i\rangle$ is slightly stronger -- in this setup, it would be like solving MAX CNF-SAT.</p>

CC BY-SA 3.0
2011-08-14T09:01:58.220Z
Awesome! But it doesn't rule out approximate data structures as well as query times like $O(m \cdot \mathrm{poly}(\log n))$, which would be also very interesting.
ilyaraz
CC BY-SA 3.0
2011-08-14T09:06:08.827Z
By the way, can't we say something like "if there was even approximate data structure with fast query time, then MAX-SAT would be approximable".
ilyaraz
CC BY-SA 3.0
2011-08-14T12:41:37.337Z
Why does the equivalence stated in the first paragraph hold?  I think that the inner product can be negative in general.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-14T15:47:21.130Z
ilyaraz: Yes, even approximate data structures would imply approximate MAX-SAT. Tsuyoshi: Thank you for your insight
Ryan Williams
CC BY-SA 3.0
2011-08-14T08:16:51.220Z
2011-08-14T15:49:21.877Z
2011-08-14T15:49:21.877Z
Ryan Williams
<p>Here's one idea for the exact answer, that I suspect Chao Xu might be alluding to. Firstly observe that we might as well normalize $x$, as Chao points out. Now consider the hyperplane $h$ normal to the direction $x$. The goal is to find the point closest to this hyperplane. By duality, this corresponds to a ray shooting query in an arrangement of hyperplanes to find the closest plane "above" the query point. Since this can be preprocessed, the main complexity is the point location, and so your problem has now been reduced to the complexity of doing point location in an arrangement of hyperplanes. Using cuttings, this can be done in $O(\log n)$ time in $n^d$ space. </p>

CC BY-SA 3.0
2011-08-14T07:03:39.310Z
I should have mentioned that I'm also interested in a reasonable preprocessing time which is not the case here if a dimension is largish.
ilyaraz
CC BY-SA 3.0
2011-08-14T06:44:02.550Z
2011-08-14T06:44:02.550Z
Suresh Venkat
<p>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$. <strong>Is it possible to go beyond the trivial $O(nm)$ query time?</strong> For example if $n = 2$, then it is immediate to get $O(\log^2 m)$.</p>

<p>The only thing I can come up with is the following. It is an immediate consequence of <a href="http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma">Johnson-Lindenstrauss lemma</a> that for every $\varepsilon &gt; 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 <em>evaluated</em> 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 <em>something</em> 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).</p>

<p><strong>UPD</strong> 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.</p>

<hr>

CC BY-SA 3.0
2011-08-13T13:13:15.693Z
I am not sure if this works or helps, but your problem (after switching the sign of v_i to convert to the maximization) looks related to Voronoi diagrams.  It may be possible to modify algorithms for Voronoi diagrams to this problem, but even if it is possible, it will be probably useful only for small n.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-13T15:14:47.623Z
I don't know if this is the same observation... All $x$ can be normalized to a unit vector and doesn't change the result, we can do everything in a unit n-cube centered in origin. Find which region of the cube minimize the dot product with $v_i$ for each $i$ (each region must be a polytope). I do not have a bound on the number of polytopes. If it is less than exponential in $nm$, you have something better than $O(nm)$ by doing a n-dimensional point location query.
Chao Xu
CC BY-SA 3.0
2011-08-14T05:25:15.647Z
which parameter do you care about more ? usually, if you want to get sublinear in m, you're going to start getting exponential in n.
Suresh Venkat
CC BY-SA 3.0
2011-08-14T05:59:21.520Z
@Suresh Well, it would be nice to understand different possible trade-offs. Approximate version is interesting too.
ilyaraz
CC BY-SA 3.0
2013-05-17T18:37:29.947Z
Quick note: for the n = 2 case, binary search on the convex hull gives $O(\log n)$ query time.
Geoffrey Irving
<ds.data-structures><cg.comp-geom><linear-algebra><metrics>
A data structure for minimum dot product queries
ilyaraz
# A data structure for minimum dot product queries

(Asked by: username_0 on 2011-08-13)

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](http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_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.

---

**Tags:** ds.data-structures, cg.comp-geom, linear-algebra, metrics
> **Comments:**
> **username_1**: I am not sure if this works or helps, but your problem (after switching the sign of v_i to convert to the maximization) looks related to Voronoi diagrams.  It may be possible to modify algorithms for Voronoi diagrams to this problem, but even if it is possible, it will be probably useful only for small n.  
> **username_2**: I don't know if this is the same observation... All $x$ can be normalized to a unit vector and doesn't change the result, we can do everything in a unit n-cube centered in origin. Find which region of the cube minimize the dot product with $v_i$ for each $i$ (each region must be a polytope). I do not have a bound on the number of polytopes. If it is less than exponential in $nm$, you have something better than $O(nm)$ by doing a n-dimensional point location query.  
> **username_3**: which parameter do you care about more ? usually, if you want to get sublinear in m, you're going to start getting exponential in n.  
> **username_0**: @Suresh Well, it would be nice to understand different possible trade-offs. Approximate version is interesting too.  
> **username_4**: Quick note: for the n = 2 case, binary search on the convex hull gives $O(\log n)$ query time.  

---

## 2 answers

### Answer by username_5 on 2011-08-14. Score: 16

Consider the special case where you just want to determine if your query vector is orthogonal to some vector in your preprocessed collection. (That is, you want to determine if $\min\_i \langle x, v\_i \rangle = 0$, where the vectors under discussion have non-negative coefficients.) This case is already very interesting.

Suppose you can answer queries in $n^{O(1)} m^{1-\delta}$ time for some $\delta > 0$, with $m^{O(1)} n^{O(1)}$ preprocessing (the polynomial's degrees should not depend on $m$ or $n$ or $\delta$).

In the paper "A new algorithm for optimal 2-constraint satisfaction and its implications", I observed that such a data structure would actually allow you to solve CNF-SAT in $2^{\alpha v}$ time for some $\alpha < 1$, where $v$ is the number of variables. This would refute the "Strong Exponential Time Hypothesis" that k-SAT requires essentially $2^n$ time for unbounded $k$.

To see why, suppose the preprocessing time is bounded by $(nm)^c$. Consider a CNF formula $F$ with $v$ variables and $n$ clauses. We split the set of variables into two parts $P\_1$ and $P\_2$ of size $v(1-1/(2c))$ and $v/(2c)$, respectively. List all possible assignments to the variables in the parts (getting $2^{v(1-1/(2c))}$ and $2^{v/(2c)}$ assignments, respectively). Associate each of these partial assignments $A\_i$ with an $n$-bit vector $w\_i$ where $w\_i[j]=1$ iff the $j$th clause of $F$ is not satisfied by $A\_i$. So we have two lists of exponentially many bit vectors.

Notice that $F$ is satisfiable iff there is a vector $w\_1$ from an assignment on $P\_1$ and a vector $w\_2$ from an assignment on $P\_2$ such that $\langle w\_1, w\_2 \rangle = 0$.

Now let $m=2^{v/(2c)}$, and preprocess the assumed data structure with all vectors from part $P\_2$. This takes $n2^{v/2}$ time, by assumption. Run the query algorithm on all vectors from assignments on part $P\_1$. By assumption this takes $2^{v(1-1/(2c))} \cdot n^{O(1)} m^{1-\delta} = n^{O(1)} 2^{v - \delta v/(2c)}$. Let $\alpha = 1 - \delta/(2c)$.

Perhaps it is possible to get efficient preprocessing and $n^{O(1)} m^{1-1/(\log \log m)}$ query time with existing techniques. The best known CNF-SAT algorithms don't rule it out. (They get something like $2^{n-n/\log n}$.) But to compute $\min\_i \langle x, v\_i\rangle$ is slightly stronger -- in this setup, it would be like solving MAX CNF-SAT.

> **Comments:**
> **username_0**: Awesome! But it doesn't rule out approximate data structures as well as query times like $O(m \cdot \mathrm{poly}(\log n))$, which would be also very interesting.  
> **username_0**: By the way, can't we say something like "if there was even approximate data structure with fast query time, then MAX-SAT would be approximable".  
> **username_1**: Why does the equivalence stated in the first paragraph hold?  I think that the inner product can be negative in general.  
> **username_5**: ilyaraz: Yes, even approximate data structures would imply approximate MAX-SAT. Tsuyoshi: Thank you for your insight  

---

### Answer by username_3 on 2011-08-14. Score: 6

Here's one idea for the exact answer, that I suspect Chao Xu might be alluding to. Firstly observe that we might as well normalize $x$, as Chao points out. Now consider the hyperplane $h$ normal to the direction $x$. The goal is to find the point closest to this hyperplane. By duality, this corresponds to a ray shooting query in an arrangement of hyperplanes to find the closest plane "above" the query point. Since this can be preprocessed, the main complexity is the point location, and so your problem has now been reduced to the complexity of doing point location in an arrangement of hyperplanes. Using cuttings, this can be done in $O(\log n)$ time in $n^d$ space.

> **Comments:**
> **username_0**: I should have mentioned that I'm also interested in a reasonable preprocessing time which is not the case here if a dimension is largish.  

---

