Welcome to MathOverflow

Question

3

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.

edited Feb 15 2011 at 0:46

Anthony Quas
6,260●1●12●28

asked Feb 14 2011 at 21:52

mexx
31●2

	You can do one lookup by using a simple compare. XOR Y and whatever number you are examining, and if the Hamming weight of the result is at most k then you're done. Of course, this makes your one lookup more expensive, but not much: bitwise operations are cheap and you can do the integer stuff in a single byte. – Steve Huntsman Feb 14 2011 at 22:06
	yes you are right, but the file lookups are expensive as I said and I want to minimize the number of lookups for each given number Y. So, I want to be able to probabilistically predict the existence of a number before I look for it and probably shouldn't look for it if the probability of it being in the file is low. – mexx Feb 14 2011 at 22:14
	One thing which could help is looking to the sum of the digits $s(x)$ of each number. If for a number $x$ you have $\|s(x)-s(y)\| >k$ for sure $x$ is not good. This should eliminate many $x$ from your search. If you are lucky and for some $x$ you get $s(x)+s(y) \leq k$ or $s(x)+s(y) \geq 2n-k$, then you are done: $x$ works. – Nick S Feb 14 2011 at 22:53
	One more comment: the sum of teh digits completely solves the problem in the case $y=000000.000$ or $y=11111...1$. You could try the following procedure, but this is basically just the standard comparison: Look at $y$ and for each 1 switch the digits in that possition in all $x$ in your code. But this is probably more expensive than studing the Hamming distance. – Nick S Feb 14 2011 at 22:59
	Thanks Nick. But I guess, using sum to narrow down on probable matches is still going to give a lot of false positives. I am hoping if there is a better way. – mexx Feb 15 2011 at 0:26

show 4 more comments

Suresh Venkat · Accepted Answer · 2011-02-15 08:10:48Z UTC

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.

Anthony Quas · Answer 2 · 2011-02-15 00:44:58Z UTC

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.

finding numbers at k hamming distance

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.