Question

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

Was it helpful?

Solution

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

OTHER TIPS

No. LSH is not restricted to L1 or L2(Eucliand Distance). It is just an advanced method of hyperplane partitioning or indexing, whatever you call it.

LSH will help you find the most possible KNN vectors to the query vector. Afterwards you can use l1/l2/cosine/damming code to do the detailed similarity or distance computation.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top