Testing boolean vectors orthogonality with fast query-time 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 ...
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.