Near-Linear Time Algorithm for the Chamfer Distance
Authors: Ainesh Bakshi
Piotr Indyk
Rajesh Jayaram
Sandeep Silwal
Erik Waingarten
Venue: NeurIPS 2023 poster (2023)
Keywords: chamfer distance
earth mover distance
high dimensional data analysis
nearest neighbor search
high dimensional data
high-dimensional geometry
sublinear algorithms
point clouds
theory
TL;DR: We give a near linear time algorithm for computing the Chamfer distance, a common relaxation of the Earth Mover (Optimal Transport) distance, improving upon the naive quadratic runtime.

Abstract: For any two point sets $A,B \subset \mathbb{R}^d$ of size up to $n$, the Chamfer distance from $A$ to $B$ is defined as $\texttt{CH}(A,B)=\sum_{a \in A} \min_{b \in B} d_X(a,b)$, where $d_X$ is the underlying distance measure (e.g., the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward $O(d n^2)$-time brute force algorithm. Further, Chamfer distance is often used as a  proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{quadratic} dependence on $n$ in the running time  makes the naive approach intractable for large datasets.

We overcome this bottleneck and present the first $(1+\epsilon)$-approximate algorithm for estimating Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time $O(nd \log (n)/\epsilon^2)$ and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to report a $(1+\epsilon)$-approximate mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic  time algorithm is unlikely to exist.

A Near-Linear Time Algorithm for the Chamfer Distance
Ainesh Bakshi MIT ainesh@mit.eo eduu
Piotr Indyk MIT indyk@mit.edi
Rajesh Jayaram Google Research
Sandeep Silwal MIT silwal@mit.edi
rkjayaram@@gogle.com
Erik Waingarten
University of Pennsylvania
ewriingarsseas.uue edu
Abstract
For any two point sets B C Rd of size up to n, the Chamfer distance from A to B defined as CH(A, B) EnEA minge underlying distance measure (e.g., the Euclidean Manhattan distance). The Chamfer distance is a popular measure dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits straightforward O( dn ((dn)) -time brute force algorithm. Further, the Chamfer distance is often used proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the quadratic dependence on n in the rumning time makes the naive approach intractable for large datasets.
where dx the
We overcome this bottleneck and present the first (1 (1+e)-appe approxxmmme algorithm for estimating the Chamfer distance with near-lineat running time. Specifically, our algorithm runs in time O(nd nd log(n)/=²) and is implementable. Our experiments demonstrate that it both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high- dimensional point clouds. We also give evidence that if the goal to report a (1 apppoxxmia mapping from A to B (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.
Introduction
For any two point sets A, B C Idd of sizes up to n, the Chamfer distance! from A defined as
CH(A, = Σ min dx b)
beB
aEA
where dx underlying distance measure, such as the Euclidean or Manhattan distance. The Chamfer distance, and its weighted generalization called Relaxed Earth Mover Distance [16, 7], are popular measures dissimilarity between point clouds. They are widely used in machine learning (e.g., [16, 23]), computer vision (e.g., [8, 22, 12, 15]) and computer graphics [17]. Subroutines for computing Chamfer distances are available in popular libraries, such as Tensorflow [3], Pytorch [2] and PDAL [1]. In many of those applications (e.g., [16]) Chamfer distance is used faster proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance.
'This the definition adopted, e.g., [8]. Some other papers, e.g.. [12], replace each distance term dx (a, with its square, e.g.. instead of ||a b/1a they use l|a bl2.. In this paper we focus on the first detinition, as emphasizes the connection to Earth Mover Distance and its relaxed weighted version in [16, 7J.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Despite the popularity of Chamfer distance, the naive algorithm for computing it has quadratic O(n²) running time, which makes it difficult to use for large datasets. Faster approximate algorithms can be obtained by performing n exact or approximate nearest neighhor queries, one for each point in A. By utilizing the state of the art approximate nearest neighbor algorithms, this leads to (1 + e)- approximate estimators with running times of ((z(1/s)0rd) log n) in low dimensions [6] or roughly
of dn 1+ ((++))ー in high dimensions [3]. Alas, the first bound suffers from exponential dependence on the dimension, while the second bound significantly subquadratic only for relatively large approximation factors.
1.1 Our Results
In this paper we overcome this bottleneck and present the first + (1+=)-apprees -apppoximmaee algorithm for estimating Chamfer distance that has a near-linear running time, both in theory and in practice. Concretely, our contributions are as follows:
When the underlying metric dx is defined by the & or l norm, we give an algorithm that runs in time O Ond log (e?) and estimates the Chamfer distance up to 1 + with 99% probability (see Theorem 2.1). In general, our algorithm works for any metric dx supported by Locality- Hash functions (see Definition 2.2), with the algorithm running time depending on the parameters of those functions. Importantly, the algorithm is quite easy to implement, see Figures and 2.
For the more general problem of reporting a mapping A + B whose cost Eae dx g(a)) is within a factor of + & from CH( A, B), we show that, under popular ionplexity-hheoreiic -heoretic conjecture, an algorithm with a running time analogous to that of our estimation algorithm does not exist, even when dx dx(a, 6)
||a bll1. Specifically, under Hitting Set Conjecture [24], any such algorithm must run in time 22n226) for any constant 8 >> O, even when the dimension d = O(log" n) and (D) (In contrast, our estimation algorithm runs in near-linear time for such parameters). This demonstrates that, for the Chamfer distance, estimation is significantly easier than reporting.
We experimentally evaluate our algorithm on real and synthetic data sets Our experiments demonstrate the effectiveness of our algorithm for both low and high dimensional datasets and across different dataset scales. Overall, it is much faster (>5x) than brute force (even accelerated with KD-trees) and both faster and more sample efficient (5-10x) than simple uniform sampling. We demonstrate the scalability of our method by running it on billion-scale Big-ANN-Benchhe datasets [21], where it runs up to 50x faster than optimized brute force. In addition, our method is robust to different datasets: while uniform sampling performs reasonably well for some datasets in our experiments, performs poorly on datasets where the distances from points in A to their neighbors in B vary significantly. In such cases, our algorithm is able to adapt its importance sampling probabilities appropriately and obtain significant improvements over uniform sampling.
2 Algorithm and Analysis
In this section, we establish our main result for estimating Chamfer distance:
Theorem 2.1 (Estimating Chamfer Distance in Nearly Linear Time). Given input two datasets A, B C Rd such that [A],]]] & n, and an accuracy parameter 0 < e < 1, Chamfer-Estinne
runs in time nnd log (on))))?) and outputs an estimator d such that with probability least 99/ /000,
(1 (--)CH(AA, B) < & (1 (1+ +e)CHAA,
when the underlying metric is Euclidean (E2) or Manhattan (&,) distance.
For ease of exposition, we make the simplifying assumption that the underlying metric is Manhattan distance, i.e. dx (a, b) = |aa bll1- Our algorithm still succeeds whenever the underlying metric admits locality- sensitive hash function (the corresponding analogue of Definition 2.2).
Definition 2.2 (Hashing at every scale). There exists fixed constant c₁ 0 and parameterized family H(r) of functions from X to some universe U such that for all r > 0, and for every x, y E X
1. Close points collide frequently:
1ll1
Pr h-J((r))
[h(x) & h(y) <
2

---

Subroutine Chamfer-Estimaate/ Estimate
Input: Two subsets A, B C IR of size at most and parameter T E I.. Output: A number r E Rg0.
1. Execute the algorithm CrudeNN(A, B), and let the output be set of positive real numbers
(DaJaEA which always satisfy D, 2 minge ||a - bll1. Let D ===EasA Da-
2. Construct the probability distribution D, supported on the set A, which satisfies that for every
E A,
D. D
Pr x
al
For E (7], sample ay ~ and spend B[] time to compute
D
me
min Ø
bl11-
D
BEB
4. Output
=
T
Figure 1: The Chamfer-Estimate Algorithm.
2. Far points collide infrequently:
(-c
|
Pr [hx)) = h(v)l < exp h-330r))
(-c1
Uniform vs Importance Sampling. A natural algorithm for estimating CH( (A, B) proceeds by A uniformly random and explicitly compute minse ||a bll In general, we can compute the estimator 2 for CH(A B) by averaging over uniformly chosen samples, resulting in runtime (nds). It is easy
uniform sampling: sample
that the resulting estimator is un-biased, i.e. E CH( A, B). However, if a small constant fraction elements in A contribute significantly to CH(A, A, B), then with constant probability. Since each sample requires a linear scan to find the nearest neighbor, this would result in a quadratic runtime.
(2)) samples could be necessary obtain, say, a 1% relative
estimate
While such an approach has good empirical performance for well-behaved datasets, it does not work for data sets where the distribution of the distances from points in A to their nearest neighbors in B is skewed. Further, it is computationally prohibitive to verify the quality the approximation given by uniform sampling. Towards proving Theorem 2.1, is paramount to obtain algorithm that works regardless of the structure of the input dataset.
A more nuanced approach is to perform importance sampling where we sample A with probability proportional to contribution to CH(A, B). particular, if we had access to distribution, Da, over elements E A such that, minse 8 l|e b|], & Da & À minse a lla bll for some parameter À > 1, then sampling ((A) samples results in an estimator å that is within 1% relative error to the true answer with probability least 99%. Formally, we assume access to CrudeNN B). sub-routine which receives as input and and outputs estimates D. Rşu for each E A which is guaranteed to be upper bound for minge & ||a - bll Based on the values (Da)ae. we construct an importance sampling distribution D supported on A. As result, obtain the following lemma:
consider the estimator defined in Algorithm 1, where
Lemma 2.3 (Variance Bounds for Chamfer Estimate). Let n. d N and suppose A, B two subsets of IRd of size at most n. For any T E N, the output of Chamfer- Chamfer-Estimatel A, B, T) satisfies
E [n] CH (A, B), Var [n] < T
D CH(A, B)
-))
CH(A, B)²
3

---

for D from Line in Figure 1. The expectations and variance are over the randommess in the samples of Line 3 of Chamfer- Chamfor-Esimmaee( B,). : In particular,
1 D
(CH(A,))) -1)
Pr In - In-CH(A, B) CH(A, < 22. CH(AA B)
The proof follows from standard analysis of importance sampling and is deferred to Appendix A. Observe, if D & ACH(A, B), it suffices to sample T = (2/6²) points in A, leading to a running time of (ndA/e²).
Subroutine CrudeNN A, B)
Input: Two subsets A, B of a metric space (X, || [I1) of size at most n such that all non-zero distances between any point in A and any point in B is between 1 and poly(n/e). We assume access to a locality-sensitive hash family at every scale H(r) for any > 0 satisfying conditions of Definition 2.2. (We show in Appendix A that, for l and Ez, the desired hash families exist, and that distances between and (oly(n/e) is without loss of generality).
Output: A list of numbers [Da)oEA where D2 7 minse B I|a 61[1-
1. We instantiate L = O[log(n/s) (s) and for i E {0... [O..... L), we let =
2. For each E {0..... -} sample hash function h,: X + U from h, H((r)).
3. For each a E A, find the smallest i E {O..... ....... L for which there exists a point E B with (a) = h; (b), and set D. ||a l|a-blli bll1.
The above may be done by first hashing each point b E B and i E (o....,.1
........]] L}
according to (b). Then, for each A, we iterate through i E (0.....1) L) while hashing a according to h, (a) until the first b E B with ha = (b) found.
Figure 2: The CrudeNN Algorithm.
Obtaining importance sampling probabilities. It remains to show how to implement the CrudeNN (A, B) subroutine to obtain the distribution over elements in A which is a reason- able over-cstimator of the true probabilities. A natural first step is to consider performing an O(log aapppoxxiee nearest neighbor search (NNS): for every a' E A, find b' B satisfying ||a' - b'111/ minse I|a' bll Olog n). This leads to the desired guarantees fortunately, the state of the art algorithms for O(log n) apprrxxmiat NNS, even under the & norm, posses extraneous poly(log n) factors in the runtime, resulting in a significantly higher running time. These factors are even higher for the & norm. Therefore, instead of performing direct reduction to approximate NNS, open up the approximate NNS black-box and give simple algorithm which directly satisfies our desired guarantees on [Da]aeA-
(Da Jaa)a Un-
To begin with, we assume that the aspect ratio of all pair-wise distances is bounded by a fixed polynomial, (nly(n/e) (we defer the reduction from an arbitrary input to one with polynomially bounded aspect ratio to Lemma A.3). We proceed via computing Olog(n/=)) different (randomized) partitions of the dataset A U B. The i-th partition, for < i & Olog(nn/s)). can be written as A B UjP] and approximately satisfies the property that points in A U B that are distance most 2' will be in the same partition JPj with sufficiently large probability. To obtain these components, we use a family of locality-sensitive hash functions, whose formal properties are given in Definition 2.2. Intuitively, these hash functions guarantee that:
1. For each a' E A, its true nearest neighbor b' E falls into the same component as a' in the ig partition, where 20 O(Iaa' b' (1l 2, and
2. Every other extraneous + b' not the same component as a' for each < io.
It is easy to check that any hash function that satisfies the aforementioned guarantees yields valid set of distances boA as follows: for every a' E A, find the smallest in for which there exists a b' E B in the same component as a' in the io-th partition. Then set D. = ||a' - 6' 6''11- Intuitively, the b' we find for any fixed a' in this procedure will have distance that least the closest neighbor in
B and with good probability, it won't 't be too much larger. A caveat here is that we cannot show the
Recall assumed all distances are between 1 and (n))(1)) resulting in only O(log n) different partitions

---

above guarantee holds for 2 - ( -b'11). Instead, we obtain the slightly weaker guarantee that, in the expectation, the partition '' lands in is O[log approoxximiiiionn to the minimum distance, i.e. 2 O(log n I|a' b11)). Therefore, after running CrudeNN (A, B), setting À = log suffices time algorithm. We formalize this argument in the following lemma:
for our O(nd
Lemma 2.4 (Oversampling with bounded Aspect Ratio), Let dx,x) be metric space with locality-sensitivy hash family at every scale (see Definition 2.2). Consider two subsets A, B C X of size at most n and any & E (0, satisfying
1 1<
min (x & aE axb
dx(a, < poly(n/s).
Algorithm 2, CrudeNN(A, B), outputs a list of (random) positive numbers (DalaeA which satisfy the following guarantees:
* With probability 1, every E A satisfies D minseB (a,
For every a A, D|D.] < n)og minge dx (a,
Further, Algorithm 2, runs in time O(dn log(n/E)) time, assuming that each function used in the algorithm can be evaluated in (d) time.
Proof Sketch for Theorem 2.1. Given the lemmas above, it straight-forward to complete the proof of Theorem 2.1. First, we reduce to the setting where the aspect ratio is poly(n/E) (see Lemma A.3 for a formal reduction). We then invoke Lemma 2.4 and apply Markov's 's inequality to obtain a set of distances D. such that with probability at least 99/100, 100. for each E A, minge B ||a bll2 & D. and E.EA Do & (l)g((n) CH(A, B). We then invoke Lemma 2.3 and set the number of samples, T= (llgg())/e (e?). The running time of our algorithm then given by the time of CrudeNN A, B), which is (nd log(n/s)) and the time needed to evaluate the estimator in Lemma 2.3, requiring (onlog(()) /e²) time. Refer to Section for the full proof.
Other Related Works We note that importance sampling is a popular technique used for speeding up geometric algorithms. For example, [14] uses it to obtain a fast c-approximate algorithm for computing Farth Mover Distance (EMD) in two (or any constant) dimensions, for some constant <>> 2. However, the application and implementation of importance sampling in that paper is quite different from ours. In [14], the space containing all input points is subdivided into regions, and the total EMD value is represented as a sum of EMDs restricted to point-sets in each region (plus an additional representing the "global" EMD). The EMD cost in each region is then approximated quickly by embedding EMD into & using randomly shifted quadtree with logarithmic distortion; these estimations define the sampling probabilities.
In contrast, in our paper, the value of the Chamfer distance is exactly equal to the sum of distances from each point to its nearest neighbor, so there no decomposition involved. Instead, we approximate each distance nearest neighbor using a randomized hierarchical decomposition; for the case of the l norm, each level of the decomposition partitions the space into rectangular boxes, as in quadtrees. Crucially, however, ensure that the running time of our algorithm is within the stated bounds, we cannot use a standard randomly shifted quadtree where each level is shifted by the same random vector (as in [14)). This is because shifting all levels by the same amount only ensures that the expected distortion between a fixed pair of points is logarithmic; to ensure that the distance to the nearest neighbor is distorted by O(log n), would need to use O(log n) independent quadtrees and apply the union bound. Instead, we use independent random partitions at each level, and show (Lemma 2.4) that this suffices to bound the expected distortion of the distance the nearest neighbor, without incurring any additional factors. This makes it possible to obtain the running time as stated.
There are other works on quickly computing EMD and related distances. For example, the algorithm of [4] runs in time that is linear in the number of distances, i.e. it runs in ?(n²²) time and gets a 1 + approximation to EMD. This means that their approach requires a runtime quadratic in the size of the dataset n. In contrast, Chamfer distance admits trivial time O(n²) algorithm and our main contribution is to provide nearly linear (n log(n)/ (n)) algorithm to get (1 + +& a)aaprroxnnation to Chamfer distance.
5

---

3 Experiments
We perform an empirical evaluation of our Chamfer distance estimation algorithm.
Summary of Results Our experiments demonstrate the effectiveness our algorithm for both low and high dimensional datasets and across different dataset sizes. Overall, is much faster than brute force (even accelerated with KD-trees). Further, our algorithm is both faster and more sample-efficien than uniform sampling. It is also robust to different datasets: while uniform sampling performs well for most datasets in our experiments, it performs poorly on datasets where the distances from points in A their neighbors in B vary significantly. In such cases, our algorithm is able to adapt its importance sampling probabilities appropriately and obtain significant improvements over uniform sampling.
Dataset
[ |B|
d
Experiment
Metric
Reference
ShapeNet
~8 10 ~ 8 10
Small Scale
[10]
Text Embeddings
2 10 10
1.8
300
Small Scale
4
[16]
Gaussian Points
5 10 5- 10*
Outliers
&
DEEP1B
10 109
96
Large Scale
82
[9]
Microsoft-Turiee
109 109
100
Large Scale
[21]
Table 1: Summary of our datasets. For ShapeNet, the value of |A| and [B] is averaged across different point clouds in the dataset.
3.1 Experimental Setup
We use three different experimental setups, small scale, outlier, and large scale. They are designed to 'stress test' our algorithm, and relevant baselines, under vastly different parameter regimes. The datasets we use are summarized in Table 1. For all experiments, we introduce uniform sampling as a competitive baseline for estimating the Chamfer distance, as well as (accelerated) brute force computation. All results are averaged across 20+ trials and 1 standard deviation error bars are shown when relevant.
Small Scale These experiments are motivated from common use cases of Chamfer distance in the computer vision and NI.P domains. our small scale experiments, we use two different datasets: (a) the ShapeNet dataset, collection of point clouds of objects in three dimensions [10]. ShapeNet is common benchmark dataset firquently used in computer graphics, computer vision, robotics and Chamfer distance is widely used measure of similarity between different ShapeNet point clouds [10]. (b) We create point clouds words from text documents from [16]. Each point represents word embedding obtained from the word-to-wer vec model of [19] in IR 300 applied the Federalist Papers corpus. As mentioned earlier, a popular relaxation the common Earth Mover Distance is exactly the (weighted) version of the Chamfer distance [16, 7].
Since ShapenNet is in three dimensions, implement nearest neighbor queries using KD-trees to accelerate the brute force baseline as KD-trees can perform exact nearest neighbor search quickly in small dimensions. However, they have runtime exponential in dimension meaning they cannot be used for the text embedding dataset, for which we use a standard naive brute force computation. For both these datasets, implement our algorithms using Python 3.9.7 on an M1 MacbookPro with 32GB of RAM. We also use an efficient implementation of KD trees in Python and use Numpy and Numba whenever relevant. Since the point clouds in the dataset have approximately the same value, we compute the symmetric version CH(A, A B) + CH( B, A). For these experiments, we use the L distance function.
This experiment is meant to showcase the robustness of our algorithm. We consider two point clouds, and B, each sampled from Gaussian points IR 100 with identity covariance. Furthermore, we add an "outlier" point to A equal to 0.5n 1, where 1 is the all ones vector.
Outliers
This example models scenarios where the distances from points in A to their nearest neighbors in B vary significantly, and thus uniform sampling might not accurately account for all distances, missing small fraction of large ones.

---

Large Scale The purpose of these experiments is to demonstrate that our method scales to datasets with billions of points in hundreds of dimensions. We use two challenging approximate nearest neighbor search datasets: DEEPIB [9] and Microsoft Turing-ANNS [21]. For these datasets, the set the query data associated with the datasets. Due to the asymmetric sizes, we compute CH(A, (A, B). These datasets are normalized to have unit norm and we consider the & distance function.
These datasets are too large to handle using the prior configurations. Thus, we use proprietary in- memory parallel implementation of the SimHash algorithm, which is an E2 LSH family for normalized vectors according Definition 2.2 [11], on shared virtual compute cluster with 2x64 core AMD Epyc 7763 CPUs (Zen3) with 2.45Ghz 3. 3.5GHz clock frequency, 2TB DDR4 RAM and 256 MB L3 cache. We also utilize parallization on the same compute cluster for naive brute force search.
3.2 Results
ShapeNet
Polecalat
0.8
Importatra Sumpling
Unilsem Samplng
6.6
Ingvrtance Sumpling
Unibbrr Sangling
Roartte Srree
0.6
Importaaze Sampling
3.4-
Uniiomm Sampling
0.2
5.2
0.2
0.2
0.0
30
40
50
Sampiex
Samplees
Sumpine
(a) ShapeNet
(b) Federalist Papers
(c) Gaussian Points
DroP Tatbret
Pering Datsest
6.8
ingertannce Sumping
Unifeera Sunglng
Importance Sampling
Undiom Sampling
0,6
0.55
0.33
6.2
0.0
Sumples
Sampoor
(d) DEEP
(c) Turing
Figure Sample complexity vs relative error curves.
StopeNet Datoont
Federalist Papers Detanet
000 Churdor Oospatucass (ta3)
Compusatioss (ea)
1000
4000
800
2000
800
2000
400
1000
50
Uhther: Sumpling Iepartunce Suephay
Uhohee Sampling Importasii Sumptog
(a) ShapeNet
(b) Federalist Papers
Figure 4: Runtime experiments. We set the number of samples for uniform and importance sampling such that the relative errors of their respective approximations are similar.
Small Scale First we discuss configuring parameters. Recall that in our theoretical results, we use Ologn) n) different scales of the LSH family in CrudeNN. CrudeNN then computes (over) estimates of the nearest neighbor distance from points in A to B (in near lincar time) which is then used
7

---

DEEP Dutaset
Turing Dataset
32:2006
G4:1M
Undorra Samplind
0.10
Ibesotic
Teeittiic
dei bok
Selabvv Zrnee
0.08
16:2566
Unilorm Sangling
GENDONS
0.07
0.06
6.06
0.00
6.04
0.03
20 30
80
50
70
80
90
100
20
30
60
00 Samplin
70
50
90
100
Stamples
(a) DEEP
(b) Turing
Figure 5: The figures show sample complexity vs relative error curves as we vary the number of LSH data structures and window sizes. Each curve maps x W where & is the number of LSH data structures we use to repeatedly hash points in B and W is the window size, the number of points retrieved from B that hash closest to any given a at the smallest possible distance scales.
for importance sampling by Chamfer- EEttmmate. Concretely for the & case, this the LSH family corresponds to imposing Olog n) grids with progressively smaller side lengths. In our experiments, we treat the number of levels of grids to use as tuneable parameter in our implementation and find that a very small number suffices for high quality results in the importance sampling phase.
Figure 6 (b) shows that only using 3 grid levels is sufficient for the crude estimates Da to be within a factor of away from the true nearest neighbor values for the ShapeNet dataset, averaged across different point clouds in the dataset. Thus for the rest of the Small Scale experiments, we fix the number grid levels to be 3.
Figure 3 (a) shows the sample complexity vs accuracy trade offs of our algorithm, which uses importance sampling, compared to uniform sampling. Accuracy is measured by the relative error to the true value. We see that our algorithm possesses a better trade off as we obtain the same relative error using only 10 samples as uniform sampling does using 50+ samples, resulting in at least a 5x improvement in sample complexity. For the text embedding dataset, the performance gap between our importance sampling algorithm and uniform sampling grows even wider, as demonstrated by Figure (b), leading to 10x improvement in sample complexity.
In terms of runtimes, we expect the brute force search to be much slower than either importance sampling and uniform sampling. Furthermore, our algorithm has the overhead of first estimating the values D, for a E A using an LSH family, which uniform sampling does not. However, this is compensated by the fact that our algorithm requires much fewer samples to get accurate estimates.
Indeed, Figure 4 (a) shows the average time of 100 Chamfer distance computations between randomly chosen pairs of point clouds in the ShapeNet dataset. We set the number of samples for uniform sampling and importance sampling (our algorithm) such that they both output estimates with (close to) 2% relative error. Note that our runtime includes the time to build our LSH data structures. This means we used 100 samples for importance sampling and 500 for uniform. The brute force KD Tree algorithm (which reports exact answers) approximately 5x slower than our algorithm. At the same time, our algorithm is 50% faster than uniform sampling. For the Federalist Papers dataset (Figure 4 (b)), our algorithm only required 20 samples to get a 2% relative error approximation, whereas uniform sampling required at least 450 samples. As a result, our algorithm achieved 2x speedup compared to uniform sampling.
Outliers We performed similar experiments as above. Figure 3 (c) shows the sample complexity vs accuracy trade off curves of our algorithm and uniform sampling. Uniform sampling has a very large error compared to our algorithm, as expected. While the relative error of our algorithm decreases smoothly as the sample size grows, uniform sampling has the same high relative error. In fact, the relative error will stay high until the outlier is sampled, which typically requires 2()) samples.
Large Scale We consider two modifications to our algorithm to optimize the performance of CrudeNN on the two challenging datasets that we are using; namely, note that both datasets are standard for benchmarking billion-scale nearest neighbor search. First, in the CrudeNN algorithm, when computing D, for A, search through the hash buckets by (a), h2(a),.. containing
8

---

a in increasing order of i (i.e., smallest scale first), and retrieve the first W (window size) distinct points in B from these buckets. Then, the whole process is repeated times, with independent LSH data structures, and Da is set to be the distance from to the closest among all Wk retrieved points.
Note that previously, for our smaller datasets, we set Da to be the distance to the first point in B colliding with a, and repeated the LSH data structure once, corresponding W = k = 1. In our figures, we refer to these parameter choices as k x W and test our algorithm across several choices.
For the DEEP and Turing datasets, Figures 3 (d) and 3 (e) show the sample complexity vs relative error trade-offs for the best parameter choice (both 64 x 10%) compared to uniform sampling. Qualitatively, we observe the same behavior as before: importance sampling requires fewer samples to obtain the same accuracy as uniform sampling. Regarding the other parameter choices, we see that, as expected, if we decrease k (the number of LSH data structures), or if we decrease W (the window size), the quality of the approximations Faa decreases and importance sampling has worse sample complexity trade-offs. Nevertheless, for all parameter choices, we see that we obtain superior sample complexity trade-offs compared to uniform sampling, as shown in Figure 5. A difference between these parameter choices are the runtimes required to construct the approximations {Du Jas For example for the DEEP dataset, the naive brute force approach (which is also optimized using parallelization) took approximately 1.3- : 10 seconds, whereas the most expensive parameter choice of 64 10 took approximately half the time at 6.4 10 and the cheapest parameter choice of 8 x 10t took 225 seconds, leading to 2x-50x factor speedup. The runtime differences between brute force and our algorithm were qualitative similar for the Turing dataset.
Similar to the small scale dataset, our method also outperforms uniform sampling in terms of runtime if we require they both output high quality approximations. If we measure the runtime to get a 1% relative error, the 16 x 2- 10th version of our algorithm for the DEEP dataset requires approximately 980 samples with total runtime approximately 1785 seconds, whereas uniform sampling requires > 1750 samples and runtime > 2200 seconds, which is > 23% slower. The gap in runtime increases if we desire approximations with even smaller relative error, as the overhead of obtaining the approximations (Dahee becomes increasingly overwhelmed by the time needed to compute the exact answer for our samples.
Additional Experimental Results We perform additional experiments show the utility of our approximation algorithm for the Chamfer distance for downstream tasks. For the ShapeNet dataset, we show we can efficiently recover the true exact nearest neighbor of fixed point cloud A in Chamfer distance among large collect of different point clouds. In other words, it is beneficial for finding the 'nearest neighboring point cloud', Recall the ShapeNet dataset, contains approximately 5 10a different point clouds. We consider the following simple (and standard) two step pipeline: (1) use our algorithm to compute an approximation of the Chamfer distance from to every other point cloud B in our dataset. More specifically, compute an approximation to CH( A, B) + CH( B, A) for all B using 50 samples and the same parameter configurations as the small scale experiments. Then filter the dataset of points clouds and prune down to the top k closest point cloud candidates according to our approximate distances. (2) Find the closest point cloud the top k: candidates via exact computation.
We measure the accuracy of this via the standard recall @k measure, which computes the fraction of times the exact nearest neighbor B of A, averaged over multiple A's, is within the top & choices. Figure 6 (a) shows that the true exact nearest neighbor of A, that is the point cloud B which minimizes CH(A, B) B CH B, A) among our collection of multiple point clouds, within the top 30 candidates > 98%, time (averaged over multiple different choices of A). This represents more than 1000x reduction in the number of point clouds we do exact computation over compared to the naive brute force method, demonstrating the utility of our algorithm for downstream tasks.
4 Lower Bound for Reporting the Alignment
We presented an algorithm that, in time
produces (1 + >)apprxximnti to CH(A, B). It is natural to ask whether it is also possible to report a mapping g : A + B whose cost Eees ||u - g(a)]l within a factor of 1 + e from CH(A, B). (Our algorithm uses on random sampling and thusdoes not give such mapping). This section shows that, under a popular complexity- theoretic conjecture called the Hitting Set Conjecture [24], such an algorithm does not exists. For simplicity, we focus on the case when the underlying metric dx is induced by the Manhattan distance,

---

StapsNot Dersont
1.0
Shapenet Datsowt
Ratlo
0.8
0.6
10
50
Levels
(a) ShapeNet NNS pipeline experiments
(b) Quality of approximations D. the number of levels LSH data structure
Figure 6: Additional figures for the ShapeNet dataset.
i.e. dx(a,,) b) la bll1. The argument is similar for the Euclidean distance, Euclidean distance squared, etc. To state our result formally, we first define the Hitting Set (HS) problem.
Definition 4.1 (Hitting Set (HS) problem). The input to the problem consists of two sets of vectors A, B C (0, 1)d, and the goal is determine whether there exists every b E B. If such an a E exists, we say that a hits B.
such that b + 0 for
It is easy Conjecture [24] postulates that this running time is close to the optimal. Specifically:
that the Hitting Set problem
be solved in time O(n²d). The Hitting Set
Conjecture 4.2. Suppose (log" n)) Then for every constant no randomized algorithm solve the Hitting Set problem in O(n²~)) time.
Our result can be now phrased as follows.
Theorem 4.3 (Hardness for reporting mapping). [et D,E) be the running time of an algorithm ALG that, given sets of A" B" c (0, sizes most N, reports a mapping 9 A" B" with cost (1 + +H)CH(A (A", B. D = Ollgg² 2 N) and D
@(1) Assuming the Hitting Set Conjecture,
we have that TNN, D,E) is at least ((N2-A) f any constant 8 > 0.
Conclusion
We present efficient approximation algorithm for estimating the Chamfer distance up to 1 + factor in time O(nd lee( The result is complemented with conditional lower bound which shows that reporting Chamfer distance mapping of similar quality requires nearly quadratic time. Our algorithm is easy to implement in practice and compares favorably to brute force computation and uniform sampling. We envision our main tools of obtaining fast estimates of coarse nearest neighbor distances combined with importance sampling can have additional applications in the analysis of high-dimensional, large scale data.
Acknowledgement
AB was supported by Ankur Moitra's ONR grant and the NSF TRIPODS program (award DMS- 2022448). PI was supported by the NSF TRIPODS program (award DMS-2022448), Simons Investigator Award and GIST-MIT Research Collaboration grant.
References
[1] Pdal: Chamfer.
html, 2023. Accessed: 2023-05-
12.
[2] Pytorch3d: Loss functions. http:///aoccBeaaaaaaaaacc////eee html, 2023. Accessed: 2023-05-12.
10

---

[3] Tensorflow graphics: Chamfer distance. https://www.teneort/ org/ wwwg/ggaphccs//p/ docs/pp hatas/yytoo//tee /tgg/ wetttggg/g/////eeeeee http://eeeacaaacnceeo/oeaae distance evaluate, 2023, Accessed: 2023-05-12.
[4] Jason M. Altschuler, Jonathan Weed, and Philippe Rigollet. Near-linear time approximation algorithms for optimal transport via sinkhom iteration. Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 1974, 2017.
[5] Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the forty-seventh annual ACM symposium Theory of computing. pages 193-801, 2015.
[6] Sunil Arya, David M Mount, Nathan S Netanyahu. Ruth Silverman, and Angela Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891-92) 1998.
[7] Kubilay Atasu and Thomas Mittelholzer. Linear-complexin data-parallel earth mover's distance approximations. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 364-3 373. PMLR, 09-15 Jun 2019.
[8] Vassilis Athitsos and Stan Sclaroff. Estimating 3d hand pose from a cluttered image. In 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings., volume 2, pages II 432. IEEE, 2003.
[9] Artem Babenko and Victor Lempitsky. Efficient indexing of billion-scale datasets of deep de- scriptors. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 2055-2063, 2016.
[10] Angel X Chang, Thomas Funkhouser, Leonidas Guibas, Pat Hanrahan, Qixing Huang. Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, et al. Shapenet: An information-rich 3d model repository. arXiv preprint
2015.
[11] Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 380-388, 2002.
[12] Haoqiang Fan, Hao Su, and Leonidas J Guibas. A point set generation network for 3d object reconstruction from a single image. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 605-615 2017.
[13] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream computation. Journal of the ACM (JACM), 53(3):307-322 2006.
[14] Piotr Indyk. A near linear time constant factor approximation for euclidean bichromatic matching (cost). In Nikhil Bansal, Kirk Pruhs, and Clifford Stein, editors, Proceedings of the Eighteenth Anmual ACCM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA. January 7-9, 2007, pages 39 42. SIAM, 2007.
[15] Li Jiang, Shaoshuai Shi, Xiaojuan Qi, and Jiaya Jia, Gal: Geometric adversarial loss for single-view 3d-object reconstruction. In Proceedings of the European conference computer vision (ECCV), pages 802-816, 2018.
[16] Matt Kusner, Yu Sun, Nicholas Kolkin, and Kilian Weinberger. From word embeddings to document distances. In International conference on machine learning, pages 957-966. PMLR, 2015.
[17] Chun-Liang Li, Tomas Simon, Jason Saragih, Barnabás Póezos, and Yaser Sheikh. Lbs autoencoder: Self-supervised fitting of articulated meshes to point clouds. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 11967-11976.
2019.
11

---

[18] Jiri Matousek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013.
[19] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg Corrado, and Jeff Dean. Distributed repre- sentations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
[20] Dhruv Rohatgi. Conditional hardness of earth mover distance. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROXRANDOM 2019). Schloss Dagstuhl-LecinnizzZZenuuu fuer Informatik, 2019.
[21] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini, Ravishankar Krishnaswamny, Gopal Srinivasa, et al. Results of the neurips 21 challenge on billion-scal approximate nearest neighbor search. In NeurIPS 2021 Comperitions and Demonstrations Track, pages 177-189. PMLR, 2022.
[22] Erik B Sudderth, Michael I Mandel, William T Freeman, and Alan S Willsky. Visual hand tracking using nonparametric belief propagation. In 2004 Conference Computer Vision and Puttern Recognition Workshop, pages 189-189. IEEE, 2004.
[23] Ziyu Wan, Dongdong Chen, Yan Li, Xingguang Yan, Junge Zhang, Yizhou Yu, and Jing Liao. Transductive zero-shot learning with visual structure constraint. Advances in neural information processing systems, 32, 2019.
[24] Virginia Vassilevska Williams. On some fine-grained questions algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018 pages 3447-3487. World Scientific, 2018
12


Reviews:
[{"review_id": "vCOWjo8hmB", "reviewer": "Reviewer_WXaW", "summary": "This paper considers the problem of computing the Chamfer distance between two point sets. Informally, the Chamfer distance is simply the total cost of mapping points of A to their closest point in B. Practically, Chamfer distance seems to be used as a proxy for the earth mover’s distance.\n\nOne can always compute Chamfer distance is quadratic time – for every point in A, find the cheapest edge by simply scanning all the edges. Of course, in low dimensional spaces, one can speed this up by the use of exact nearest neighbor data structures. To approximate the Chamfer distance, one can use the approximate nearest neighbor data structure leading to a near-linear time algorithm in fixed dimension and a super-linear time algorithm in higher dimensions. \n\nThe main contribution of this paper is to show that Chamfer distance can be estimated in near-linear time even in higher dimensions. As opposed to this, the authors show that computing the maps themselves is hard to approximate in near-linear time (the running time has to be only slightly sub-quadratic under the hitting set conjecture). \n\nThe main technique used is the idea of importance sampling. Their algorithm first obtains a crude approximation of the contribution of each point and then uses these values to obtain a small sized weighted sample which can then be used to estimate the Chamfer distance in $O(nd\\log n/\\varepsilon^2)$ time. The idea of using Importance sampling to estimate distances efficiently is not new. It has been used, for instance, to estimate EMD in low dimensions by Indyk in his paper titled “A near linear time constant factor approximation for Euclidean bichromatic matching (cost).”\nNonetheless, the use of importance sampling for approximate Chamfer distance is novel and the contribution towards computing high dimensional Chamfer distance is significant. For this reason, I recommend accepting this paper.\n", "questions": "Please answer the questions in weaknesses.", "limitations": "NA", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The algorithm is simple and estimates Chamfer distance for high dimensional data with solid theoretical guarantees and strong practical results.", "weaknesses": "I’m not convinced that Chamfer distance has strong theoretical properties. For instance, it doesn’t appear to be symmetric, i.e., Chamfer(A,B) is not equal to Chamfer(B,A). Is there a relationship between Chamfer distance and EMD even under some stochastic assumptions for B and A? \n\nSimilar techniques seem to have been used for EMD approximations before (Indyk, SODA 2007). Could you add a comparison of your algorithm to the techniques used in other papers?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and thorough comments. We would first like to remark that, while it is true that Chamfer is usually used as a proxy for EMD, there are scenarios where Chamfer distance is actually the correct choice instead of EMD. This includes settings where duplication of points should not affect the similarity significantly: an example is when the point clouds are sets of pre-trained image embeddings of a location (building, city, ect.) and one wants to determine if the location described by the point cloud  is the same.\n\n**Relationship between Chamfer and EMD:**\nWith regards to theoretical properties of the Chamfer distance, note that for symmetry, a common practice is to compute Chamfer(A,B) + Chamfer(B,A), which is symmetric. Our method also easily extends to the symmetric case by two calls to our algorithm. With regards to comparing Chamfer to EMD, it’s always true that EMD(A,B) >= Chamfer(A,B). This fact is particularly useful for finding points in a dataset with EMD smaller than some threshold to a query (nearest neighbor search): first quickly compute the Chamfer distance from each point to the query, and if the Chamfer distance to a point is too large then one does not need to compute the EMD to that point. This is called prefetch and prune (see e.g. “From Word Embeddings To Document Distances” by Kusner, Sun, Kolkin, and Weinberger, ICML '2015). \n\nNote that under stochastic assumptions, the Chamfer distance may be quite close to EMD depending  on the assumptions made. For example, if the point sets A and B are uniform on the unit sphere in at least $\\Omega(\\log n)$ dimensions, then with high probability, both values are within $1+o(1)$ multiplicative factors of each other since all the points are pairwise distance $\\sqrt(2) - o(1)$ apart, with high probability. Further exploring the relationship between Chamfer and EMD for stochastic inputs is an interesting future direction. \n\n**Comparison between our algorithm and other papers:**\nWith regards to the comparison of our algorithm to techniques used in prior papers: we note that importance sampling is indeed a popular technique used for speeding up algorithms. In particular, as the reviewer points out, the paper of Indyk, SODA, 2007, uses it to obtain a fast c-approximate algorithm for computing EMD in two (or any constant) dimensions, for some constant c>2. However, the application and implementation of importance sampling in that paper is quite different from ours.\n \nIn (Indyk’07), the space containing all input points is subdivided into regions, and the total EMD value is represented as a sum of EMDs restricted to point-sets in each region (plus an additional representing the “global” EMD). The EMD cost in each region is then approximated quickly by embedding EMD into L1 using a randomly shifted quadtree with logarithmic distortion; these estimations define the sampling probabilities.\n \nIn contrast, in our paper, the value of the Chamfer distance is exactly equal to the sum of distances from each point to its nearest neighbor, so there is no decomposition involved. Instead, we approximate each distance to nearest neighbor using a randomized hierarchical decomposition; for the case of the L1 norm, each level of the decomposition partitions the space into rectangular boxes, as in quadtrees.  Crucially, however, to ensure that the running time of our algorithm is within the stated bounds, we cannot use a standard randomly shifted quadtree where each level is shifted by the same random vector (as in Indyk’07). This is because shifting all levels by the same amount only ensures that the expected distortion between a fixed pair of points is logarithmic; to ensure that the distance to the nearest neighbor is distorted by O(log n), we would need to use O(log n) independent quadtrees and apply the union bound. Instead, we use independent random partitions at each level, and show (Lemma 2.3) that this suffices to bound the expected distortion of the distance to the nearest neighbor, without incurring any additional factors. This makes it possible to obtain the running time as stated.\n\nWe will add the comparison to the final version of the paper. \n\n\n"}, {"review_id": "GLh7X2nRlt", "reviewer": "Reviewer_cYq9", "summary": "This paper studies the approximation algorithm for computing the Chamfer distance between two datasets. The Chamfer distance is a very useful distance metric in machine learning, and the naive approach for computing it takes $O(n^2d)$-time for $n$ points in $d$ dimensions. This paper proposes an approximation algorithm that runs in $O(nd\\log(n)/\\epsilon^2)$-time with $(1+\\epsilon)$-relative error. This algorithm is the first to achieve linear dependence in $nd$ and polynomial dependence in $1/\\epsilon$. Moreover, it is implementable on real datasets and empirically improves the previous methods. In addition, it shows a fine-grained lower bound that no randomized algorithm can find a $(1+ \\epsilon)$-approximate mapping for the Chamfer distance in $n^{2-o(1)}$-time for $d\\sim \\log^2 n$ and $\\epsilon\\sim 1/d$, assuming the Hitting Set Conjecture. Technically, their algorithm is based on the importance sampling and Locality-Sensitive Hashing.  \n", "questions": "1. In Section 2, it discusses the uniform sampling approach. And the runtime is $O(nds)$ if we sample $s$ points. What if we use any computational geometry data structure to pre-process the set $B$ such that for each sample, the computational cost can be reduced to $o(nd)$? \n\n2. Line 27: $O(n^2)$ should be $O(n^2d)$ to avoid confusion. \n\n3. Line 85: ``distribution, $D_a$”. However, $D_a$ itself is not a probability distribution but an estimator. \n\n4. Proof of Lemma A.2: the event $E_1(\\gamma)$ is missing. \n", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem studied in this paper is significant in theory and practice. The algorithm in this paper runs in nearly-linear time in $n$ and works for large dimensions and high accuracy. For comparison, previous approximation algorithms either incur an exponential dependence in $d$ or only work for the low-accuracy regime. This paper provides an essential theoretical improvement. Another advantage is that the algorithm is quite clean that can be implemented efficiently, which increases the practical value of this paper.  This paper thoroughly explains the experiments.  And most theorems and lemmas in this paper are mathematically sound to me.\n", "weaknesses": "Some notations could be more precise in the main text. For example, the subroutine CrudeNN uses $H(r)$ without defining it. And more intuition should be given for this subroutine. Also, the algorithm in this paper works for any distance metric with LSH functions. Some examples other than $\\ell_1$ or $\\ell_2$ can be provided. For the hardness result, the Hitting Set Conjecture is not very standard in the field of fine-grained complexity. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**On notation.** We apologize for the lack of precision in notation in the main text. We will fix these issues.\n\n**On metrics that admit a locality-sensitive hash.** We focused on L2/L1 as, to our knowledge, these are the most typical cases. However, our methods work for any metrics which support a locality sensitive hash function (or such metrics squared). This encompasses a very wide class of metrics including $\\ell_1, \\ell_2$ (and generally all $\\ell_p$ for $1\\le p \\le 2$), the Jaccard distance, and even includes functions which are not strictly metrics such as $\\ell_p$ for $0 < p < 1$ and $\\ell_2^2$.  We will make it clear in the updated version of the paper. \n\n**The Hitting Set Conjecture.** Although the conjecture is not as popular as, say, Strong Exponential Time Hypothesis, it has nevertheless been used in many papers, as listed below. Thus, we believe that hardness results assuming HSC provide useful evidence of problem complexity.\n\n[1] Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs, Abboud et al,  SODA 2016.\n\n[2] Approximation algorithms for min-distance problems, Dalirrooyfard et al, ICALP 2019.\n\n[3] Tight approximation algorithms for bichromatic graph diameter and related problems, Dalirrooyfard et al ICALP 2019.\n\n[4] Approximation algorithms for min-distance problems in DAGs, Dalirrooyfard and Kaufmann, ICALP 2021.\n\n[5] Conditional hardness of earth mover distance, Rohatgi, APPROX 2019.\n\n[6] Completeness for first-order properties on sparse structures with algorithmic applications, Gao et al, SODA 2017.\n\n[7] Dynamic Data-Race Detection Through the Fine-Grained Lens, Kulkarni et al, CONCUR 2021.\n\n[8] Fast approximation of eccentricities and distances in hyperbolic graphs, Chepoi et al, Journal of Graph Algorithms and Applications, 2019.\n\n[9] Tight hardness results for distance and centrality problems in constant degree graphs, Dahlgaard and Evald, arxiv preprint, 2016.\n\n[10] On the complexity of 1 center in various metrics, Abboud et al, arXiv preprint, 2021.\n\n[11] Balancing graph Voronoi diagrams with one more vertex, Ducoffe, 2022\n\n\n**What if we use any computational geometry data structure to pre-process the set such that the computational cost can be reduced to o(nds)?**\n\nWe assume that the reviewer suggests using a nearest neighbor data structure that computes an (approximate) nearest neighbor of each uniformly sampled point. Indeed, we discuss a very similar idea on page 2, lines 30-34, though the data structure is applied to *all* n points. Unfortunately, unless $s=\\Omega(n)$, we do not believe uniform sampling will yield provable guarantees with good probability. This is because the distance from one of the points (say p) in A to its nearest neighbor could be very large, and if the sample misses p, the estimate will be inaccurate. \n\n**Line 27: $O(n^2)$ should be $O(n^2d)$ to avoid confusion. Line 85: ``distribution $D_a$”. However $D_a$ itself is not a probability distribution but an estimator.**\n\nWe thank the reviewer for pointing out these typos, we will fix them. \n\n**Proof of Lemma A.2: the event $E_1(\\gamma)$ is missing.**\n\nWe apologize for the typo, the definition of the event was omitted while preparing the supplementary. The event $E_1(\\gamma)$ occurs when there exists a point $b' \\in B$ at distance at least $\\gamma$ from $a$ and there exists an index $i \\leq i_0$ for which $h_i(a) = h_i(b')$. \n"}, {"review_id": "gVb7lAaiCf", "reviewer": "Reviewer_3E3v", "summary": "The paper gives an algorithm to approximate Chamfer distance between two sets within $(1 \\pm \\epsilon) $ of the original value. The brute force algorithm to calculate the distance exactly between two sets of size $n$ and with points in $d$-dimension is $O(n^2d)$ which is prohibitive for large values of $n$. The authors use a crude version of the locality sensitive hashing technique, to design an importance sampling algorithm that samples $O(\\log{n})$ points from the first set and approximates Chamfer distance only using these weighted and sampled points, hence giving an approximation algorithm with time complexity $O(nd\\log{n})$. They validate the efficiency of their algorithm for a variety of datasets. They also show negative result where they show that it is not possible to give the actual mapping between the two sets which gives the $(1 + \\epsilon) $approximate Chamfer distance with a faster algorithm under the assumption that the hitting set conjecture is true.", "questions": "Please refer to weaknesses section", "limitations": "Please refer to weaknesses section", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The paper is written very nicely and is coherent and easy to follow\n2) Experiments are performed under a variety of settings and code is provided. Authors should make it public if the paper gets accepted.\n3) Proofs appear sound to the best of my understanding.\n\nOverall, the paper does a good job of efficiently approximation a quantity which finds application in a variety of problems in machine learning and will be of interest to the community.", "weaknesses": "1) I think it would be good if the authors can at least give the definition of Locality Sensitivity Hashing in the main body of the paper. It would increase the readability.\n2) The only other arguable weakness I find is that the ideas used in the paper and the proof techniques are not novel and as such may not be so interesting from theoretical perspective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and thorough comments. See our answers to specific comments below.\n\n**Experiments are performed under a variety of settings and code is provided.**\nThank you for the comment. We intend to make the code public if the paper is accepted. \n\n**Definition of Locality Sensitive Hashing.**\nThank you for the suggestion. We will make this change to include a definition in the main body in the updated version of the paper.\n\n\n**On the novelty of the ideas and proof techniques.**\nOur main upper bound algorithm uses both importance sampling and a hierarchical space decomposition. While these tools are indeed quite common, we would like to point out that we apply them in a subtle but crucially different manner than prior works. We hope the following elaboration will be insightful in pointing out the differences. \n\nThe value of the Chamfer distance is exactly equal to the sum of distances from each point to its nearest neighbor. We approximate each distance to nearest neighbor using a randomized hierarchical decomposition; for the case of the L1 norm, each level of the decomposition partitions the space into rectangular boxes, as in quadtrees.  Crucially, however, to ensure that the running time of our algorithm is within the stated bounds, we cannot use the standard randomly shifted quadtree where each level is shifted by the same random vector, a common method in geometric approximation algorithms. This is because shifting all levels by the same amount only ensures that the expected distortion between a fixed pair of points is logarithmic; to ensure that the distance to the nearest neighbor is distorted by O(log n), we would need to use O(log n) independent quadtrees and apply the union bound, leading to extraneous overhead. Instead, we use independent random partitions at each level, and show (Lemma 2.3) that this suffices to bound the expected distortion of the distance to the nearest neighbor, without incurring any additional factors. This makes it possible to obtain the running time as stated.\n\nWe will add the comparison to the final version of the paper.\n\n"}, {"review_id": "f9mHOo9hSq", "reviewer": "Reviewer_qK6W", "summary": "This paper provides the first near-linear time approximation scheme to compute the Chamfer distance $\\texttt{CH}(A,B) = \\sum_{a \\in A} \\min_{b \\in B} d_X(a,b)$ for any two point sets $A,B \\in \\mathbb{R}^d$ and $d_X$ is the distance measure under consideration. In particular, for $|A|, |B| \\leq n$, and for any $\\epsilon > 0$, they provide an algorithm which outputs a $(1 + \\epsilon)$-approximate solution with probability greater than 99% in time $O(nd \\log(n)/\\epsilon^2)$. They also provide experimental evaluation of their algorithm and also a matching lower bound for the harder task of not just computing the value of the Chamfer distance but also providing a valid mapping from $A \\mapsto B$ which achieves that Chamfer distance. ", "questions": "Not a major question, but more of a suggestion. As a person who has not worked with Chamfer distances earlier, I don't know if they are useful other than as a proxy for Earth-mover distance (at least that's what I got from your introduction). A quick google search on approximating Earth-mover distances led me to this following paper: Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration, by Altschuler et.al, which appeared in NeurIPS 2017. The paper seems to be pretty well-known by now, with over 500 citations. Given that your paper is about approximating Chamfer distances, which seem to only be a proxy for Earth-mover distance, I think it is very natural that you at least refer this paper, or even better give a more detailed explanation of why your paper is relevant even though there is an approximation scheme for Earth-mover distances already.", "limitations": "Mainly theoretical paper.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper is the first to provide a near-linear time approximation scheme for computing Chamfer distances.\n\nQuality and Clarity: Paper is overall pretty well-written.\n\nSignificance: I have personally not used Chamfer distances in any of my prior work before so cannot directly attest the importance of Chamfer distances but the authors have done a reasonably good job of motivating the problem in the introduction of the paper. It looks like Chamfer distances have already been implemented in several popular ML libraries like TensorFlow and PyTorch. They have also been used in prior papers which have appeared in NeurIPS and other related conferences.", "weaknesses": "Not any that I can think of right now.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and thorough comments. See our answers to specific comments below.\n\n**Applications of Chamfer Distance.**  In addition to being a proxy for earth-mover distance, Chamfer distance is widely and independently used in point-cloud reconstruction and completion tasks, often as a component of the loss function in a deep network.Chamfer distance is also widely used in many use cases beyond these tasks, with a very common application being comparing the similarity between two point clouds. This is evidenced by the fact that the Chamfer distance is implemented in many popular libraries such as PDAL [1], CloudCompare [2], PointCloud Utils [3], for the purposes of comparing point clouds.\n\n**Comparison to Altschuler et. al.** We thank the reviewer for pointing us to Altschuler et. al. The algorithm introduced by Altschuler et. al. runs in time that is linear in the number of edges in the graph, i.e. it runs in $O(n^2/\\epsilon^3)$ time and gets a 1+eps approximation to EMD. This means that their approach requires a runtime quadratic in the size of the dataset n. In contrast, Chamfer distance admits a trivial $O(n^2)$ time algorithm and our main contribution is to provide a nearly *linear* $O(n \\log(n)/\\epsilon^2)$ algorithm to get a $(1+\\epsilon)$-approximation to Chamfer distance. We will add the reference and comparison to our paper. \n\n**Empirical evaluations.** Lastly, with regards to the comment about being mainly a theoretical paper, we would like to emphasize the detailed experimental section in our paper, where we evaluated our algorithm and compared it to the brute force and uniform sampling baselines. Moreover, we evaluated on a variety of dataset types and scales, including the ShapeNet dataset of 3D point clouds, word embedding datasets, and two different billion-scale embedding datasets from Big-ANN-Benchmarks, which is a central benchmark for large-scale nearest neighbor search. Thus, our experimental section empirically demonstrates that our algorithm is applicable and performs well for a wide range of data types and scales. \n\n\n\n[1] PDAL, Documentation » Applications » chamfer\n\n[2] CloudCompare, User’s Manual for version 2.1\n\n[3] Point Cloud Utils, Functionality » Point Cloud Metrics​\n"}, {"review_id": "jPosIJ7D3q", "reviewer": "Reviewer_5NRb", "summary": "The paper proposes a fast estimation of Chamfer distance which is a famous distance between two sets. The key idea is to use random sampling on the first set and then find the closest point on the other set. To enhance further the approximation performance and quality of samples, importance sampling is utilized. The paper proposes to use a proposal $D_a$ such that for any $a \\in A$, we have $ min_{b \\in B} |a-b| \\leq D_a \\leq \\lambda  min_{b\\in B} |a-b| $ for some $\\lambda >1$.  From that, the paper can obtain an $\\epsilon$-approximation computational complexity of the estimation. To obtain the proposal distribution, a fast sub-routine (CrudeNN) is proposed. The experiments are designed to show that the proposed importance sampling has better relative error than the uniform sampling and is faster than the  KD-tree implementation.", "questions": "* As the paper mentions Chamfer is a fast alternative distance to EMD, the stochastic approximation of EMD should be discussed [1].\n\n[1] Improving Mini-batch Optimal Transport via Partial Transportation\n\n* For near-linear computational complexity, the sliced Wasserstein distance has the same complexity. Therefore, it is a direct competitor to the proposed approximated Chamfer and should be compared in a benchmark point-cloud task in the paper.", "limitations": "Not applicable.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "* Stochastic approximation of Chamfer distance is new.\n* The design of the importance sampling proposal is interesting.\n* An approximation error can be obtained.\n* The final approximation is faster than the conventional Chamfer distance.", "weaknesses": "* The proposed algorithm can only work with some restricted set of ground metrics that satisfies  (Hashing at every scale).\n* The main weakness of the paper is lacking real applications comparison. For example, the paper can compare the proposed approximation with the conventional Chamfer distance on a point-cloud reconstruction/completion task. \n* In deep learning applications, the gradient of Chamfer distance with respect to an input set is required. Therefore, some investigation about the approximation error of the gradient should be considered.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed and thorough comments. See our answers to specific comments below.\n\n**On the set of ground metrics which the algorithm works for.**\n\nWe emphasize that our methods work for any metrics which support a locality sensitive hash function (or such metrics squared). This encompasses a very wide class of metrics including $\\ell_1, \\ell_2$ (and generally all $\\ell_p$ for $1\\le p \\le 2$, the Jaccard distance, and even includes functions which are not strictly metrics such as $\\ell_p$ for $0 < p < 1$ and $\\ell_2^2$.  In addition, using standard metric embedding theory allows us to extend our results to more general metrics. We believe this demonstrates the wide applicability of our methods.\n\n**On real application comparisons**\n\nWe agree with the reviewer that the Chamfer distance is widely used in point-cloud reconstruction and completion tasks, often as a component of the loss function in a deep network. However, we would like to point out that the Chamfer distance is also widely used in many use cases beyond these tasks, with a very common application being comparing the similarity between two point clouds. This is evidenced by the fact that the Chamfer distance is implemented in many popular libraries such as PDAL [1], CloudCompare [2], PointCloud Utils [3], for the purposes of comparing point clouds.\nThe main practical application of our theoretical results is indeed to speed up the chamfer distance for point cloud comparisons with strong provable guarantees. Our experiments complement our theory and demonstrate its effectiveness, even on billion scale datasets.\nExploring the applicability of our method for reconstruction and completion tasks, which will likely require efficient estimation of the gradient of the chamfer distance, is an interesting future research direction.\n\n[1] PDAL, Documentation » Applications » chamfer\n\n[2] CloudCompare, User’s Manual for version 2.1\n\n[3] Point Cloud Utils, Functionality » Point Cloud Metrics​\n\n**Investigation on the approximation error of the gradient.**\n\nThank you for the comment. As stated above, we agree that exploring the application of methods to computing the gradient of the chamfer distance is an interesting future direction.\n\n\n\"**The stochastic approximation of EMD should be discussed Improving Mini-batch Optimal Transport via Partial Transportation**\"\n\nThank you for the reference. We would like to point out that the focus of our paper is not to motivate or argue for why the Chamfer distance is a useful approximation to the EMD, or an interesting similarity measure in its own right. This is a well established notion in the ML literature (as evidenced by the references in our paper and the references above).\n\nWith regards to the proposed reference, it is our understanding that while the proposed algorithm is fast, it cannot effectively approximate the EMD. The reference proposes computing the EMD on a smaller subsampled set of points as a proxy for the full computation on the entire dataset. In the worst case, this approach can require sampling almost all of the dataset to form any accurate approximation of the EMD, offering no practical speed up over the naive computation. To see this, consider the case where the two point sets A and B are both of size n and each have n-1 points at the origin. The nth point of A is located at 10 on the real line and the nth point of B is located at 11. The true EMD distance between A and B is clearly 1. However, if we don’t subsample Omega(n) points, then we will not sample the nth points of A and B, implying that the computed estimate is 0 with high probability. While this exact example is unlikely to occur in practice, it shows the fragility of the proposed method. In contrast, we have provable worst case guarantees for computing the chamfer distance in near linear time up to arbitrary accurate approximation, which we believe is a valuable contribution to the ML community.\n\n\n**On the sliced Wasserstein distance.**\n\nThank you for the reference. We agree that the sliced Wasserstein distance has a linear complexity, *if* the number of projections used is constant. However in practice, a prohibitively large number of projections are commonly used to effectively estimate the sliced Wassertein distance. For example, many practical works (see [a,b,c,d] below) recommend using at least d different random projections, where d is the dimension of the dataset, leading to a runtime of at least Omega(nd^2). In contrast, our method for the Chamfer distance provably runs in O(nd log n) time, to provide a 1% relative error estimate for worst case inputs. \n\n[a] Hierarchical Sliced Wasserstein Distance. Khai Nguyen, Tongzheng Ren, Huy Nguyen, Litu Rout, Tan Nguyen, Nhat Ho. 2023\n\n[b] Distributional sliced-Wasserstein and applications to generative modeling. Khai Nguyen, Nhat Ho, Tung Pham, and Hung Bui. 2021.\n\n[c] Improving relational regularized autoencoders with spherical sliced fused Gromov-Wasserstein. Khai Nguyen, Son Nguyen, Nhat Ho, Tung Pham, and Hung Bui. 2021.\n\n[d] Generative modeling using the sliced Wasserstein distance. Ishan Deshpande, Ziyu Zhang, Alexander G Schwing. 2018\n\n"}]

Author rebuttal:
We thank all the reviewers for useful comments and feedback. We will fix the typos and presentation issues in the final version of the paper. In what follows in the individual rebuttals, we address the issues identified by the reviewers as weaknesses and/or listed as questions. 


Meta-review: The paper addresses the computation of the Chamfer distance between two point sets, defined as the cost of mapping points from set A to their nearest points in set B, often used as a proxy for the earth mover's distance. While traditional methods involve quadratic time complexity, this work introduces an algorithm that estimates the Chamfer distance in near-linear time even in higher dimensions using importance sampling. This approach obtains an approximate contribution value for each point, then derives a weighted sample to efficiently estimate the Chamfer distance. Unlike mapping computations, which remain hard to approximate, this method proves valuable for efficiently estimating high-dimensional Chamfer distances, making a notable contribution to the field. Referees were mostly positive and recommend acceptance.
Decision: Accept (poster)