Using k-NN for Exact Match in Hamming Space (after Multi-index Hashing)
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.