0
$\begingroup$

Consider two binary strings of two alphabets of length $l$, to find the hamming distance each corresponding bit needs to be compared. The runtime will be $O(l)$ or simply $l$ many comparisons are required. The goal is to reduce the number of comparisons with error less than $t$.

My idea is to divide input strings into blocks of size two and then there will be $l/2$ many blocks will be there. From each block pick a bit at random pick a random bit from the corresponding block, and now compare the bits. Repeat the previous step for $l/2$ blocks.

Question: What is the best algorithm for approximate hamming distance in the literature with some error?

Improve this question
$\endgroup$
5
  • $\begingroup$ Divide & conquer offers no speed-up where a base algorithm's time is in $O(n)$. $\endgroup$
    – greybeard
    Commented Mar 29 at 16:12
  • 1
    $\begingroup$ Depending on the type of error you care about, you could randomly sample indices to check. Sampling $o(\ell)$ indices should be enough to get an additive error of $o(\ell)$ with high probability (via a standard chernoff bound) and in expectation. But if you expect the hamming distance to be $\ll \ell$, and you want to measure it somewhat accurately, you'll need more samples. E.g. to detect constant hamming distance you would need $\Omega(\ell)$ samples anyhow. $\endgroup$
    – Neal Young
    Commented Mar 29 at 17:05
  • $\begingroup$ @ Neal Young. Thanks. Are there papers that I can refer to to get more ideas? $\endgroup$
    – Shi
    Commented Mar 30 at 10:08
  • $\begingroup$ @Neal Young Please elaborate more on the second part. Where I can find the algorithm for the second part of your question? $\endgroup$
    – Shi
    Commented Mar 30 at 10:29
  • 1
    $\begingroup$ You mean, for estimating hamming distance when it is small (e.g. constant)? In that case you can't do better than the trivial algorithm (enumerate the indices and count the number of differences). E.g. consider trying to distinguish between Hamming distance 0 and 1. In the worst case any deterministic algorithm has to look at all $\ell$ indices. Any randomized algorithm has to look at at least $\ell/2$ in expectation to find an index where the two vectors differ. $\endgroup$
    – Neal Young
    Commented Mar 30 at 11:48

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.