Search code examples
c++opencvsiftknnorb

LSH for fast NN similarity search based on hamming distance?

I am investigating the fast NN search over multi dimensional vectors. (Like searching for similar images after having extracted and computed feature vectors)

I am currently using ORB that describes its keypoints with a bit strings.
To compare 2 descriptors ORB needs Hamming Distance.

I have read taht LSH computes its hash tables based on Eucliand Distance (L2) or Manathann distance (L1). Does this mean that LSH isn't an option for vectors comparison that need Hamming Distances?

Edit

LSH can work with hamming distance because it makes hash table based on substrings on the intial bit strings, that's why it works

Solution

  • Hamming distance is equivalent to L1 (Manhattan) distance restricted to boolean vectors.