We have given a set of $n$ binary vectors each of dimension $d$, i.e. a binary matrix of $d*n$. Our goal is to group vectors which are almost similar, $\forall v_i, v_j\in\{0,1\}^d$, we say $v_i$ and $v_j$ are almost similar, if $HammingDistance(v_i,v_j)<\epsilon$. Since comparing two $d$ bit vectors are expensive, and $n$ is large, we can't afford to do $O(n^2)$ comparisons, we use Locality Sensitive Hashing algorithm to computer similarity preserving matrix in subquadratic time.

Now, my question is that how to tune parameters of LSH, i.e. # of hash tables $m$, # of entries per hash table $l$, such that error is minimizes (the number of similar items which hashes to different bucket, and the number of dissimilar items which hashes to same bucket is minimizes).

Pls let me know if I am missing something obvious.

  • 3
    $\begingroup$ I went quite elaborately through the details of how to fine tune these parameters in Chapter 20 of my book (Geometric approximation algorithms). Unfortunately, the version available online is not updated, so you would have to get your hands on a hard copy (the online version is significantly less polished for this specific chapter). $\endgroup$ Sep 18, 2014 at 1:28


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.