<p>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).</p>

<p>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.</p>

<p>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...</p>

CC BY-SA 3.0
2013-02-04T11:35:55.643Z
Great find. On another note, a colleague of mine found this paper: http://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
CC BY-SA 3.0
2013-02-04T23:37:28.007Z
Yes. Looks familiar - but notice that this is approximation - Suresh asked for the exact result...
Sariel Har-Peled
CC BY-SA 3.0
2013-02-03T21:27:45.427Z
2013-02-03T21:27:45.427Z
Sariel Har-Peled
<p>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 <a href="http://en.wikipedia.org/wiki/Taxicab_geometry" rel="nofollow">"taxicab metric"</a> on binary coordinates. their algorithm takes $ O(dn \log n)$ preprocessing time ($d$ dimensions) and logarithmic "query" time (per point). see also [2]</p>

<p>[1] <a href="http://www.cs.umd.edu/~mount/Papers/dist.pdf" rel="nofollow">An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions</a> Arya et al, 30pp</p>

<p>[2] <a href="http://dl.acm.org/citation.cfm?id=276884.276910" rel="nofollow">Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering</a> Cazals</p>

CC BY-SA 3.0
2013-02-04T14:53:44.267Z
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
CC BY-SA 3.0
2013-02-03T16:19:24.150Z
2013-02-03T16:19:24.150Z
vzn
<p>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?</p>

<p>For simplicity we may assume that $|M|=|N|=d$.</p>

CC BY-SA 3.0
2013-02-01T19:08:17.613Z
hmmm. is there any more motivation/application? suspect there is a multidimensional analog of this [euclidean/planar algorithm](http://en.wikipedia.org/wiki/Closest_pair_of_points#Planar_case) 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
CC BY-SA 3.0
2013-02-01T20:43:58.077Z
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
CC BY-SA 3.0
2013-02-01T21:15:00.773Z
see also [nearest neighbor search](http://en.wikipedia.org/wiki/Nearest_neighbor_search)
vzn
CC BY-SA 3.0
2013-02-02T05:55:18.443Z
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
CC BY-SA 3.0
2013-02-03T15:07:45.257Z
@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
CC BY-SA 3.0
2013-02-03T21:14:22.983Z
@TsuyoshiIto The problem can be solved in linear time in constant dimension. I am assuming implicitly that $$d=\Omega(\log n)$$, which is required since you are talking about binary strings - and you need these many dimensions to have that many strings. Except that the question asks for sets of size d. Missed that.
Sariel Har-Peled
CC BY-SA 3.0
2013-02-03T21:21:42.853Z
@Sariel Har-Peled: Oops, thanks, I stand corrected.  Indeed, the current problem would not make sense in a constant dimension.  Still I wonder why we have to spend Ω(|M||N|d) time in the case of random strings.  Is there a better reason than “we cannot immediately see a faster algorithm”?
Tsuyoshi Ito
<cg.comp-geom>
Finding the closest pair between two sets of points on the hypercube
HdM
# Finding the closest pair between two sets of points on the hypercube

(Asked by: username_0 on 2013-02-01)

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

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: hmmm. is there any more motivation/application? suspect there is a multidimensional analog of this [euclidean/planar algorithm](http://en.wikipedia.org/wiki/Closest_pair_of_points#Planar_case) 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?  
> **username_2**: 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.  
> **username_1**: see also [nearest neighbor search](http://en.wikipedia.org/wiki/Nearest_neighbor_search)  
> **username_3**: 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.  
> **username_4**: @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.  
> **username_3**: @TsuyoshiIto The problem can be solved in linear time in constant dimension. I am assuming implicitly that $$d=\Omega(\log n)$$, which is required since you are talking about binary strings - and you need these many dimensions to have that many strings. Except that the question asks for sets of size d. Missed that.  
> **username_4**: @Sariel Har-Peled: Oops, thanks, I stand corrected.  Indeed, the current problem would not make sense in a constant dimension.  Still I wonder why we have to spend Ω(|M||N|d) time in the case of random strings.  Is there a better reason than “we cannot immediately see a faster algorithm”?  

---

## 2 answers

### Answer by username_3 on 2013-02-03. Score: 7 | Accepted answer

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

> **Comments:**
> **username_0**: Great find. On another note, a colleague of mine found this paper: http://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..  
> **username_3**: Yes. Looks familiar - but notice that this is approximation - Suresh asked for the exact result...  

---

### Answer by username_1 on 2013-02-03. Score: -3

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"](http://en.wikipedia.org/wiki/Taxicab_geometry) 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](http://www.cs.umd.edu/~mount/Papers/dist.pdf) Arya et al, 30pp

[2] [Effective nearest neighbors searching on the hyper-cube, with applications to molecular clustering](http://dl.acm.org/citation.cfm?id=276884.276910) Cazals

> **Comments:**
> **username_5**: 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.  

---

