11
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\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, 2013 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, 2013 at 20:43
  • $\begingroup$ see also nearest neighbor search $\endgroup$
    – vzn
    Feb 1, 2013 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, 2013 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, 2013 at 15:07

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\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, 2013 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, 2013 at 23:37
-3
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 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, 2013 at 14:53

Your Answer

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

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