Computing Hamming Distance Between Binary Vectors

Question

Consider the following problem:

Input: We are given a set $S$ of $n$ binary vectors. A binary vector is of the form $(b_0, b_1, ... b_n)$, where $b_i \in \{0, 1\}$. Therefore, there are $n$ vectors of size $n$.

Output: For each vector in $S$, we would like to (efficiently) compute a list of binary vectors from $S$ whose Hamming distance is within some predefined constant $c$.

Output (alternative): Find the pair of vectors with minimum Hamming distance.

---

Clearly, the above can be done in $O(n^3)$ by computing the Hamming distance pairwise between each vector in S ($\frac{n*(n+1)}{2}$ pairwise combinations and $O(n)$ to compute the Hamming distance). However, I am looking for something more efficient, since $n$ can take large values (say, $n=10^6$).

To speed up the computation, one could use some form of hashing, where we place the binary vectors into $N$ buckets, where every vector in the $i^{th}$ bucket contains exactly $i$ ones. This could work, but in my particular case, one could expect that all binary vectors have approximately the same number of ones, so not much would be gained from such hashing. One could also look to perform some sort of compression on binary vectors and perform Hamming distance computation on the smaller compressed vectors as a bound on the distance, but I suspect there are better approaches.

Another hashing approach would be to subdivide the space into hypercubes and place each vector in one of the cubes. I believe similar approaches are used in physics simulations, where space would be divided in a number of 2D- or 3D-cubes and then compute the interaction of elements within cubes and neighboring cubes.

I have seen variations of the above in many applications, but I am not sure what is the name of the problem or how to efficiently compute the solution. It is worth noting that in my particular case the solutions does not need to be "exact", that is, there can be some errors in the output as long as "most" of it is correct. The main issue seems to be how to avoid computing the distance between vectors that are clearly far apart.

(The structure of the binary vectors in $S$ can be diverse. In some cases, there are few bits set in each vector, while in other cases the vectors can be dense. For the sparse case, the Hamming distance computation can get greatly sped up, but the bottleneck is the $\frac{n*(n+1)}{2}$ comparisons that need to be made.).

Answer 1

You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing.

For example, here is a simple LSH. Randomly choose a set of about 10,000 indices (out of the 1,000,000). Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring the other 990,000 bits entirely). Store all the vectors in a hashtable using this hash. Now look for all pairs of vectors that have the same hash. This can be done by storing all the vectors in a hashtable using this hash and looking at all collisions within a single hash bucket, or by sorting the hashes and looking at adjacent pairs.

Suppose the pair of vectors $b_i,b_j$ are at distance $\le 15$. Then with probability about 0.86, they will agree in the selected 10,000 positions and thus have the same hash. In other words, about 86% of the pairs of vectors at distance $\le 15$ will be found in this way.

Now you can repeat this multiple times to ensure you find all of the pairs, with high likelihood. If you repeat this about 10 times with a different random set of indices each time, then only about $10^{-8}$ of the pairs that are close will be missed. If you repeat it 100 times, each close pair has only a $10^{-85}$ probability to be missed. That probability is so low it can be safely ignored: essentially, all close pairs will be found.

The running time is $O(n^2)$: $O(n)$ time to compute each hash, and then you do that $n$ times for $n$ different vectors. In practice it might be even faster than that if you can take advantage of the fact that most of the bit positions are ignored during the hashing.