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