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. 



finding numbers at k hamming distance
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](http://www.mit.edu/~andoni/LSH/). Your case is even simpler because you know the radius you're concerned with. Alternatives include the method by [Kushilevitz, Ostrovsky and Rabani](http://www.cs.technion.ac.il/~rabani/pss/Publications/KushilevitzOR98.ps.gz). 


