Find all pairs of values that are close under Hamming distance

Question

I have a few million 32-bit values. For each value, I want to find all other values within a hamming distance of 5. In the naive approach, this requires $O(N^2)$ comparisons, which I want to avoid.

I realized that if I just treated these 32-bit values as integers and sorted the list once, then values which differed only in the least significant bits ended up very close together. This allows me to have a shorter "window" or range of numbers within which I can perform actual pair-wise comparisons for the exact hamming distance. However, when 2 values vary only in the higher order bits, then they end up outside this "window" and appear in opposite ends of the sorted list. E.g.

11010010101001110001111001010110

01010010101001110001111001010110

would be very far apart, even though their hamming distance is 1. Since, the hamming distance between 2 values are preserved when both are rotated, I figured that by doing 32 left rotations and then sorting the list every time, it's likely that 2 values will end up close enough in the sorted list in at least one of them.

1. Although this approach is giving me good results, I'm struggling to formally establish the correctness of this approach.

2. Given that I'm looking for matching values having hamming distance $k$ or less, do I really need to do all 32 bit rotations? For e.g. if $k=1$ and my window size is 1000, I need to do at max 24 bit rotations because even if the stray bit appeared in any of the 8 lower order bits, the resulting numbers won't differ by more than 1000.

Answer 1

As stated, your approach is problematic, because if 2 bitmaps have evenly spaced differences then in any rotation, there will be differences on some high order bits.

You can generalize your approach by permuting the bit position in a more complex fashion. Indeed, if you select a random permutation of bits, then all differences between 2 bitmaps with distance $5$ will appear in the 16 low-order bits with probability better than $1/50$. So repeating a few hundred times you should find a very large proportion of your bitmap pairs. For each trial, the number of pairs to test (with the same 16 high bits) is close to $64\cdot N$ (for $N\approx 2^{22}$).

However, I would also try the following approach: build a list of your bitmaps modified in at most 2 bit positions and sort this list. If there are collisions within this list, you have two bitmaps within distance $4$. Then enumerate all values of your initial bitmaps modified three positions and search them in the list to find pairs of bitmaps at distance $5$. The memory cost of this approach requires storing $529\cdot N$ elements and the number of elements to search in the second phase is $4960\cdot N$.

---

Additional information:

1. The probability that $5$ differences are located in the $16$ low order bit after a random permutation of the $32$ bit-positions is just a quotient of two binomials: $$ \frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217 $$
2. Construction of the lists, for each element in the original list, put in the augmented list: the element itself, all elements differing in one position and all elements differing in two positions (keeping the information about the original element). The number of copies for each element is $1+32+\binom{32}{2}=529.$ Any collision within this list (detected after sort) corresponds to two original element at distance at most $4$. Note that each pair can be detected several times so you will need to remove duplicates (but this was already the case with your initial algorithm).
3. For the final pass, it is preferable to prune the augmented list of elements to keep only those at exact distance $2$ from their original element. Then, for each original element, create the $\binom{32}{3}=4960$ elements at distance $3$ and search them within the augmented list. Once again, you need to remove duplicates since each pair is going to be detected $\binom{5}{3}=10$ times. [With extra care, you can probably anticipate/avoid most duplicates but I am not sure whether it is worth the effort.]

Answer 2

minar's answer is excellent and is probably the right approach for this particular problem. However, I'll mention one more possible approach:

You could use a locality-sensitive hash function (LSH). A locality-sensitive hash function $H$ is designed so that if $x,y$ are close in Hamming distance, then $H(x)=H(y)$. If you have such a hash $H$, then you can store all your values into a hash table (using hash function $H$ and open hashing), and then you'll very quickly be able to find all pairs of values that are close in Hamming distance. There are various techniques for constructing a LSH; you can look at references on this topic to find several candidates.

That said, for your particular problem (with the specific parameters you mentioned), I expect minar's two algorithms will prove to be better in practice than any LSH-based scheme. I mention this only in case other readers come here to this question with a similar problem, but with different parameters where LSH might make more sense.