<p>The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, <a href="http://www.stanford.edu/~rrwill/orthog-soda.pdf">Finding orthogonal vectors in discrete structures</a>. 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. </p>

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

CC BY-SA 3.0
2013-12-23T01:50:56.650Z
2013-12-23T01:50:56.650Z
Ryan Williams
<p>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$.</p>

<p>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)$.</p>

<p>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)$.</p>

<hr>

<p>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)$.</p>

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

CC BY-SA 3.0
2013-12-22T23:26:18.097Z
2013-12-23T00:26:09.023Z
2013-12-23T00:26:09.023Z
D.W.
<p>Consider the following problems, </p>

<p>Problem1:
<strong>INPUT</strong>: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$ <br>
<strong>TASK</strong>: 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$.</p>

<p>Problem2:
<strong>INPUT</strong>: a set $S:=\{s_1, \ldots, s_n\}$ of vectors in $d$-dimensional boolean vector space $\{0,1\}^d$ over $\mathbb{F}_2$<br>
<strong>TASK</strong>: 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$.</p>

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

<p>In particular, I was wondering whether we can adapt <a href="http://en.wikipedia.org/wiki/Range_searching" rel="nofollow">range searching</a> techniques (I'm thinking about kd-trees or similar partitioning trees) to the problems above ...</p>

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

CC BY-SA 3.0
2013-12-22T05:58:38.697Z
when you say "boolean vector space", do you mean $\{0, 1\}^d$ taken as vectors over $\mathbb{F}_2$?
Sasho Nikolov
CC BY-SA 3.0
2013-12-22T10:47:50.777Z
Hi Sasho, thanks for comment, yes I do mean $\mathbb{F}_2$.
XORwell
CC BY-SA 3.0
2013-12-22T21:55:49.733Z
There's a question (http://cstheory.stackexchange.com/questions/7719/a-data-structure-for-minimum-dot-product-queries/7736#7736) 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.
Suresh Venkat
CC BY-SA 3.0
2013-12-22T22:30:55.907Z
@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$).
D.W.
CC BY-SA 3.0
2013-12-22T22:54:56.363Z
@D.W. ah good catch.
Suresh Venkat
CC BY-SA 3.0
2013-12-22T22:56:12.073Z
@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.
Suresh Venkat
CC BY-SA 3.0
2013-12-23T11:05:22.540Z
Thank you all for the answers, I now begin to study Ryan work. Your comments and Ryan topic http://cstheory.stackexchange.com/questions/7719/a-data-structure-for-minimum-dot-product-queries/7736#7736, made me think about another question of interest: Consider Problem1, finding all orthogonal vectors.
Does anyone believe $O(n\cdot\text{poly}(\log d))$ query-time (and $\text{poly}(n,d)$ preprocessing/space) to be possible for $n$ boolean vectors over $\{0,1\}^d$ **but** with orthogonality computed over $\mathbb{R},\mathbb{Z}$, instead of finite fields ?
XORwell
<cc.complexity-theory><ds.algorithms><cg.comp-geom><ds.data-structures>
Testing boolean vectors orthogonality with fast query-time
XORwell
# Testing boolean vectors orthogonality with fast query-time

(Asked by: username_0 on 2013-12-22)

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](http://en.wikipedia.org/wiki/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 ...

**Tags:** cc.complexity-theory, ds.algorithms, cg.comp-geom, ds.data-structures
> **Comments:**
> **username_1**: when you say "boolean vector space", do you mean $\{0, 1\}^d$ taken as vectors over $\mathbb{F}_2$?  
> **username_0**: Hi Sasho, thanks for comment, yes I do mean $\mathbb{F}_2$.  
> **username_2**: There's a question (http://cstheory.stackexchange.com/questions/7719/a-data-structure-for-minimum-dot-product-queries/7736#7736) 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.  
> **username_3**: @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$).  
> **username_2**: @D.W. ah good catch.  
> **username_2**: @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.  
> **username_0**: Thank you all for the answers, I now begin to study Ryan work. Your comments and Ryan topic http://cstheory.stackexchange.com/questions/7719/a-data-structure-for-minimum-dot-product-queries/7736#7736, made me think about another question of interest: Consider Problem1, finding all orthogonal vectors. Does anyone believe $O(n\cdot\text{poly}(\log d))$ query-time (and $\text{poly}(n,d)$ preprocessing/space) to be possible for $n$ boolean vectors over $\{0,1\}^d$ **but** with orthogonality computed over $\mathbb{R},\mathbb{Z}$, instead of finite fields ?  

---

## 2 answers

### Answer by username_4 on 2013-12-23. Score: 10

The "offline" version of this question is addressed in my SODA 2014 paper with Huacheng Yu, [Finding orthogonal vectors in discrete structures](http://www.stanford.edu/~rrwill/orthog-soda.pdf). 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.


---

### Answer by username_3 on 2013-12-22. Score: 1

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.


---

