# Finding the closest pair between two sets of points on the hypercube

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$.

-
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? –  vzn Feb 1 '13 at 19:08
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. –  Suresh Venkat Feb 1 '13 at 20:43
see also nearest neighbor search –  vzn Feb 1 '13 at 21:15
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. –  Sariel Har-Peled Feb 2 '13 at 5:55
@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. –  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...

-
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.. –  HdM Feb 4 '13 at 11:35
Yes. Looks familiar - but notice that this is approximation - Suresh asked for the exact result... –  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]

-
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. –  Sasho Nikolov Feb 4 '13 at 14:53