7
$\begingroup$

Consider the following problems,

Problem1: INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a way that the following queries can be solved as fast as possible: given a query vector $x\in\{0,1\}^d$, find every $s\in S$ that is orthogonal (or non orthogonal, by complementarity) to $x$.

Problem2: INPUT: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$
TASK: preprocess INPUT in such a way that the following queries can be solved as fast as possible: given a query vector $x\in\{0,1\}^d$, decide whether $S$ contains a vector orthogonal to $x$.

I'm in deep search of fast methods, i.e. faster than naive inspection! Also complexity lower bounds, or any other known reference ...

In particular, I was wondering whether we can adapt range searching techniques (I'm thinking about kd-trees or similar partitioning trees) to the problems above ...

Also, I wonder whether Random Projection or (Jaccard index, angle, cosine based) Similarity Search methods might provide good speed-up ...

$\endgroup$
  • $\begingroup$ when you say "boolean vector space", do you mean $\{0, 1\}^d$ taken as vectors over $\mathbb{F}_2$? $\endgroup$ – Sasho Nikolov Dec 22 '13 at 5:58
  • $\begingroup$ Hi Sasho, thanks for comment, yes I do mean $\mathbb{F}_2$. $\endgroup$ – XORwell Dec 22 '13 at 10:47
  • 2
    $\begingroup$ There's a question (cstheory.stackexchange.com/questions/7719/…) that asks for not just the decision, but the vector of minimum dot product. Ryan Williams' answer there answers your question here. If you agree, you can flag this for being marked as duplicate - I didn't want to do it without letting you check first. $\endgroup$ – Suresh Venkat Dec 22 '13 at 21:55
  • $\begingroup$ @SureshVenkat, no, I don't think Ryan Williams' answer solves this problem. His answer is for $\mathbb{R}$ or $\mathbb{Z}$. But this question is about the dot-product over $\mathbb{F}_2$, which is different. Ryan Williams' reduction fails because of this: if we know that $\langle w_1,w_2 \rangle = 0$ over $\mathbb{R}$ and that $w_1,w_2 \in \{0,1\}^n$, we know there is no index $i$ such that $(w_1)_i = (w_2)_i = 1$. However that's not true if we are working over $\mathbb{F}_2$ (if $w_1 \cdot w_2 = 0$ over $\mathbb{F}_2$, there can be an index $i$ where $(w_1)_i = (w_2)_i = 1$). $\endgroup$ – D.W. Dec 22 '13 at 22:30
  • 2
    $\begingroup$ @XORwell following up after D.W's comment: in $\mathbb{F}_2$, one bit can make the difference between orthogonal and not, which makes me worry that nothing is going to help you without further assumptions/structure. $\endgroup$ – Suresh Venkat Dec 22 '13 at 22:56
10
$\begingroup$

The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, Finding orthogonal vectors in discrete structures. For the case of $\mathbb F_2$, we give an $O(nd)$ time algorithm for determining, given two sets of $n$ vectors $A$ and $B$, whether there is a vector in $A$ and vector in $B$ with zero inner product.

I'm sure you can modify our algorithm appropriately, and get an interesting preprocessing/query version; we did not consider this question.

$\endgroup$
1
$\begingroup$

Your second problem has an efficient answer. In particular, after preprocessing, each query can be answered in at most $O(d^2)$ time. This will be a big performance gain if $d \ll n$.

Let's start by considering the variant where we want to test whether $S=\{s_1,\dots,s_n\}$ contains a vector that is non-orthogonal to $x$. The answer will be "No" exactly if $s_i \cdot x = 0$ for all $i$. Form the $n\times d$ matrix $M$ whose $i$th row is $s_i$; then the answer to the query will be "No" exactly if $Mx=0$. Notice that we can form a new matrix $M'$ containing at most $d$ rows, such that $Mx=0$ if and only if $M'x=0$. (In particular, consider the subspace of $\mathbb{F}_2^d$ spanned by $s_1,s_2,\dots,s_n$; let $t_1,\dots,t_{n'}$ be a basis for this space, and define $M'$ to be a $n' \times d$ matrix whose $i$th row is $t_i$.) In a preprocessing step, we can compute the matrix $M'$. To answer each query $x$, we can simply compute $M'x$; if $M'x=0$, then answer "No", otherwise answer "Yes". The running time to answer the query is the time to multiply a $n' \times d$ matrix by a $d$-vector, where $n' \le d$; this is at most $O(n'd) = O(d^2)$.

What about the original version of the problem, where we are given a vector and we want to decide whether $S$ contains a vector that is orthogonal to $x$? Well, we can solve this with a very similar strategy. Define $S'=\{s'_1,\dots,s'_n\} \subseteq \mathbb{F}_2^{d+1}$ where $s'_i = (s_i,1)$, and define $x'= (x,1)$ (extend each vector by adding a single 1 to the end). Now notice that $s_i \cdot x = 1$ if and only if $s'_i \cdot x' = 0$. Therefore, $S$ contains a vector that is orthogonal to $x$ if and only if $S'$ contains a vector that is non-orthogonal to $x'$. Therefore, we can preprocess the set $S'$ using the technique of the previous paragraph, then test whether $S'$ contains a vector that is non-orthogonal to $x$. This increases the dimension from $d$ to $d+1$, so the running time to answer each query is $O((d+1)^2) = O(d^2)$.


I doubt that your first problem will have any general solution that is much more efficient than the naive approach of testing $x$ against each element of $S$, one by one. The naive approach has running time $\Theta(nd)$. If $x$ and each element of $S$ are distributed uniformly at random, then you'd expect about $n/2$ elements of $S$ to be orthogonal to $x$, so there doesn't seem to be much room for hope for a general solution whose running time is asymptotically better than $d \times n/2 = \Theta(nd)$.

If you know something about the distribution on your vectors or if they have some structure, perhaps one could do something better in that specific setting -- but I wouldn't expect to see a generally applicable algorithm that doesn't make use of that kind of additional information.

$\endgroup$

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.