Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 '11 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 '11 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 '11 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 '11 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 '11 at 0:26

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
Thanks Anthony. The numbers are already stored in a sorted order. But what I want is to avoid all possible lookups starting from numbers at hamming distance 0 to k. So for a number Y, basically by looking at some information of the data I want to be probabilistically able to tell of its existence in the file. –  mexx Feb 15 '11 at 2:30
    
Hmmm. Sounds like you're hoping for some kind of Fourier information. I don't have a good feeling for these things, but my guess is that you would need to store vast amounts of information and do major calculations to get anything out of this (similar to what was suggested in the previous comments). <p> FWIW the algorithm I suggested (with the numbers that you offered in the question) would be expected to terminate in 256 lookups, each taking 24 steps. –  Anthony Quas Feb 15 '11 at 7:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.