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.
Although this approach is giving me good results, I'm struggling to formally establish the correctness of this approach.
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.
A[i].close
of indices of near-neighbours for each string $i$? $\endgroup$