Even Faster Algorithm for the Chamfer Distance

In this paper we make a substantial progress towards reducing the gap between the upper and lower bounds for this problem. In particular, we show the following theorem. Assume a Word RAM model where both the input coordinates and the memory/processor word size is $𝒪(\log n)$ bits.³³3In the Appendix, we adopt the reduction of [8] to extend the result to coordinates of arbitrary finite precision. Then:

Thus, we reduce the gap between upper and lower bounds from $𝒪(\log (n)/{\epsilon }^2)$ to
$𝒪(\log \log n+\log \frac{1}{\epsilon })/{\epsilon }^2)$.

For any integers $a\ge 1$, we use $[n]$ to denote the set of all integers from $1$ to $n$. For any two real numbers $a,b$ such that $a\le b$, we use $[a,b]$ to denote the set of all reals from $a$ to $b$. Let $d$ be the dimension of points.

For any $q\in {ℝ}^d$, define ${\mathrm{𝗈𝗉𝗍}}_q^P:={\min }_{p\in P}{\parallel q-p\parallel }_1$ for some subset $P$ of ${ℝ}^d$. We will omit the superscript $P$ when it is clear in the context.

For any $x\in {[0,\alpha ]}^d$ and any integer $k$ such that $0\le k\le t$, let $h_k(x):=(\lceil \frac{{\overrightarrow{x}}_1+{\overrightarrow{z}}_1}{2^k}\rceil ,\lceil \frac{{\overrightarrow{x}}_2+{\overrightarrow{z}}_2}{2^k}\rceil ,$ $\mathrm{\cdots },\lceil \frac{{\overrightarrow{x}}_d+{\overrightarrow{z}}_d}{2^k}\rceil )$, where $z$ is the random point drawn on Line 1 in Figure 1. Observe that $h_k(x)$ is related to the prefix of $h{(x)}^{\top }$.

If $h{(q)}^{\top }$ and $h{(p)}^{\top }$ share a common prefix of length at least $d(t-k)$, then in hashes $h(q)$ and $h(p)$, the first $(t-k)$ bits of all $d$ coordinates are the same. $h_k(q)$ and $h_k(p)$ compute exactly these bits, thus $h_k(q)=h_k(p)$. The reverse direction holds symmetrically. $\mathrm{⊲}$

Claim 2 justifies using $h_k(\cdot )$’s as an alternative representation of the binary string $h{(\cdot )}^{\top }$. [8] shows that $h_k$ has a locality-sensitive property, which will help us to bound the distance between points.

We now show that if two points have the same hash $h_k$, then their distance is likely not too much greater than $2^k$. A straight-forward bound follows from the diameter of the $d$-dimensional cube.

Observe that $h_k(q)=h_k(p)$ only if $q+z$ and $p+z$ are in the same $d$-dimensional cube of side-length $2^k$. The diameter of such a cube under the ${\mathrm{\ell }}_1$ norm is $2^k\cdot d$. Therefore, for any $q,p$ and $0\le k\le t$, ${\parallel q-p\parallel }_1\le 2^k\cdot d$ is a necessary condition for $h_k(q)=h_k(p)$ to hold. $◀$

Moreover, using Claim 3, we can bound this ratio with respect to $n$.

We show the contrapositive that with probability $1-𝒪(1/n)$, implies $h_k(q)\ne h_k(p)$ simultaneously for all $q\in Q$ and $p\in P$. It suffices to argue that for any fixed pair of points $q\in Q$ and $p\in P$, this holds with probability at least $1-𝒪(1/n^3)$. The lemma then follows by a union bound over $n^2$ pairs.

Let $k_0$ denote the largest integer $k$ that satisfies . Then we have

i.e., with probability at least $1-𝒪(1/n^3)$, $h_{k_0}(q)\ne h_{k_0}(p)$. Also, it is easy to see that if $h_{k_0}(q)\ne h_{k_0}(p)$, then for all $k\le k_0$, $h_k(q)\ne h_k(p)$, concluding the claim. $◀$

Symmetrically, if we define $h_k^{\prime }(x):=(\lceil \frac{{\overrightarrow{x}}_1+{\overrightarrow{z^{\prime }}}_1}{2^k}\rceil ,\lceil \frac{{\overrightarrow{x}}_2+{\overrightarrow{z^{\prime }}}_2}{2^k}\rceil ,\mathrm{\cdots },\lceil \frac{{\overrightarrow{x}}_d+{\overrightarrow{z^{\prime }}}_d}{2^k}\rceil )$, the claims and lemmas above also hold for $h_k^{\prime }$. Using these, we show that the expected outputs of the QuadTree algorithm are (crude) estimations of the nearest neighbor distances.

We assume the success case of Lemma 5 for both $h_k$ and $h_k^{\prime }$. Fix an arbitrary $q_i\in Q$. Recall that the QuadTree algorithm finds $p,p^{\prime }\in P$ for $q_i$, which are associated with longest common prefixes of lengths $l,l^{\prime }$, respectively. For integer $k:0\le k\le t$, let ${ℰ}_k$ denote the event . Observe from Claim 2 that when ${ℰ}_k$ happens,

• $\mathrm{■}$

  either $l\ge l^{\prime }$ and $h_k(q_i)=h_k(p)$,

• $\mathrm{■}$

  or $l^{\prime }>l$ and $h_k^{\prime }(q_i)=h_k^{\prime }(p^{\prime })$.

In both cases, we know from Lemma 4 and 5 that ${𝒟}_i\le 2^k\cdot \min (d,3\log n)$.

Let $D:=\min (d,3\log n)$, $p^{\ast }:={\arg \min }_{p\in P}{\parallel q_i-p\parallel }_1$, and $k^{\ast }:=\lceil \log ({\mathrm{𝗈𝗉𝗍}}_{q_i})\rceil$. We have

where the second inequality holds because ${ℰ}_k$ implies that neither pair $\{h{(q_i)}^{\top },h{(p^{\ast })}^{\top }\}$ nor $\{h^{\prime }{(q_i)}^{\top },h^{\prime }{(p^{\ast })}^{\top }\}$ share a common prefix of length $\ge d(t-k+1)$. Thus $h_{k-1}(q_i)\ne h_{k-1}(p^{\ast })$ and $h_{k-1}^{\prime }(q_i)\ne h_{k-1}^{\prime }(p^{\ast })$ by Claim 2.

Moreover, events ${ℰ}_k$ for all $k$ form a partition of a sample space, so ${\sum }_k\text{Pr}\left[{ℰ}_{\mathrm{k}}\right]\le 1$. Applying this and the locality sensitive properties of $h_{k-1}$ and $h_{k-1}^{\prime }$, we get

$◀$

We assume without loss of generality that both $d,t$ are powers of $2$. Computing the binary matrix representation of $h(x)$ can be done in $𝒪(d)$ time since $t=𝒪(\log n)$. Given this, we compute $h{(x)}^{\top }$ as follows.

We partition the matrix into $t$-by-$t$ square submatrices, denoted by

For each $i\in [d/t]$, we use a recursive subroutine $\text{Transpose}(M_i,t)$ to compute $M_i^{\top }$. See Figure 2 for a pictorial illustration of the Transpose algorithm.

The correctness of the Transpose algorithm can be shown by induction on (the base-$2$ logarithm of) $w$. When $I=J=t=𝒪(\log n)$, Line 2a and 3a can be done using a constant number of operations on words. Thus we get the following runtime.

We execute the Transpose algorithm for all $i$, which takes $𝒪((d/t)\cdot t\log t)=𝒪(d\log \log n)$. Then we can write down $h{(x)}^{\top }$ by concatenating rows of $M_i^{\top }$’s, which takes $𝒪(t\cdot (d/t))$ time.

We again partition the matrix into $t$-by-$t$ square submatrices. In this case, we obtain .

We execute $\text{Transpose}(M,d)$ and obtain . In principle, to obtain $h{(x)}^{\top }$, we just concatenate $d\cdot (t/d)$ rows of all $M_i^{\top }$. However, when $t\gg d$, this takes longer than $𝒪(d\log \log n)$ time. We instead use another recursive subroutine $\text{Concatenate}(M^{\prime },d)$. An example of the Concatenate algorithm is given in Figure 3.

The correctness of the Concatenate algorithm can again be observed by inducting on the logarithm of $w$. Line 2a and 3a can be done using $𝒪((J/w)\cdot \lceil w/\log n\rceil )$ operations on words, and both lines are repeated for $I$ times in each recursive call. Therefore, the total runtime is

$◀$

Computing $h(x)$ for all $x$ takes $𝒪(nd)$ time. Then computing $h{(x)}^{\top }$ takes
$𝒪(nd\log \log n)$ time. After that, sorting $𝒪(n)$-many $𝒪(d\log n)$-bit strings can be done in $𝒪(nd)$ time using radix sort. Finally, to find $p\in P$ with the longest common prefix for every $q\in Q$, we go through the sorted list and link each $q\in Q$ with adjacent $p\in P$, which takes $𝒪(n)$ total time. The above time bounds also hold for $h^{\prime }(x)$’s, resulting in $𝒪(nd\log \log n)$ time in total. $◀$

We use the same notation $D:=\min (d,3\log n)$ as in the previous section. For any finite subset $T\subset ℝ$, let $\mathrm{𝗆𝖾𝖽}T\in ℝ$ denote the median of $T$.

When working under the ${\mathrm{\ell }}_1$ norm, we use Cauchy random variables to project points. We first recall a standard bound on the median of projections, which will be useful for our analysis. (The following lemma essentially follows from Claim 2 and Lemma 2 in [13]; we reprove it in the appendix for completeness.)

In Figure 4, we describe how to construct a data structure to find $2$-approximate nearest neighbors. The construction borrows ideas from the second algorithm of [16], but using a tournament of depth $2$ instead of $𝒪(\log n)$.

Fix a query $q:=q_i$. Let $S$ denote the set of all $2$-approximate nearest neighbors to $q$, i.e., $S:=\{p\in P:{\parallel q-p\parallel }_1\le 2{\mathrm{𝗈𝗉𝗍}}_q\}.$ We prove the correctness of the algorithm by casing on the size of $S$.

With probability $\frac{1}{30t\log n}$, a random sample from $P$ is in $S$. Therefore, for $\overline{S}$ containing $w$ independent samples, at least one of them is in $S$ with probability $1-{(1-\frac{1}{30t\log n})}^w\ge 1-e^{-w/(30t\log n)}$. Moreover, when this happens, it must be that $\overline{p}\in S$. Setting $w\ge 90t\log t\log n$ gives the desired probability. $◀$

Let $p^{\ast }\in P$ denote a nearest neighbor of $q$, i.e. ${\parallel q-p^{\ast }\parallel }_1={\mathrm{𝗈𝗉𝗍}}_q$. To prove Lemma 13, we first make the following observation:

From $P^{\prime }\subseteq (P\setminus S)$ we know that ${\parallel q-p\parallel }_1>2{\parallel q-p^{\ast }\parallel }_1$ for any $p\in P^{\prime }$. Therefore, if ${\mathrm{𝗆𝖾𝖽}}_p\le {\mathrm{𝗆𝖾𝖽}}_{p^{\ast }}$ then either ${\mathrm{𝗆𝖾𝖽}}_p\ne (1\pm \frac{1}{4}){\parallel q-p\parallel }_1$ or ${\mathrm{𝗆𝖾𝖽}}_{p^{\ast }}\ne (1\pm \frac{1}{4}){\parallel q-p^{\ast }\parallel }_1$. Applying Lemma 11 with $c=\frac{1}{4}$ and $r\ge 800(2\log t+\log \log n)$ and a union bound, we get that

$◀$

In Line 3 of the data structure building procedure, the point $p^{\ast }$ is assigned to one of the subsets $P^{\ast }\in \{P_1,P_2,$ $\mathrm{\cdots },P_{n/\log n}\}$. If , then one can show that $p^{\ast }$ is likely the only $2$-approximate nearest neighbor in $P^{\ast }$. Conditioned on this, we can use Lemma 14 to show that $p^{\ast }$ is added into $\tilde{S}$ with high probability.

The set $P^{\ast }$ contains $\log n$ points. Since we randomly partition $P$ into $P_1,\mathrm{\cdots },P_{n/\log n}$, $P^{\ast }\setminus \{p^{\ast }\}$ is a uniformly random subset of $P$. When , $\text{Pr}\left[({\mathrm{P}}^{\ast }\setminus \{{\mathrm{p}}^{\ast }\})\cap \mathrm{S}=\mathrm{\varnothing }\right]\ge 1-\frac{1}{20\mathrm{t}}$. Conditioned on this event, we have

by Lemma 14, as long as $t\ge 40$. Therefore, with probability at least $1-\frac{1}{10t}$, $p^{\ast }$ has the smallest median of projected distance to $q$, and thus must be added to $\tilde{S}$. $◀$

Lemma 13 is a direct corollary of Lemma 15.

$p^{\ast }\in \tilde{S}$ implies that if we compute $\tilde{p}={\arg \min }_{p\in \tilde{S}}{\parallel q-p\parallel }_1$, we are guaranteed to find a nearest neighbor of $q$, which is clearly in $S$. $◀$

Combining Lemma 12 and 13 we get the following correctness guarantee:

Finally, we state the runtime guarantee as follows: