19
$\begingroup$

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.


$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Aug 13 '11 at 13:13
  • $\begingroup$ 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. $\endgroup$ – Chao Xu Aug 13 '11 at 15:14
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Aug 14 '11 at 5:25
  • $\begingroup$ @Suresh Well, it would be nice to understand different possible trade-offs. Approximate version is interesting too. $\endgroup$ – ilyaraz Aug 14 '11 at 5:59
  • $\begingroup$ Quick note: for the n = 2 case, binary search on the convex hull gives $O(\log n)$ query time. $\endgroup$ – Geoffrey Irving May 17 '13 at 18:37
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ilyaraz Aug 14 '11 at 9:01
  • $\begingroup$ 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". $\endgroup$ – ilyaraz Aug 14 '11 at 9:06
  • $\begingroup$ Why does the equivalence stated in the first paragraph hold? I think that the inner product can be negative in general. $\endgroup$ – Tsuyoshi Ito Aug 14 '11 at 12:41
  • $\begingroup$ ilyaraz: Yes, even approximate data structures would imply approximate MAX-SAT. Tsuyoshi: Thank you for your insight $\endgroup$ – Ryan Williams Aug 14 '11 at 15:47
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – ilyaraz Aug 14 '11 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.