finding numbers at k hamming distance Guys,
I have N < 2^n randomly generated n-bit numbers stored in a file the lookup for which is expensive. Given a number Y, I have to search for a number in the file that is at most k hamming dist. from Y. Now this calls for a  C(n 1) + C(n 2) + C(n 3)...+C(n,k) worst case lookups which is not feasible in my case. I tried storing the distribution of 1's and 0's at each bit position in memory and prioritized my lookups.
So, I stored probability of bit i being 0/1:

Pr(bi=0), Pr(bi=1) for all i from 0 to n.

But it didn't help much since N is too large and have almost equal distribution of 1/0 in every bit location. Is there a way this thing can be done more efficiently. For now, you can assume n=32, N = 2^24.   
 A: If you're willing to live with approximations, then the standard approach to near-neighbor search (or in your case fixed radius search) in a Hamming space is by using locality-sensitive hashing. Your case is even simpler because you know the radius you're concerned with. Alternatives include the method by Kushilevitz, Ostrovsky and Rabani. 
A: I think there is a better way. With the parameters you mention there are 256 times more possible numbers than are in the table. If you look at the Hamming neighbourhood of a point $x$ of radius $r$, then it contains $M_r$ points, where $M_r=\binom{n}{0}+\binom{n}{1}+\ldots+\binom{n}{r}$. In your case $n=32$, $M_0=1$, $M_1=33$, $M_2=529$ and $M_3=5489$. What this means is that you are very likely to find something in a 2-ball and essentially guaranteed to find something in a 3-ball.

I would suggest:

(1) sorting the numbers in your table. It's well known that this can be done in $M\log M$ steps;

(2) Now given a single number $y$, you can use binary search to see if it's in the table in $\log M$ steps. (You can improve by a factor this since you have a good idea where $y$ would occur in the table). You could then test all of the 1-Hamming neighbours of $y$, the 2-Hamming neighbours etc until you get a match. In practice you can probably speed this up further because you can test things near where $y$ should be in the table to see if there are Hamming neighbours that differ in the low order bits only - not clear whether this is worthwhile.
