# 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.