Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing) Before the Question:
Greene, Parnas and Yao presented a scheme which, for binary data chosen uniformily a random,
 retrieves all points within Hamming distance r of a given point in time $O(d n^{r/d})$ using $O(d n^{1+r/d})$. 
The scheme is based on Turán's graph and the complete description can be found 
here.

I was reading this paper 
Fast Exact Search in Hamming Space with Multi-Index Hashing.
and realised there is nothing written WHEN r=0, that is, how to find an EXACT MATCH using neighbour search.

The question is concerned with EXACT MATCH (r=0) of an exact k-NN search in Hamming Space using Multi-index Hashing.
I'm not interested in the first nearest element. 
I would like a data structure that answer the existence of an element inside a set. 
Is it possible to make such a data structure?

What is the complexity of the Yao's algorithm or Norouzi's algorithm when r=0?
I think it is not only make r=0 in the above complexities to get the answer...
You don't need sophisticated data structures or algorithms to handle this case.   Exact match (r=0) just means that you want to store a set $S$ of points in a way so that, given $x$, you can test whether $x$ is in $S$.  If you have a set $S$ and want to be able to query whether a point $x$ is in the set, then standard data structures suffice.  You don't need anything fancy: you can just store all the points of the set in a hashtable.  Queries just involve a lookup into the hashtable.  Or, you can use a balanced binary tree, or any other standard dictionary data structure.

The running time per query is basically expected $O(d)$ time or $O(d \lg n)$ time, where $d$ is the number of dimensions, if you choose the data structures appropriately.  This is essentially optimal, since even just reading the point takes $O(d)$ time.  In principle, you could get the running time down to expected $O(\lg n)$ time per query, if you cared, by taking a random projection onto a subset of $O(\lg n)$ coordinates, though I'm not sure whether it'll be significantly faster in practice.