Given two subsets of the $d$-dimensional hypercube (i.e., $M, N \subseteq \{0,1\}^d$), I am looking for an algorithm which retrieves the points $m\in M, n\in N$ s.t. the hamming distance (or $L_1$-distance on the hypercube) $d_H(m,n)$ is minimal. The naive algorithm which checks just each pair needs $|M|\cdot |N| \cdot d$ time, is there any better result known?

For simplicity we may assume that $|M|=|N|=d$.

  • $\begingroup$ hmmm. is there any more motivation/application? suspect there is a multidimensional analog of this euclidean/planar algorithm but wikipedia doesnt cite anything & havent heard of it elsewhere.... it might help to look for an algorithm for n-dim vectors. the beginning of the article seems to assert it can be solved in $O(n \log n)$ for higher dimensions $d>2$ but gives no citation. maybe somewhere in the refs? $\endgroup$ – vzn Feb 1 '13 at 19:08
  • 1
    $\begingroup$ The divide and conquer argument relies on a packing bound. In higher dimensions, this introduces a $2^d$ factor in the recurrence, but the dependence on $n$ remains the same. So if you don't mind terms exponential in $d$, you can use this approach. If you want something exact, you're unlikely to be able to do any better. $\endgroup$ – Suresh Venkat Feb 1 '13 at 20:43
  • $\begingroup$ see also nearest neighbor search $\endgroup$ – vzn Feb 1 '13 at 21:15
  • 1
    $\begingroup$ This seems unlikely. Think about n+m random strings on the hypercube. Somehow the hamming distance of each pair is roughly d/2, and you have to check all pairs to find the closest pair. $\endgroup$ – Sariel Har-Peled Feb 2 '13 at 5:55
  • $\begingroup$ @Sariel Har-Peled: As Suresh wrote, the problem can be solved in time O(n log n) (where n=max{|M|,|N|}) for any constant d. Therefore, “you have to check all pairs to find the closest pair” does not sound correct to me. $\endgroup$ – Tsuyoshi Ito Feb 3 '13 at 15:07

Just realized that you are asking for the case that $|M|=|N|=d$. Then you can do matrix multiplication, right? Write $M$ is a row matrix $X$, $N$ as a column matrix $Y$, negate the entries of $Y$, and compute the matrix $Z=XY$. Clearly, the $z_{i,j}$ is the Hamming distance between the $i$th point of $M$ and the $j$th point of $N$. According to the last breakthroughs this has running time $O(d^{2.3727})$ (but I have a 50,000 pages manuscript that shows how to do this matrix multiplication in $O(d^{2.3726999999})$ time by a really simple algorithm).

You can get similar effect if the matrices are not squares. I think Uri Zwick has a paper about fast matrix multiplication in this case.

In some sense, this is not too interesting - we want to avoid the $O(|M| * |N|)$ term. The improvements in the $d$ term are kind of meh, meh...

  • $\begingroup$ Great find. On another note, a colleague of mine found this paper: toc.cse.iitk.ac.in/articles/v008a014/v008a014.pdf and only now I realize that it was (also) written by you. Page 17+ is particularly interesting.. $\endgroup$ – HdM Feb 4 '13 at 11:35
  • $\begingroup$ Yes. Looks familiar - but notice that this is approximation - Suresh asked for the exact result... $\endgroup$ – Sariel Har-Peled Feb 4 '13 at 23:37

as in the comments this problem is generally closely connected to the same problem in a Hilbert space and algorithms there are nearly applicable. an example of this can be found in this paper by Arya et al [1] p29 where the authors benchmark their Hilbert space nearest neighbor algorithm using the boolean cube and the $L_\infty$ norm. their algorithm works on any $L_m$ Minkowski metric. as you point out (but wikipedia does not seem to nor do a lot of other refs) the Hamming distance metric is equivalent to the $L_1$ Minkowski space metric or "taxicab metric" on binary coordinates. their algorithm takes $ O(dn \log n)$ preprocessing time ($d$ dimensions) and logarithmic "query" time (per point). see also [2]

[1] An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions Arya et al, 30pp

[2] Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering Cazals

  • 1
    $\begingroup$ the query time bound proved in Arya et al is $\Omega(d^d)$. any trivial algorithm does better on a hypercube. they do argue on p.29 that experiments suggest the bound to be too pessimistic but they only look at dimension <= 16. $\endgroup$ – Sasho Nikolov Feb 4 '13 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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