2
$\begingroup$

We have unsorted array of hashes, each hash is a 64bit integer. We need to find the pairwise hamming distance in an array. What state the problem to find maximum Manhattan distance between points in 64Bit space where each dimension has only 0 and 1 state.

The simplest solution is:

  • just pick each item one-by-one
  • and compare (find the hamming distance) with the rest items starting for this one.

That gives us $O(N^2)$ complexity, where $N$ is length of list. But can we do better because of nature of Hamming distance and nature of 64bit numbers? Could we use binary operations here?

$\endgroup$
9
  • 2
    $\begingroup$ Hamming distance satisfies the triangle inequality $d(a,b)+d(b,c) \ge d(a,c)$. You can use this to skip some computations if all you need is the biggest Hamming distance of any pair. Note sure whether this is enough to get below $O(N^2)$ and what a good algorithm using that fact would look like. $\endgroup$
    – quarague
    Commented Feb 1, 2019 at 11:55
  • 2
    $\begingroup$ Do you need it exactly? Can you live with decent bounds on it? For instance, it is $O(N)$ to compute the ($\mathbb{F}_2$) mean, and then to find the node furthest from this. Twice this distance gives you a $2$-approximation. $\endgroup$ Commented Feb 1, 2019 at 19:53
  • $\begingroup$ @stochasticboy321 wouldn't a $2-$ approximate solution be useless if it outputs an guess $\geq n/2$? $\endgroup$
    – kodlu
    Commented Feb 3, 2019 at 0:56
  • $\begingroup$ I mean because the max distance is very likely quite close to $n=64$ the bitlength. $\endgroup$
    – kodlu
    Commented Feb 3, 2019 at 1:17
  • $\begingroup$ @kodlu I mean then its a little obvious that you would report 64 as the upper bound. Really it depends on the application, although I agree that for fixed string-lengths a $2$-approximation would be kinda weak. In any case, my question really was trying to get at if approximate solutions could be acceptable, and how good they'd need to be. Essentially since bringing in some randomised algorithm might get to some decent approximation at $o(N^2).$ $\endgroup$ Commented Feb 3, 2019 at 4:03

0

You must log in to answer this question.

Browse other questions tagged .