Suppose I have two vectors $V_1, V_2 \in R^l$. Can they be converted into bit vectors $B_1,B_2 \in \{0,1\}^l $ such that if $V_1, V_2$ is close in Euclidean distance, $B_1,B_2$ is close in hamming distance?

Please note that this is a little different from locality sensitive hashing, where each vector will be hashed into a bucket with certain probability and $l$ such hash functions will be combined to generate $B_i$. The problem appears to be simpler than that as I am not concerned with dimensionality reduction, which is a goal of LSH.

Side note: Please feel free to add new tags as I am not sure which tags should go here.

  • 1
    $\begingroup$ So what's wrong with using locality sensitive hashing (LSH) for this? Sure, it might achieve more than you need, but it sounds like it does achieve what you want. Am I missing something? See, e.g., mit.edu/~andoni/papers/CACM-article.ps $\endgroup$ – D.W. Mar 28 '14 at 22:49
  • $\begingroup$ LSH can certainly be used, but I was wondering if there are other solutions for this. $\endgroup$ – rivu Mar 29 '14 at 0:14
  • 1
    $\begingroup$ I assume you also want that if the $V_i$ are far apart, then the $B_i$ are as well, right? In this case, the idea of partitioning $\mathbb{R}^\ell$ by $\ell$ hyperplanes (which is what LSH will do, but with fewer hyperplanes) is pretty natural, and not that hard to analyze. Whether there is a deterministic approach is interesting. $\endgroup$ – Louis Mar 29 '14 at 10:13
  • $\begingroup$ I am only offerring a suggestion here so don't be cross with me if I might be wrong but I have a hunch that this can be done by augmenting a kd-tree to encode the nearest neighbours. $\endgroup$ – Francesco Gramano Apr 9 '14 at 7:50

Your Answer

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

Browse other questions tagged or ask your own question.