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

<p>You could use a <a href="https://en.wikipedia.org/wiki/Locality-sensitive_hashing">locality-sensitive hash function</a> (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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-08-01T22:29:41.033Z
2013-08-01T22:29:41.033Z
D.W.
<p>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.</p>
<p>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 <span class="math-container">$5$</span> will appear in the 16 low-order bits with probability better than <span class="math-container">$1/50$</span>. 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 <span class="math-container">$64\cdot N$</span> (for <span class="math-container">$N\approx 2^{22}$</span>).</p>
<p>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 <span class="math-container">$4$</span>. Then enumerate all values of your initial bitmaps modified three positions and search them in the list to find pairs of bitmaps at distance <span class="math-container">$5$</span>.
The memory cost of this approach requires storing <span class="math-container">$529\cdot N$</span> elements and the number of elements to search in the second phase is <span class="math-container">$4960\cdot N$</span>.</p>
<hr />
<p>Additional information:</p>
<ol>
<li>The probability that <span class="math-container">$5$</span> differences are located in the <span class="math-container">$16$</span> low
order bit after a random permutation of the <span class="math-container">$32$</span> bit-positions is
just a quotient of two binomials:
<span class="math-container">$$ \frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217
$$</span></li>
<li>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 <span class="math-container">$1+32+\binom{32}{2}=529.$</span> Any collision within this list (detected after sort) corresponds to two original element at distance at most <span class="math-container">$4$</span>. 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).</li>
<li>For the final pass, it is preferable to prune the augmented list of elements to keep only those at exact distance <span class="math-container">$2$</span> from their original element. Then, for each original element, create the <span class="math-container">$\binom{32}{3}=4960$</span> elements at distance <span class="math-container">$3$</span> and search them within the augmented list. Once again, you need to remove duplicates since each pair is going to be detected <span class="math-container">$\binom{5}{3}=10$</span> times. [With extra care, you can probably anticipate/avoid most duplicates but I am not sure whether it is worth the effort.]</li>
</ol>

CC BY-SA 3.0
2013-08-01T16:29:17.913Z
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.
karterk
CC BY-SA 4.0
2020-07-26T06:43:14.103Z
This reminds me of the "meet-in-the-middle" approach for knapsack problem.
qwr
CC BY-SA 4.0
2013-08-01T11:23:21.190Z
2022-03-31T10:42:32.960Z
2022-03-31T10:42:32.960Z
minar
<p>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. </p>

<p>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. </p>

<p><code>11010010101001110001111001010110</code></p>

<p><code>01010010101001110001111001010110</code></p>

<p>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.</p>

<ol>
<li><p>Although this approach is giving me good results, I'm struggling to formally establish the correctness of this approach. </p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2013-07-31T17:15:33.013Z
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?
Kile Kasmir Asmussen
CC BY-SA 3.0
2013-07-31T17:26:05.877Z
Could you be more precise about the very large number of bitmaps ? It is close to $2^{20}$, $2^{30}$ or whatever ?
minar
CC BY-SA 3.0
2013-08-01T03:11:25.353Z
@minar: I have 3-4 million of such 32-bit bitmaps.
karterk
CC BY-SA 3.0
2013-08-01T15:29:58.753Z
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$?
András Salamon
CC BY-SA 3.0
2013-08-01T16:30:57.790Z
think there is a similar concept of ["quadtrees"](http://en.wikipedia.org/wiki/Quadtree) 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....
vzn
CC BY-SA 3.0
2013-08-01T16:31:38.720Z
@AndrásSalamon: The basic goal is to find all bitmaps within a hamming distance of k (k=5 in my case) for each bitmap in a set of 4 million 32-bit bitmaps.
karterk
CC BY-SA 3.0
2013-08-01T16:37:06.543Z
seems similar to this question [finding closest points on a hypercube](http://cstheory.stackexchange.com/questions/16322/finding-the-closest-pair-between-two-sets-of-points-on-the-hypercube), see refs on it
vzn
CC BY-SA 3.0
2013-08-02T01:11:40.893Z
also note that if the bitvectors are not randomly/evenly distributed, an algorithm may do better or worse than the random case. so there is a question of how they are distributed. lacking any further info, could go with the assumption of random distribution.
vzn
CC BY-SA 3.0
2013-08-02T06:23:59.433Z
@vzn: In a set of 3-4M bitvectors, for each bitvector, I expect at most a few hundred vectors to be within 3-4 hamming distances. As for the distribution, I don't expect the bits to mostly differ in a specific region of the bitvectors.
karterk
CC BY-SA 4.0
2022-03-31T18:08:43.020Z
Finding nearest neighbors, closest pair and all close pairs in metric spaces is a well-studied problem. Your setting is the Hamming metric. Here is a recent paper which has pointers to some previous work. https://drops.dagstuhl.de/opus/volltexte/2021/15531/pdf/LIPIcs-FSTTCS-2021-20.pdf
Chandra Chekuri
<ds.algorithms><co.combinatorics><approximation-algorithms>
Find all pairs of values that are close under Hamming distance
karterk
# Find all pairs of values that are close under Hamming distance

(Asked by: username_0 on 2013-07-31)

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.

**Tags:** ds.algorithms, co.combinatorics, approximation-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_2**: Could you be more precise about the very large number of bitmaps ? It is close to $2^{20}$, $2^{30}$ or whatever ?  
> **username_0**: @username_2: I have 3-4 million of such 32-bit bitmaps.  
> **username_3**: 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$?  
> **username_4**: think there is a similar concept of ["quadtrees"](http://en.wikipedia.org/wiki/Quadtree) 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....  
> **username_0**: @AndrásSalamon: The basic goal is to find all bitmaps within a hamming distance of k (k=5 in my case) for each bitmap in a set of 4 million 32-bit bitmaps.  
> **username_4**: seems similar to this question [finding closest points on a hypercube](http://cstheory.stackexchange.com/questions/16322/finding-the-closest-pair-between-two-sets-of-points-on-the-hypercube), see refs on it  
> **username_4**: also note that if the bitvectors are not randomly/evenly distributed, an algorithm may do better or worse than the random case. so there is a question of how they are distributed. lacking any further info, could go with the assumption of random distribution.  
> **username_0**: @username_4: In a set of 3-4M bitvectors, for each bitvector, I expect at most a few hundred vectors to be within 3-4 hamming distances. As for the distribution, I don't expect the bits to mostly differ in a specific region of the bitvectors.  
> **username_5**: Finding nearest neighbors, closest pair and all close pairs in metric spaces is a well-studied problem. Your setting is the Hamming metric. Here is a recent paper which has pointers to some previous work. https://drops.dagstuhl.de/opus/volltexte/2021/15531/pdf/LIPIcs-FSTTCS-2021-20.pdf  

---

## 2 answers

### Answer by username_2 on 2013-08-01. Score: 9 | Accepted answer

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.]

> **Comments:**
> **username_0**: 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.  
> **username_7**: This reminds me of the "meet-in-the-middle" approach for knapsack problem.  

---

### Answer by username_6 on 2013-08-01. Score: 6

username_2'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](https://en.wikipedia.org/wiki/Locality-sensitive_hashing) (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 username_2'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.


---

