11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just ideas from 20 seconds of thinking: What about a sort by Grey-Code? What about splitting the list of 32-bit bitmaps into four lists of 8-bit bitmaps and then using your technique? $\endgroup$ – Karl Damgaard Asmussen Jul 31 '13 at 17:15
  • 1
    $\begingroup$ Could you be more precise about the very large number of bitmaps ? It is close to $2^{20}$, $2^{30}$ or whatever ? $\endgroup$ – minar Jul 31 '13 at 17:26
  • $\begingroup$ @minar: I have 3-4 million of such 32-bit bitmaps. $\endgroup$ – karterk Aug 1 '13 at 3:11
  • $\begingroup$ I'm not sure what you are asking. Are you saying that you have an array $A[i]$ of 32-letter Boolean strings (large but not containing all $4\times 10^9$ possible strings), and you want to mark the pairs that have Hamming distance at most 5 in some way, perhaps by creating a linked list A[i].close of indices of near-neighbours for each string $i$? $\endgroup$ – András Salamon Aug 1 '13 at 15:29
  • $\begingroup$ think there is a similar concept of "quadtrees" except with hypercubes that is applicable. the algorithm locates & recursively locates the vectors in hypercubes, and then when you want to search "nearby" bitvectors, you only search "nearby" hypercubes. suspect it may be studied & in a paper somewhere.... not sure the correct terms.... $\endgroup$ – vzn Aug 1 '13 at 16:30
9
$\begingroup$

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 generalized 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. Built 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.]
$\endgroup$
  • $\begingroup$ For the first approach, are you saying that I permute the bitmap in some pre-determined orders instead of doing just bit rotations? Can you please explain how you got the 1/50 probability? Also, for the second approach, do I need to build an index of my list first and then for every element - generate (32C1 + 32C2) combinations and check them against this index to identify all bitmaps differing by a distance of 2? It would be great if you can explain this further. Thanks. $\endgroup$ – karterk Aug 1 '13 at 16:29
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.