2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.