Fully Dynamic Algorithms for Chamfer Distance
Authors: Gramoz Goranci
Shaofeng Jiang
Peter Kiss
Eva Szilagyi
Qiaoyuan Yang
Venue: NeurIPS 2025 poster ()
Keywords: Chamfer distance
dynamic algorithms
Primary area: general_machine_learning

Abstract: We study the problem of computing Chamfer distance in the fully dynamic setting, where two sets of points $A, B \subset \mathbb{R}^{d}$, each of size up to $n$, dynamically evolve through point insertions or deletions and the goal is to efficiently maintain an approximation to $dist_{\mathrm{CH}}(A,B) = \sum_{a \in A} \min_{b \in B} dist(a,b)$, where $dist$ is a distance measure. Chamfer distance is a widely used dissimilarity metric for point clouds, with many practical applications that require repeated evaluation on dynamically changing datasets, e.g., when used as a loss function in machine learning. In this paper, we present the first dynamic algorithm for maintaining an approximation of the Chamfer distance under the $\ell_p$ norm for $p \in$ {$1,2$}.
Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, we obtain $(1+\epsilon)$-approximation in $\tilde{O}(\epsilon^{-d})$ update time and $O(1/\epsilon)$-approximation in $\tilde{O}(d n^{\epsilon^2} \epsilon^{-4})$ update time.
We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.

Fully Dynamic Algorithms for Chamfer Distance
Gramoz Goranci
Shaofeng H.-C. Jiang
Faculty of Computer Science
School of Computer Science
University of Vienna, Austria
Peking University, China shaofeng jiangūpku eerppluuedd..ee edu. cn
gramoz. gowanci www.nniiuiiiiiiiiieeei.ieeeieeee ac.
Peter Kiss
Eva Szilagyi
Faculty of Computer Science University of Vienna, Austria peter. kissuunivie ac.at at
Faculty of Computer Science
UniVie Doctoral School Computer Science DoCS University of Vienna, Austria eva szilagyiiiiao @univie. ac. at
Qiaoyuan Yang
School of Computer Science Peking University, China qiaoyuanyangostu. pku. edu. cn
Abstract
We study the problem of computing Chamfer distance in the fully dynamic setting, where two sets of points A, B C Rd. each of size up to dynamically evolve through point insertions deletions and the goal is to efficiently maintain an ap- proximation to distch (A, B) = ΣeSa minse dist(a, b). where dist is a distance measure. Chamfer distance is a widely used dissimilarity metric for point clouds, with many practical applications that require repeated evaluation changing datasets, e.g., when used as loss function in machine learning. In this paper, we present the first dynamic algorithm for maintaining an approximation the Chamfer distance under the Ep norm for p E (1,2). Our algorithm reduces to approximate nearest neighbor (ANN) search with little overhead. Plugging in standard ANN bounds, obtain (1 approxxmaatiiiionn in Ō(E-d) update time and (L/e)) approxmmaatnn in Ö(dn" 4) update time. We evaluate our method on real-world datasets and demonstrate that it performs competitively against natural baselines.
dynamically
Introduction
We consider the problem computing the Chamfer distance, a popular dissimarlity metric between point clouds. Given two sets of points A, B c Rd each of size up the Chamfer distance of A from B with respect to distance measure dist 12d Rd + R>o is defined as
distcu (A, B)
Σ min dast(a,b) 6).
BEB
The Chamfer distance is typically defined with respect distance measures such as Manhattan and Euclidean metrics. It has found wide range of applications in various domains, including machine learning [KSKW15, WCI. + 19], computer vision [AS03, IJG05, FSG17, JSQJ18), and geometric
Authors listed in the alphabetical order.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

computing [HSS 24]. 24]. as a computationally efficient alternative to the more demanding Farth-Mover's distance (EMD) [KSKW15, AM19].
Due to its strong empirical performance, the Chamfer distance is often used
In many practical applications, the Chamfer distance is repeatedly calculated on evolving datasets. A notable example is cloud completion and up-scaling, where the models aim to reconstruct missing regions or enhance the resolution of 3D point clouds. In such tasks, the Chamfer distance is commonly used as loss function during training and it must be evaluated continously as the model's predictions evolve [LYH+23, LLZ*24, 24, WPZ*21]. Two other mainstream use cases include (1) object reconstruction from video sequences. where the objective is to represent objects as point clouds based on observations from moving camera [RLT*20, TMPF22. 23]; and (2) medical imaging, where it is used to track anatomical structures (such as heart motion on ultrasound images) over time [VHK94, HB91, MDJT14).
Motivated by these applications, we pose the following fundamental question: Can the Chamfer distance be maintained under dynamically evolving point sets? More concretely, consider two input sets A an B that undergo point insertions or deletions, referred to as updates. The goal is to design a dynamic algorithm that efficiently supports these updates while maintaining an estimate that approximates the Chamfer distance up to a small relative error. A naive solution to handle such updates is to recompute the Chamfer distance from scratch after each update. However, this is computationally prohibitive: the best- static algorithms require either (1) O(n² d) time for exact computation or (2) O log ne 2) [BIJ + 233,, for a (1 + e)pprooximmtiion when the underlying metric is an lp norm for E (1, 2). In summary, even for low-dimensional datasets, these off-the- shelf static algorithms cannot go beyond the linear time barrier for handling updates.
In this paper, we obtain the first dynamic algorithm for maintaining an estimate to the Chamfer distance under the lp norm for p E [1, which significantly outperforms the linear-time update barrier. Our problem reduces to nearest neighbour (NN) oracles: given parameters a > 0, 2 1, there is a data structure that maintains dynamic point-set B Rdd and supports in time the following opertions (i) insert/delete a point in B and (ii) given a point x, return an (1 + ((a))- approximate nearest neighbour of in B. We call such a data structure an (1 + ((a)) -aprox-apeo NÑ oracle with time parameter т. Plugging in known bounds for NN oracles, our algorithm achieves constant (or even (1 + e)) approximation and supports very fast updates across different parameter regimes. The guarantees of our algorithmic reduction are summarized in the theorem below.
Theorem 1.1. Let A, B be two sets of points from R&, with |A), |B| S n, and let E (0,1) > 0. and v 2 1 be parameters. Assume that there is a (1 +1+8 ((a))) apprrxxmmate NN oracle with time parameter T. Then there is a dynamic algorithm that supports insertions and deletions of points to A and B in Ö(T) worst-case time per update, and when queried. with high probability, it returns (1+ + -ppproooxnnttion to distch(A, (A, in D((d+T)c max{11, (1,2?)) time, when the underlying metric is the Manhattan (f1) metric.
The state-of-the-art trade-offs for (1 + aaproxxapto NN oracles differ between low and high dimensions: (a) for low dimensions, the trade-off is = with query/update time T = Ö( [AMN+98], while (b) for high dimensions, we have
O(1/c) with = Ö(dn²) [AR15]. Substituting these bounds in Theorem 1.1, we obtain dynamic algorithms for the Chamfer distance achieving (1 (1+el -)aaproxxiittion in Ö(E update time and an ((1/e)-app -approximation in Ö(dn e
update time. 2 Moreover, using known embeddings from Eg into f,, Theorem 1.1 readily extends to the setting when the underlying metric is Euclidean (E2) (see Appendix A for details).
Our dynamic algorithms maintain an estimate the Chamfer distance distcn (A, B) with provable approximation ratios. It is natural to ask whether it is possible to maintain the underlying assignment g: A B that attains these approximation ratios, i.e., Σ.e dist(a, (a)) < (1 (e) --)dditcsnn( (A, B). Since reporting the assignment itself takes (n)) time, reporting the changes in the assignment due to an update, also known as recourse, would be desirable. Unfortunately, turns out that any dynamic algorithm that maintains an a-approximate assignment between A and B must have at least 2(n) recourse, and thus also 2()) update time (see Lemma 1. 1). In fact, for any constant > 0, [BI] 23]
'The stated bounds on the update time are in fact stronger in that they achieve a better dependency on the dimension d. This is because Theorem 1.1 presents only a simplified version of our main result; the precise trade-offs are given in Theorem 1.
2

---

show that even in the statie setting, reporting a (1 + appproxxie assignment requires (2 2-2) time under the hitting set conjecture [Wil18].
Experiments. We implement our algorithm and validate its performance over four real datasets covering both high and low dimensions, as well their noisy versions with injected outlier points. In all datasets, our algorithm achieves less than 10% eπrоr using only hundreds of samples, even against injected outliers, in time up to magnitudes better than a naive dynamic algorithm. We also discover that a simple uniform sampling baseline is competitive for these real datasets, but its performance degrade significantly when outliers are present, where our algorithm has a clear advantage.
1.1 Technical Contribution
We employ an importance sampling framework to estimate distcH B), and our main contribu- tion dynamic data structure that maintains an importance sampler. This importance sampling framework was introduced in [33]+ in static setting, where the key idea is to compute coarse Olog n) approxxxxee assignment ğ from A B, and then sample with probability proportional to the distance (a, {(a)). A standard importance sampling argument shows that an average of Ó(1) samples suffices for (1 >approximation to distcH (A, B).
However, it difficult to explicitly maintain the approximate assignment g in the dynamic setting. since the recourse/change of 9 can already be very significant per update (let alone the running time). To resolve this issue, our dynamic sampler obtains these sampling guarantees with an implicit representation of distance estimates dist, a E A such that dist, is an Olog" n) approximation to minge & dast b) for a E A in Õ(d) update time. This sampler only generates a sample à E A, and the final estimator for the importance sampling is computed through (log" n e -² max a²)) = Ó6-2 max 1, a²)) queries to (1 + ((aa)-approximate nearest neighbor oracle. This eventually leads to a (1 + a appprooxxiitoonn to distcH(A, (A, B).
Our dynamic sampler (similarly to the static algorithm of [BIJ+23)) relies on a family of partitions of the input plane Ed into series of nested cells that exponentially decrease in size lower levels (also known as andomly-shifted quadtree in the literature). For each a E A, we say that a is matched in some cell of our decomposition if it is the smallest cell that contains a and any point of B. The size of this unique sub-cell serves as an approximation to minge dist(a, b). Our goal is to implicitly maintain some information about the unique matching cell for all a E A.
Importantly, we cannot afford to explicitly maintain the matching cell for each point a E A as it could change for ((1)) points of A due to a single update in B. Instead, for each cell we maintain how many B inside that sub-cell. This allows us to implement a sampler
points of A happen to be matched that, instead of explicitly sampling a point of A, samples a cell in our nested decomposition based on its size and the number of points of A matched in it. Once a cell is sampled, our goal is to sample a uniformly random point of A matched in that cell. To achieve this, every cell maintains dynamic sampler which allows it to sample one of its sub-cells in our family of partitions with probability proportional to the number of points of A in that sub-cell. Repeating this sub-cell sampling process through the ((1) levels of the algorithm finds cell that contains single point of A, which we then return.
1.2 Related Work
In the static setting, [BII+23, F125) present near-optimal algorithm for estimating the Chamfer distance, running in Ö(nd - time. For comparison, dynamic algorithm handles point updates in near-optimal time proportional Ö(d), up to the cost of invoking the nearest neighbour oracle.
Perhaps the closest problem to the dynamic Chamfer distance is the dynamic maintenance of the Earth Mover distance (EMD), for which Chamfer distance is often used as proxy in practical appli- cations [KSKW15, AM19J. For d = 2, dynamic EMD is known to admit an algorithm that achieves O(1/e) approximation in O(n-/r) update time [GKP+25]] In contrast, our dynamic algorithm for the Chamfer distance extends to any dimensions, and can even achieve an improved approximation ratio of (1 + e) in low dimensions. Similar to our negative result on the recourse, [GKP+25 25) show that maintaining mapping to the dynamic EMD problem that achieves an approximation ratio better
3

---

than 2 requires at least Q(n) time, even for 1 dimensional point sets. This highlights the difficulty of dynamically maintaining mappings underlying different proximity measures between point clouds.
Recently, there has been a growing interest in designing dynamic algorithms for fundamental problems in machine learning, thus contributing towards the grand vision of building library of efficient data structures for key machine learning primitives. Notable progress has been made on several fronts, including dynamic algorithms for various clustering objectives such as k-center [CGS18 18, GHL+21, BEF CFG*24, BHMS23, LHG+24, CLSW24), k-median/k- means [CHP* 19a, HK20, BCLP23], facility location [GHL18, CHP+ 19b, BGJ+241 correlation clustering [CLMP24], well as dynamic matrix multiplication for structured matrices arising in machine learning applications [AvdBM25].
Preliminaries
Definition 2.1 (Chamfer distance). Given two point-sets A, B C IRd with max [|A], |B] S n, the Chamfer distance is defined as distch(A, B) == EnEA minseB dist(a, 6). For a 2 1, we say that a value jú is an a approximation to distcu(A, B) if I distcH (A B) S fu a.
We will refer to minse & dist(a, b) as distch(a, B). We will use the following dynamic nearest- neighbor data structure as a subroutine in our algorithm.
Definition 2.2 (Dynamic nearest-neighhor data structure). Given a > 0 and a dynamic point set B C Rd [B] S n,, (1 + ar) -ppproxiieteee dynamic nearest neighbor data structure with update time and query time r(a) with respect to the & norm is a data structure which can be maintained in T r(a) update time as B undergoes insertions and deletions, and when queried for point a E R returns a value tha such that Paa I minse ||a bll2 S (1 + o Sa with (1 1/ poly(n)) probability in r(o) time.
Throughout this paper, we assume that the input points are contained in [U/] for some U poly(n). which is a power of 2. Furthermore, we assume that during all updates to the input sequence, the aspect-ratio of the input points maxae ||a - bll1/ min I|a la-blla is upper bounded by = pooy(()) 2c, for some integer L C20 O.
Lemma 2.3 (Dynamic Weighted Sampler). There exists a dynamic algorithm that maintains weighted sel of elements A (a)..... ,O.} with corresponding weights W = =w((a)), (aa()).... w((a)) undergoing insertions and deletions. Upon query, the algorithm relurns element of such that a, E A is returned with probability w(a,)/ Eje(n) w(az). Both updates and queries are supported in Ollog n) worst-case update and query time.
Data structures similar to that of Lemma 2.3 have appeared before in literature, but for sake of completeness include an implementation in Appendix B.4.
2.1 Dynamic Quad-Tree
Our algorithm relies on the dynamic quad-tree data structure [dBHTTO7]. The quad-tree is constructed as follows. We first choose random vector described by [0, UJ We then shift all input points with the vector described by x, hence after the shift they will be contained in 2. Uld. With slight overload of notation, we will refer to the shifted points as A and B.
Consider a series of O(log n) grids drawn the input space, where the i-th grid has side length U. 21-i, The quad-tree is then a rooted tree T, where each node v E T is associated with some cell C, of these grids with side length L(v). The root of I' corresponds to the smallest cell among all the grids which contains all input points. Any node v the tree T such that C, contains more than one point of the input has child nodes in T' corresponding its non-empty sub-cells on the next level of the grid decomposition with side length L(v)/2 The leaves of T correspond to the largest cells of the decomposition containing a single point of the input. As the aspect ratio of the input assumed to be o = (n). the tree consists of (log Φ) = L layers. As each input point may appear once in any of the cells of all these layers, T has most O(n log n) nodes.
[dBHTT07] has shown how to maintain this representation of the input in Oil log worst-case update time such that all nodes of the tree store the number of input points in their respective cell and

---

the leaves explicitly store the single imput point stored in their cell. For our application, we further impose that every cell aware of the number of input points in its cell from A and B separately.
3 Dynamic Algorithm
We start by deseribing an algorithm that achieves slightly worse guarantees than described in Theorem 1.1. Namely, this algorithm will maintain the estimate of the Chamfer distance between two sets with constant probability. Formally, we will first prove the following result.
Theorem 3.1. Let A, be two sets in space Rd, with |A,, |B] S n, and let r(a) be the update and query times of a (1 + a appppoxxiia dynamic nearest-neighhor data structure. There exists dynamic data structure which can be maintained in O(d log + log" n r(((a)) worst-case update time as A and B undergoes point insertions and deletions and can be queried to return a (1 + + -pprrooxiiitooon to distcu (A, B) between A and B w.r.t. l f--norm in Ollog" n.e m..e- max (=2, 1 (dlog"
and E (0, 1) parameters.
(({())))) time with 3/4 probability.
In Section 3.4, we show how to boost the above result to obtain our main result, i.c. Theorem 1.1, which on query returns (1+a++e) (L+a+t)-appron -approximation to distcH (A, B) with probability (1- 1/ poly(n)). In the following sections, we describe our dynamic algorithm on a high level. For sake of complete- ness, we include pseudo-codes of our algorithm in Appendix C.
3.1 Algorithm description
We say that a point a E AA U B belongs to a node e of level of quad-tree T if E C... We say that point a E A is matched belong to it (where we assume that the root has the highest level as it corresponds to the largest cell containing all the input points). Note that every point of B may belong to L O(log n) nodes of T, but all points of A are matched at exactly one node of T. For each a E A denote this unique node by Vo.
if is the lowest level node of T such that both and any point of B
3.1.1 Handling an Update
We augment the dynamic tree structure of Section 2.1 with the following information being stored at each node v E number of points YA (v) from belonging to v, number of points (B) from B belonging to and the number of matched points (()) from A at v. Note that 7B (v) and (A(v) can be maintained using the algorithm of [JBHTT07].
We also maintain a dynamic sampler NODE-SAMPLER(1)) corresponding to each node v of T, and a global sampler TREE-SAMPLER(T for the whole T. The sampler VODE-SAMPLER(1) is for the set fu E T u a child of e A C. n B = 0} w.r.t. weights " (u). The sampler (REE-SAMPLER(T) is for the of all nodes of T with >(v)
w.r.t. weights wT( L(v) (w).
For sake of simplicity of the presentation, assume that at all times B + 0. We will now describe how the algorithm updates y values for all E 7 after each update. Assume point is deleted from or inserted into A U B. Through iterating along the path starting from the leaf of containing x and ending at the root r, the algorithm finds the path of nodes ......, 2k of T whose cell does not contain a point of B x (ordered from the leaf). Let v' be the ancestor of Up in T. We distinguish between four cases.
1. Insertion of x into A: set ((²) = x(v) +1.
2. Deletion of x from A: set ((0)) >(0) -1
3. Insertion & into B: set 7(0') = -((0) - 7a(U)), r(01) = (A(1)) and 7wx) =
(a(1;) 7 (1 for k 2 i>11
4. Deletion of x from B: set (10))((=(000) >0') + +1EN ((x) and 7(x)) = 0 for E [k].
:
The correctness of our algorithm maintaining 7(v), v E T is proven by Claim 3.3.
3.1.2 Answering Queries
The queries are answered using importance sampling based sampling process for points in A.
5

---

Sampling points in A. To sample a single point from A, we first sample node v from T using TREE-SAMPLER(T), Then, we sample a child of using NODE-SAMPLER()), After this, we recursively call NODE-SAMPLE point contained in it.
until we reach a leaf of T, when we finally return the unique
Claim 3.5 shows that this sampling process returns point a E A with probability L(va)/ Σver 7(V)- L(v), where we recall that 2u stands for the unique cell a is matched in. Claim 3.4 shows that [(va) (as B) within poly(log factors.
Estimating the Chamfer distance. Using our sampler, estimating distcH B) turns into standard application of importance sampling. Function NN(a, B, a. refers to any procedure for finding a (1 + approximation the nearest neighbor of a in set B.
Specifically, we estimate (As B) through taking m = 240 L log n max(a?, 1} e = Ologg n- maxaa""" 1), c) samples S from A through the after- mfter-mentioned sampling procedure. For each S, then query the nearest neighbor data structure generate (1 + a/4) approximation to distcH (a, B). Refer to these values as (N B, a/4) for a E S.
We assign weight of (N B, (()) L(v)/ [(va) ) to each E S. This implies that the weight of each sample is a (1 + (aaaaaaappoooimmaatii of distcH (A, B) in expectation. We then finally return the average of these weights (shifted by 1/(1 + c/2) fit our definition of approximation).
3.2 Correctness Analysis
This section is devoted to an overview of the proof of Lemma 3.2, which establishes the correctness of our algorithm.
Lemma 3.2. On query, the algorithm returns a (1 e + a)) apprrxxiimtao distcH (A, B) with 7 7/8 probability.
We start with examining the variables 7(v). corresponding to the number of points from matched node v.
Claim 3.3. The value of (v) for all e T is maintained correctly after an update.
Proof. When an update occurs to a E A, the only y value changes is (Va)). The algorithm greedily finds Va and updates (vaa accordingly.
When an update occurs to E B, the algorithm finds all nodes of T that contain only b from B, 01,---3 Uk (ordered from the leaf upwards) and o' the node with the smallest cell containing and an and e may have its value updated.
other point of B. Observe that only U1,
......,, U1,...,
In the case of deletion, all points of A matched in Ui....s U2 should be matched in of after an update, and the algorithm updates values accordingly. In case of an insertions, every point A in Cp should be matched in the smallest cell among Co,...., Cog they are contained in (if there is such a cell). The algorithm similarly updates y values accordingly.
The following claim allows to estimate distcH (a, B) with value L(va). The proof is deferred to Appendix B.2. Our proof is similar to lemma of 23], however our lower bound on L(va) with respect to distcH (a, B) is slightly weaker due to the limitations of the dynamic model.
Claim 3.4. The following statements hold with respect to the random shift of the quad-tree (see Section 2.1).
(i) With 1/ (nly(n) probability I(va) 2 disticu (a.B) holds for all a E A. 1ogn-3
(ii [V[(v.)] < 2 L distcn(a, B)) holds for all E A, where L denotes the height Tf
From Claim 3.4 we have that L(va) ~ distch(a, B). Hence, the following claim shows that the sampling process of the algorithm samples E A with probability roughly proportional to its contribution to distch (A, B). Its proof is deferred to Appendix B.3.
Claim 3.5. The algorithm samples E A with probability L(va)/ (vw))/Eeer L(v) 7(0).

---

Table Specifications of datasets and experiment parameters.
dataset
dimension d
|A]
[B]
window size
sample size
Text Embedding
300
-1.9k
-1.2k
100
150
ShapeNet
3
-2k
-2k
100
150
Aeshion-MNIST
784
60k
10k
500
200
SIFT
128
1000k
10k
500
300
The remaining proofs follow the standard analysis for importance sampling. Our main goal is to bound the variance of a single random variable defined by the weight assigned to each of the m samples of A the algorithm draws query. The proof is deferred to Appendix B.5
Claim 3.6. Let X standfor the random variable defined by NN B, a.a/4). (v) L(v)/ ((e)/L(a)) L(va) when the algorithm samples point a E A. Then, with high (1 - 1/ polp probability Var (X] S C'H 132 logn- [ 12o².
We are now ready to finally prove Lemma 3.2, which is a standard application of importance sampling. Given random variable X with expectation EJ X] and variance [[X]² 2 o the average of (á/ i.i.d. samples of is a (1 c>-aprroximation to [ with > 1/2 probability by Chebyshev's 's inequality.
In our case, E[X] is (1+a/4)-apppp approxiitte to distcH(A, (A, B) and & O(a2e -2 log n) by Claim 3.6. Hence, we conclude the main lemma of this section Lemma 3.2. We defer the proof to Appendix B.6
3.3 Running time
Lemma 3.7. The algorithm of Section 3.1 has O(d llog + loog n + r(O(a)) and O n -2 m22max(1 a²) (d n + r({(a)))) worst-case update and query times, respectively.
Proof. Note that updating the quad tree itself (and the corresponding YA. YB values) takes Od log n) time using algorithms from literature [dBHTT07]. Observe that insertions and deletions both to A and B require the algorithm identify the set of vertices of T the affected point falls in and simply to adjust the value on a subset of these nodes. Hence, this requires at most Odd L) = O(d log time.
The algorithm also needs to update its internal global CREE-SSMPLER'S (T) and NODE-SAMPLEN SAMPLERS
for all v T. Observe that the total number of updates these samplers undergo is proportional to the number of nodes of which change their Yo (A) or To values, that is Ollog n). By Lemma 2.3 this takes (log² n) time as each sampler contains at most |A| S n elements. In addition, the algorithm needs to maintain its dynamic wearest-neighber data structure.
On query the algorithm needs to sample m = (logg n -max a² -. samples, for each of which it queries the nearest neighbor data structure. Each query requires first call TREE-SAMPLES (T). then walk from the sampled node to a leaf at each step of which NODE-SAMPLER is queried. Hence, this takes (dd log" n m) = O(d n m -2) time.
3.4 Boosting for a High-Probabilie Guarantee After Every Update
We show to derive Theorem 1.1 from Theorem 3.1. To this end, while maintaining the internal data structures of Theorem 3.1, on query output the median result of O(log n) queries to the baseline algorithm. This will result in the same update time, but O(log n) blowup in query time.
In terms of correctness, consider the logn outputs the algorithm produces. Each of them is an (1 + a + >>-approximation to dist. (A, B) with 3/4 > 1/2 probability. By standard application of Chernoff bound with high (1 - 1/ (n)) probability more than half of these query results will be (1 + a + approxxiint,, hence so is their median value.
4 Experiments
We implement our dynamic algorithm and validate its performance on various datasets. Observe that handling update of A is straightforward (by simply querying an NN oracle on B), whereas
7

---

Text Embedding
0.12
Ours
Uniform
Relative Erro
0.06
0.04
0.02
0.00
200
400
6000
800
1000
1200
Steps
ShapeNet
Ours
Uniform
0.15
Relative Error
0.10
0.05
0.00
250
500
750
1000
1250
1500
1750
2000
Steps
Fashion-MNIST
0.05
Ours
Uniform
0.04
Relative Enro
0.03
0.02
10000
Steps
SIFT
0.08
Uniform
Relative Error
0.06
0.04
0.02
2000
4000
6000
8000
10000
Steps
Figure Relative error curves for datasets without outliers. These experiments are independently run for 5 times, and we report the average (the dot), max and min values (the shaded area) after every to updates (depending on the dataset) where is the window size.
5
is more challenging. Hence, to simplify the exposition (but still keeping the key challenge), we focus on the default setting where B is dynamic and A is static set. For completeness, we also include the case that both and B are dynamic Appendix E, and the results are similar as in the default setting.
allowing updates
Our first baseline is a naive exact algorithm, which we call "Benchmark", where for each update of B, it re-computes dist(a, B) in Ol) time for each whose current dist(a, B)
Baselines.

---

Text Embedding with Outlier
Ours
2.0
Uniform
Relative Error
1.5
1.0
0.5
0.0
200
400
600
800
1000
1200
Steps
ShapeNet with Outlier
1.4
Ours
1.2
Uniform
Relative Error
1.0
0.8
0.6
0.4
0.0
250
500
750
1000
1250
1500
1750
2000
Steps
Fashion-MNIST with Outlier
1.2
Ours
Uniform
Relative Enar
0.8
0.6
0.4
0.2
6000
8000
10000
Steps
SIFT Outlier
0.150
0.125
Uniform
Relative Enror
0.100
0.075
0.000
2000
4000
6000
8000
10000
Steps
Figure 2: Relative error curves for datasets with outliers, with the same setup as in Figure
value may be affected by the update. This serves benchmark for the approximation ratio. The second baseline, called "Uniform", replaces our important sampling with a uniform sampling (while keeping the other steps the same).
Datasets and Experiment Setup. We employ four real datasets covering both high and low dimensions in the experiment: Text Embedding [KSKW15], ShapeNet [CFG+15] 15), Fashion- MNIST [XRV17], and SIFT [JDS11]. Each dataset consists of larger set which we use as A, and smaller set which we use as The ShapeNet dataset consists 3D point clouds and is widely used to measure the similarity between different shapes. The Pashion-MNIS and SIFT datasets were

---

0.204
Text Embedding
0.634
Benchmark Uniferm
0.011
Datasets
ShapeNot
0.014
0.001
0.902
MNIST
64.844
0.333
2.694
SIFT
10
10
10
10a
10a
Running Time (ms)
Figure 3: Average running time per window update for all algorithms on datasets without outliers.
also known to be used as benchmarks for approximate nearest neighbor search, Similar choice of us- ing ANN benchmark datasets was also made in previous work, to evaluate the performance of static algorithm for Chamfer distance [BIJ#23] Furthermore, to evaluate the robustness of the algorithms, we inject outlier point into each dataset: compute the geometric mean
T Eaes a, pick an arbitrary E A, and generate an outlier as = 0.1 |A] (a* - c) + c. Intuitively, this "moves" a" along the direction of a" by large distance. Finally, since these datasets do not contain information of dynamic update, we employ a sliding window (on B) to simulate the insertions and deletions. The detailed specification of the dataset and the experiment parameters be found in Table
Implementation Details. Recall that our algorithm (and the Uniform baseline) consists of sampling step and then a second step to build the estimator that makes use of a nearest neighbor query structure. Since the window size for each dataset is relatively small, choose exact nearest neighbor algorithm, which does not introduce additional errors and allows for a more accurate evaluation. For the 3D ShapeNet dataset, we implement nearest neighbor queries with KD-trees, which can efficiently perform exact search in low-dimensional spaces. All algorithms are implemented C++ and compiled with Apple Clang version 15.0.0 at -03 optimization level. All the experiments are run on MacBook Air 15.3 with an Apple M3 chip (8 cores, 2.22 GHz), 16GB RAM, and macOS 14.4.1 (23E224).
the
Experiment Results. Our main experiment evaluates both the error of the estimated Chamfer distance and the running time of the algorithms, over the sliding windows. We depict the relative етrоr curve in Figure and Figure 2.
Here, the relative error for an estimate É over the accurate Chamfer distance E is defined as [E-B] Overall, our algorithm achieves less than 10% error using only hundreds of samples. Compared with Uniform baseline, our algorithm achieves comparable error and variance for datasets without outliers, and shows clear advantage when the dataset has the outlier. This showcases the robustness of our algorithm. We observe that our algorithm performs slightly worse than Uniform in the SIFT dataset (without outliers), but this is because the distance {dist(a, B): E A} is very uniform (see Figure in Appendix D), hence uniform sampling is already the "optimal" sampling strategy.
E
We report the average running time per sliding window update in Figure 3. Our algorithm is magnitudes more efficient than the Benchmark on larger datasets. incurs slightly higher time cost than Uniform which is expected since Uniform does not need to maintain any additional structure to generate a sample. The results for datasets with outliers are similar to that in Figure and can be found in Figure 5 (Appendix D).
5 Acknowledgments
The authors would like to thank the anonymous reviewers for their insightful comments. This research was funded in part by national key R&D program of China No. 2021 17000000,,0 and the Austrian Science Fund (FWF) 10.55776/ESP60888044
10

---

References
[AM19]
Kubilay Atasu and Thomas Mittelholizer. Linear- complexity data-parallel earth mover's distance approximations. In Kamalika Chaudhuri and Ruslan Salakhutdinov, edi- tors, 36th International Conference Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pages 664-373. PMLR, 2019. URL: http://proceedingg mlr. wew..presssvvv preass/S97atasu19a att.saaaalll.... httml.l...mm.......mm.mmm....... html.
[AMN 98] Sunil Arya, David M. Mount, Nathan S. Netanyahu, Ruth Silverman, and Angela Y. Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. ACM, 45(6):891-923, 1998. doi: 10. 1145/293347 2933448.
[AR15]
Alexandr Andoni and Ilya P. Razenshteyn. Optimal data-dependent hashing for ap- proximate near neighbors. In Rocco A. Servedio and Ronitt Rubinfeld, editors, 47th Anmual ACM Symposium on Theory of Computing (STOC), pages 793-801. ACM, 2015. doi 10. 1145/2746539 2746553
[AS03]
Vassilis Athitsos and Stan Sclaroff. Estimating 3d hand pose from cluttered image. In 2003 IEEE Computer Society Conference on Computer Vision and Puttern Recognition (CVPR 2003), pages 432-442. IEEE Computer Society, 2003. doi: 10. 1109/CVPR. 2003 1211500.
[AvdBM25]
Emile Anand, Jan den Brand, and Rose McCarty. The structural complexity of matrix-vector multiplication. CoRR, abs/2502.21240, 2025. URL: attps://dol 2Fg/10.48550 aarvvvrrvvvv/v 250. 21240, arxiv: 21240, doi:10. 00004455500AAAA 2502.21240.
[BCLP23] Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, and Nikos Parotsidis. Fully dynamic k-clustering in ō(k) update time. In 36th Conference Neural Information Processing Systems (NeurIPS), 2023. URL: /tttt:://ppprsse nipssrrrrnnnns........sse.ssssss cc/ paccppppr_fffe la fil.e/ieeepppee /aper// html.
[BEF*23]
MossmmadHossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Hen- zinger, Rajesh Jayaram, Vahab Mirrokni, and Andreas Wiese. Optimal fully dynamic k- center clustering for adaptive and oblivious adversaries. Nikhil Bansal and Viswanath Nagarajan, editors, ACM-SIAM Symposium Discrete Algorithms (SODA), pages 2677- 2727. SIAM, 2023. URL: https:/ http://doooooo///////// 10. 97877771977111117755544... ch101, doi: 1137 / 9781611977554 19711194.51111.1..... CH101.
[BG] 24]
Sayan Bhattacharya, Gramoz Goranci, Shaofeng H.-C. Jiang, Yi Qian, and Yubo Zhang. Dynamic facility location in high dimensional euclidean spaces. In 4/st International Conference on Machine Learning (ICML). OpenReview.net, 2024. URL: https:// openreview htt.:/oormmmiidruuIsiose
[BHMS23]
Leyla Biabani, Annika Hennes, Morteza Monemizadeh, and Melanie Schmidt. Faster query times for fully dynamic k-center clustering with outliers. Al- ice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, 36th Conference on Neural Information Processing Systems (NeurIPS), 2023. URL: http:: mips. http/pppeefflll//ppeeeeeeeeeeeee fiw.ff wwwps//pppeeeee//////// 2tap://888..22111777744000a22212
html.
[3] Ainesh Bakshi, Piotr Indyk, Rajesh Jayaram, Sandeep Silwal, and Erik Wain- garten. Near-linear time algorithm for the chamfer distance. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, 36th Conference on Neural Information Processing Systems (NeuriPS), 2023. URL: http://papers nips www.. wtpp.c.c//pppee..lleeeeeeeeeeeee 1at.eeaaaa..11144444000000088683
.ht.l.reeeeeee...........m html.
[CFG 15]
Angel X. Chang, Thomas A. Funkhouser, Leonidas J. Guibas, Pat Hanrahan, Qi-Xing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song. Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu. Shapenet: An information-rich 3d model repository. CoRR, abs/1512.03012. 2015. URL: http://aaxii: http//axivvvrrrre org/ abs/ 1112 01552.000111 03012, arXiv:
03012.
[CFG+24] Emilio Cruciani, Sebastian Forster, Gramoz. Goranci, Yasamin Nazari, and Antonis Skarlatos. Dynamic algorithms for k-center graphs. In David P. Woodruff, editor,
11

---

ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3441-3462 SIAM, 2024. doi :0.1:0..: 11771111.98811119779912 123.
[CGS18)
T.-H. Hubert Chan, Arnaud Guerquin, and Mauro Sozio. Fully dynamic k-center clus- tering. In Pierre-Antoine Champin, Fabien Gandon, Mounia Lalmas, and Panagiotis G. Ipeirotis, editors, Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, pages 579-587. ACM, 2018. doi:10. /115/1111886. 31861144.
[CHP 19a] Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence A'ché-Buss Emily B. Fox, and Roman Gamett, editors. 32nd Conference Neural Information Processing Systems (NeurIPS), pages 1250-32660 2019. URL: StRL:tttts//pproceeeingg iew.rreeeeednnnnnnnnii.pps. ctc cc/paper/2019/ haaa:fffaes$salff99955555daaaadd Abstract.bbbtttttcoooooccaaa html.
[CHP* 19b] Vincent Cohen-Addad, Niklas Hjuler, Nikos Parotsidis, David Saulpie, and Chris Schwiegelshohn. Fully dynamic consistent facility location. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence Alché-Buc, Emily B. Fox, and Roman Garnett, editors, 32nd Conference Neural Information Processing Systems (NeurIPS), pages 3250-3260, 2019. URL: http::tt//////cceiiiiii newripe http://dwaaggaaaaeaepcccca/p///p cc/pappr/2019/ haaa:ffaaeeBaarf944533aaaaaaa
Awstrratttttttte.eeeeeee.eaaaa.e html.
[CLMP24] Vincent Cohen-Addad, Silvio Lattanzi, Andreas Maggiori, and Nikos Parotsidis. Dy- namic correlation clustering in sublinear update time. In 41st International Conference on Machine Learning (ICML). OpenReview.net, 2024. URL: net/ het/forum?icn 3d-3m5sdd33
[CLSW24] T.H.. Hubert Chan, Silvio Lattanzi, Mauro Sozio, and Bo Wang. Fully dynamic k-center clustering with outliers. Algorithmica, 86(1):111-193, 2024. URL: attps://doi org/10.
0000453-022--015---,, 01159-3, doi 10000000005000200000 00000-0002---1----2--
[dBHTT07] Mark de Berg, Herman Haverkort, Shripad Thite, and Laura Toma. Vo-efficient map overlay and point location in low-density subdivisions. In Takeshi Tokuyama, editor, Algorithms and Computation, 18th International Symposium, ISAAC 2007, volume 4835 of Lecture Notes in Computer Science, pages 500-511. Spriner, 2007. :o1: 1007 20007/97783--4-7 3-03--500--7 1-1---3-54--77-2--- 77120-31 -4.
[F125]
Ying Feng and Piotr Indyk. Even faster algorithm for the chamfer distance. In Keren Censor-Hilled Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis, ed- itors, 52nd International Colloquium Automata, Languages and Programming (ICALP), volume 334 LIPlcs, pages 76: 16:1176:18. Schloss Dagstuhl Leibniz-Zentrum für Informatik, 2025. URL: https: /oii. org/10. /ttp:/...233///// doi:10. 4230/LIPICS ICALP. .025. 76.
ICALP 2025. 76,
[FSG17]
Haoqiang Fan, Hao Su, and Leonidas J. Guibas. A point set generation network for 3d object reconstruction from single image. 2017 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2017, pages 2463-2471. IEEE Computer Society, 2017. doi: 10. 1109/CVPR.... 2017. 264.
[GHLI8]
Gramoz Goranci, Monika Henzinger, and Dariusz Leniowski. A tree structure for dynamic facility location. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th European Symposium on Algorithms (ESA), volume 112 of L/PIcs, pages 39:1- 39:13. Schloss Dagstuhl Leibniz-Zentruum für Informatik, 2018. URL: httpp:///d/ org/10. 4230 4230/LIPICS /LIIIIIPCC.C ESA 2018. 39, doi 10. 4230/LIPICS. ESA 2018.201... 39.
[GHL+21] Gramoz Goranci, Monika Henzinger, Dariusz Leniowski. Christian Schulz, and Alexan- der Svozil. Fully dynamic k-center clustering in low dimensional metrics. In Martin Farach-Colte and Sabine Storandt, editors, Proceedings of the Symposium Algo- rithm Engineering and Experiments, ALENEX 2021, pages 153-153. SIAM, 2021. doi: 000.1117/199911611199911
[GKP+25] Gramoz Goranci, Peter Kiss, Neel Patel, Martin P. Seybold, Eva Szilagyi, and Da Wei Zheng. Fully dynamic Euclidean bi-chromatic matching in sublinear update time. 267:20162-20186, 13-19 Jul 2025. URL: https: htaps://proceedings www.nng..........m.............m mww. .re.sresss/ v267 http://oaannnaaaaam. html.
12

---

[HB91]
Gabor T. Herman and Carolyn A. Bucholtz. Chape-based interpolation using chamfer distance. In Alan C. F. Colchester and David J. Hawkes, editors, Information Processing in Medical Imaging, 12th International Conference, IPM1'9, volume 511 of Lecture Notes Computer Science, pages 314-325. Springer, 1991. URL: htt.:ttts:://ao org/
10. 1007 (007/BPb0033762, doi: 10. 1007 1 /BFB003362..
[HHT+23] Shreyas Hampali, Tomas Hodan, Luan Tran, Lingni Ma, Cem Keskin, and Vincent Lepetit. In-hand 3d object scanning from RGB sequence. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023, pages 17079-17088. IEEE, 2023. doi: 10. 1119//VPR52229..... 2023. 01638.
(HK20)
Monika Henzinger and Sagar Kale. Fully-dynamic coresets. 2020. URL: attps://don http://doo..o/o.oo/ wttp//.././//./..././ 4230/LIPICs. E 2020. 57, doi:10.4230 LIPICS ESA. 2020.57.
173:57:1-57:21,
[HSS+24]
Linus Härenstam--Nelsen Lu Sang, Abhishek Saroha, Nikita Araslanov, and Daniel Cremers. Diffed: A symmetric differentiable chamfer distance for neural implicit surface fitting. In Ales Leonardis, Elisa Ricci, Stefan Roth, Olga Russakovsky, Torsten Sattler, and Gül Varol, editors, Computer Vision ECCV 2024 18th European Conference, Proceedings, Part LXXIII, volume 15131 of Lecture Notes in Computer Science, pages 432 042.447.550 Springer, 2024. doi: : 10. 100700007999
[JDS11]
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1):111712))) 2011. doi: 10. 10.1109/TPAMI 2010.57.
[JSQU18]
Li Jiang, Shaoshuai Shi, Xiaojuan Qi, and Jiaya Jia. GAL: geometric adversarial loss for single-view 3d-object reconstruction. In Vittorio Ferrari, Martial Hebert, Cristian Sminchisescu, and Yair Weiss, editors, Computer Vision ECCV 2018 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings. Part VIII, volume 1212 of Lecture Notes in Computer Science, pages 820- 0044834. Springer, 2018. doi: 10. 30007/978-3-3305 01000-112377311
[KSKW15] Matt J. Kusner, Yu Sun, Nicholas I. Kolkin, and Kilian Q. Weinberger. From word embeddings document distances. In Francis R. Bach and David M. Blei, editors, 32nd International Conference on Machine Learning (ICML), volume 37 of JMLR Workshop and Conference Proceedings, pages 957-966. JMLR.org, 2015. URL: http: / //proceedings.eo .mlr mlr, press/ /v3/ /tt//uuuuerb55 html.
[LHG+24] Jakub Lacki, Bernhard Haeupler, Christoph Grunau, Rajesh Jayaram, and Václav Rozhon. Fully dynamic consistent k-center clustering. In David P. Woodruff, editor, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3463-3484. SIAM,
2024. doi: 10.
124.
[LJG05]
Wei Liang, Yunde Jia, and Cheng Ge. Visual hand tracking using nonparametric sequential belief propagation. In De-Shuang Huang, Xiao-Ping (Steven) Zhang, and Guang-Bin Huang, editors, Advances in Intelligent Computing, International Conference on Intelligent Compusing, ICIC 2005, Proceedings, Part I, volume 3644 of Lecture Notes in Computer Science pages 679-687. Springer, 2005. doi: 100:0000077 / 1 15380599_77
[L]Z*24] Fangzhou Lin, Haotian Liu, Haoying Zhou. Songlin Hou, Kazunori D. Yamada, Gre- gory S. Fischer, Yanhua Li, Haichong K. Zhang, and Ziming Zhang. Loss distillation via gradient matching for point cloud completion with weighted chamfer distance. In JEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2024, pages 511-518 IEEE, 2024. doi: 10. 1109 II//S800S559222 2024. 10801828.
[LYH+23] Fangzhou Lin, Yun Yue, Songlin Hou, Xuechu Yu, Yajun Xu, Kazunori D. Yamada, and Ziming Zhang. Hyperbolic chamfer distance for point cloud completion. In IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, October 1-6, 2023, pages 14549-14560. IEEE, 2023. doi:10 1109/ IIC/V1CCVV.0 2023..0342 01342.
[Mat13]
Jin Matoušek. Lecture notes on metric embeddings. Technical report, Technical report, ETH Zürich, 2013.
[MDJT14]
M Mathews, J Deepa, Tonu James, and Shari Thomas. Segmentation of head from ultrasound fetal image using chamfer matching and hough transform based approaches. Int. J. Eng. Res. Technol, 365):1065- 2014.
13

---

[RLT 20]
Martin Rünz, Kejie Li, Meng Tang, Lingni Ma, Chen Kong, Tanner Schmidt, Ian Reid, Lourdes Agapito, Julian Straub. Steven Lovegrove, and Richard A. Newcombe. Frodo: From detections to 3d objects. In 2020 IEEF/CVF Con- ference on Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, 2020, pages 14708-14717. Computer Vision Foundation / IEEE, 2020. URL: https:/ /otpacc//ppeeccesss... thecvf. com/ content_CVPE. CVVR__020/htmll Runz Brrrz_FroO...o From Fwwm_ Detections _o_3D_________ 1t__3__0bbp wtt__oojeet_eeeeee 2020 paper.pp..... html, doi: 10. 1099/19///0 CC/p/22PP200.//// 2020.01473.
[TMPF22]
Michal J. Tyszkiewicz, Kevis-Kokits, Maninis, Stefan Popov, and Vittorio Ferrari. Raytran: 3d pose estimation and shape reconstruction of multiple objects from videos with ray-traced transformers.
Shai Avidan, Gabriel Brostow, Moustapha Cissé, Giovanni Maria Farinella, and Tal Hassner, editors, Computer Vision ECCV 2022 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part X, volume 13670 of Lecture Notes in Computer Science, pages 21 1 1-228. Springer, 2022. :01:10.. 1007
00000001100009990 __
[VHK94]
Marcel Van Herk and Hanne M Kooy. Automatic three-dimensional correlation of ct-ct, ct-mri, and ct-spect using chamfer matching, Medical physics, 2137):163--1178, 1994.
[WCL+19] Ziyu Wan, Dongdong Chen, Yan Li, Xingguang Yan, Junge Zhang, Yizhou Yu, and Jing Liao. Transductive zero-shot learning with visual structure constraint, In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Bue, Emily B. Fox, and Roman Garnett, editors, 32nd Conference Neural Information Processing Sys- tems (NeurIPS), pages 9972-9982, 2019. URL: httpap/e/.../aaaaeaaaaaaaaeeeeee
neurri Abstract. html.
[Wil18] Virginia Vassilevska Williams. On some fine-grained questions in algorithms and com- plexity. In Proceedings of the international congress of mathematiciaan:: Rio de janeiro 2018. pages 3447-3487. World Scientific, 2018. doi: 144:10..112/977881127788888 0188.
[WPZ*21] Tong Wu, Liang Pan, Junzhe Zhang, Tai Wang. Ziwei Liu, and Dahua Lin. Density- aware chamfer distance comprehensive metric for point cloud completion. volume abs/2111.12702, 2021.
URL: https //arxiv. owwooogg//.....ooooo..oo.oo abb//1bs/11111 12702, 2r1iv:2111
12702.
[XRV17]
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion Fashion-mnist: novel image dataset for benchmarking machine learning algorithms, 2017. URL: http: oow.orgg///................ gagb/bs//// 1708. 07747, arXiv: 07747.
14

---

A Our Algorithms for the le Norm
[Mat13] has shown the following useful lemma (which we state in the dynamic setting):
Lemma A.1. There a dynamic algorithm which for n points A C IRd undergoing insertions and deletions in O(d/e²) worst-case update time maintains A C ROld(²) such that || All1ı s
||.4- - A, la - || AfI1: (1 (1+6) ()+ for all i E [n]] with high (1 - 1/ poly(n)) probability.
That is, we may embed the input points into the Old/²2) space such that distances between the embedded points roughly correspond to & distances between the input points. Substituting the embedded point set into Theorem 1.1, and using the state of the art dynamic nearest neighbor data structures of [AMN** 98, AR15J, we obtain the following algorithms for the lg norm.
For = ((1) and 0 < <<< 1, there exists an algorithm which, with high probability, maintains (1 + -aapproximation to the Chamfer distance between A, B R |A], [B] - n with respect to the l norm, as A and B undergo point insertions and deletions, in Ō(e-O(d/e)) worst-case update time.
There exists a dynamic algorithm which maintains an O((-))))))))))) -ap''-pppoooiiattionn for c < the Chamfer distance between A, B R. |A], [ S n with respect the & norm, as and B undergo point insertions and deletions, O(d n² e . B) worst-case update time.
B Deferred Proofs
B.1 Linear Recourse for Maintaining Assignments
Lemma B.1. Any dynamic algorithm that maintains an a-approximate assignment between A and B must have at least ((n) recourse, and thus also MM()) update time.
Proof. Consider an instance where points of A are in close proximity to each other, and B contains two points, one at distance 1 from A and the other at distance M(a). Any a-approximate assignment of this instance must assign the majority of points in A the closer point in B. the closer point of B is removed from the input, then any assignment must assign all points of A to the single remaining point in B, leading the claimed recourse. fact, for any constant 6 > O, [BIJ+2] show that even in the static setting, reporting a (1 + appproxiiee mapping still requires 2 time under the hitting set conjecture [Wil18].
Li
B.2 Proof of Claim 3.4
We will first prove some useful properties of the underlying quad-tree data structure, which are based on the random shift of the points introduced at initialization. Our proof is analogous to similar separation lemma [BI]+23], and we include it here for sake of completeness.
Namely, let x, y E A B and e be some node of T. Then, with respect to the random shift defined by E [0, U7d, have:
1. Pr(y & Colæ E Co) S ||z-v I(())
2. Pr(y E Colæ E C.] S exp(
|-- L(v)
The random shift introduced at the initialization of our algorithm can be described follows: the algorithm draws a uniform random point z with coordinates 21, in [U]d. Then the algorithm defines sets A : {a + z/a E A} and B = (b + z|b E B}.
Fix some cell C, [vi, 0n + L(v)] x ... x [wa, e2 + L(v)] (we disregard the case where a shifted point falls exactly on the grid, as it occurs with 0 probability). If point E A U B with coordinates T1,..., Rea falls in cell C., we know that 2; E [at - Vi, N; e2 + T.())) for all E [d]. we condition on this event, then know that 2 is uniformly distributed on this interval.
15

---

Fix some y E A U B with coordinates V1...., yd- Conditioning on the event that x E Cv, the event y & C. for all i [d] if 2, [z+ - Ui 24 v; + L(v)], & [y: v/ Vi v; + L(v)] that is [eq > T(v) or 2; E [x: Vi, my] or zj E [y; 0 + [(e), H; 02 [(x)] (depending on
which Ti, Yı larger) which happens with probability most b Vel/ L(v). Hence, by union bounding over these events:
1/ 8/1
Prly & Color E C.)
L(u)
L(u)
Now observe that the above argument holds for all coordinates of independently. This implies:
De - Vil L(v)
- exp( | )
Pr(y E Colax E C.) S II 1=1
L(u)
We are ready to prove the claim. Fix some E A. If L(va)= < distch(a, B) 1/(4 (4-41ggg)) n). that implies that for some U/2 I distcu(a, (3 log there exists a B such that both a and belong to the same cell the tree T with side length U U/2 Let Cho ..... C² be the cells of with side length at most U/2 that a belongs to. Recall that this means & S L. By property (ii), we know that for all E B:
laa b/1
Σ Pr
Σ exp
2
iE k)
()
||a
b/12
S exp
2
distcH B)
< C exp exp
2
< C- exp( 33llogn))
S 1/n2
By union bounding over all b E B and a E A, and observing that these inequalities hold regardless which cells falls in specific levels of the tree, get that the first item holds with high 1 1-1/ 1/ 1//ooy(() probability for all E A.
To prove point (ii), fix some E A and 6 = argmin blll- Let Ci ,i...., Co be the cells of with ....., size lengths at least distch(a, (a, B) containing where C₁ has side length U/2 If L(v.) > U/2 then b & CĄ Hence, by property (i) we have that Pr(L(v,) 2 U/2'-1] S Pr(b & C a E Cd <
2 ||a bll1/U. Note that L(va) I L(C)) by definition. Hence, summing over the L levels of the tree we get:
U Σ Pr[L(v,) 2 2-11 L(C))
E[L(va)] <
()......)
U
Σ
Pr(b & C.
a E
Ci]
2-11
(Ho.....))
2 |aa
bll
U
Σ
U
2
(io.....))
Σ
2 I|a -bl1
(Da.....))
< 2 C. distcH (a, B)
Note that the second inequality holds as it does not matter which cells a falls on different levels of the tree for the set of preceding inequalities.
16

---

B.3 Proof of Claim 3.5
Fix point A, and let X be the event when is sampled in Algorithm 2. Let Va: Uyy.... be the path on tree starting at aaa ending at the leaf i containing a (hence " (vi) = 1). First, denote by Y the event when TREE-SAMPLER (T) returns node Va. and by X, the event that NODE-SAMPLER in line 4 of Algorithm choose the node tú on level i of T, for 1 < i s t. By definition, we have that 1(va)-((va) Further,
Pr[Y] Ever L(v))(())
vo(w2)
7A(12)
Pr[X2|Y]
Euwec((o)) w(u)
7(va)
by definition of wn.)) Similarly, for sisl
w(1b))
7a(e))
Pr|X E 1u w(u)
7A (1(1)=1)
Finally, we have that
P = X2. XX]
Pr[Y] 21(12)
7a(1))
7(v)
7/ (v:-1)
-r[[Y] (a(1)
7(va)
L(va)
Σ Ever [(v) -7(0)
B.4 Proof of Lemma 2.3
The data structure maintains a balanced binary tree of the elements of A, where each leaf corresponds to some element. In addition, each node of the binary search tree keeps track of the sum of the weights of the elements corresponding to the leaves in its sub-tree.
On query, the data-structure draws random real value in [0, Ei= wi}. Starting from the root of the search tree, completes a walk to a leaf. When deciding between child nodes v and u (from left to right) with leaf weight sums Way Wa in step of the walk, it chooses if x I Wa. Once reaching leaf, it returns the element assigned to it.
Observe that if the ordering of the leafs from left to right is a1,... Onn then this process chooses element a, x > Ejes Wi and S Ejsi W/s that is with probability w./ Ejen) W/. As the tree will have depth at most O(log n), the query takes Ollog n) time. The maintenance of a balanced binary tree of elements in O(log n) is folklore.
B.5 Proof Claim 3.6
First, note that when we decide to query the distance of some a A from B, a (a + e/4)- approximate nearest neighbor data structure, which might be randomized. Hence, instead of returning distch (a, B), we obtain some Z. distch (a, B), where Z, is random variable taking real values in [1,1 + a/4 e/4]. Note that this implies that E|Z2] < (1 a/4 + 2/42 < 2a?. Also, note that the randomization of Zul la E A is independent from the randomization of the rest of the algorithm (i.e. the randomness used for sampling elements of A and that of H). Furthermore, the randomness we use to sample a E is independent of the randomness of the quad-tree (that of ((w,)) and (v) values).
17

---

Var[X] - {[
L(va)
Ever Quer>(u). I(()))
Σ E
[B|z]] distch B)²
Σ VET (1v) (7())
[(v)?
A
Ever 7(0) -(()) distch B)]
Σ 4EA
IR
B[Za] diston B)
I(va)
(()) [(v)] Σ
logn distcH(a, B) 6a
vET
aEA
< log L (Astcn(A, B)² 12a²
The second inequality holds due to Claim 3.4, part (i), with high (1 1/ poly(n)) probability. The last inequality follows from the same claim, part (ii).
B.6 Proof of Lemma 3.2
query, the algorithm returns the value of random variable j/(m- (1 + e/2)). First, in order for this to be a (1 + a + apappooxiintio to distch( (A, B), by definition it must hold that
S distcH(A,B)) S á c/2)
(1 ax+++)))
(I)
(1 c/2)
Let X be a random variable described by Claim 3.6, that is a random variable taking value with probability T(va)/ (v) L(v). By the defini- tion of the nearest neighbor oracle we have that (istcH(A, + a/4) S B[X] S distcH(A, B).
NN(a, (1/4)-Ever (
Since a is the average of m i.idd copies of X, then Var[ä/m] I Var[X]/m and hence
log n 240 a²
distcH (A, B) 2.). . 20 max (a
Varlū/m] < Var[X]
(2)
with high probability by Claim 3.6. Now, by simple application Chebyshev's inequality we have
Pr
Var
16
Since by linearity of expectation it holds that distch (A, B1 + a/4) S 2 < distcu (A, B),
we have
j >
dist distch(A,BB B)
1
Pr
distcH (A, +
Var
Pr
4
Var
S
m
m
m
+ a/4
m
16'
Plugging in (2), obtain
# (A,tc
c dist (A, B)
i distcH((,))
c distcc B)
1
Pr
+ Pr
m
V5 max (a, 1}
a/4
V5 max (a, 1]
16
For all 0 and 0 <<< 1 this implies that:
# m c1+)/2) > cHst B) + Pr
< distcn(AA B) ((+a+e)
$ 16
1
(1+c/2)
Therefore, the output of the query is a (1 + a)- distcu(A, B) with 15/16 3/4 probability.
18

---

C Pseudo-code of Our Algorithm
In this section, we give pseudo-codes for the dynamic algorithm described in Section 3.
The updates to ( (b) and (z(()) in the last line of each algorithm can be done using standard results from literature (see e.g. [dBHTT07]). The following pseudo-code shows how the algorithm updates y values after point æ is inserted into/deleted from A U B.
Algorithm 1 UPDATE (OINT(
1: 01 < leaf containing
2: II f path (U1, u............................... from 81 to root r in T
3: Ui..... Ei < V E 1I[C, n (B x) =
4: v' < ancestor of 0g T
5: if Insertion into A then
6:
+ 7: end if
8: if Deletion from A then
9:
>(0') 7(1)
10: end if
11: if Insertion into B then
12:
T(0') t -11))- 7A (vb)
7(v1) 7A(
14:
for 7(U:) - (A(() - i
end if
16: if
Deletion from B then
y(v)) + ((1) Eieny ((1))
18:
7(1)) t for E [M]
19: end if
The algorithm also updates the global sampler NODE-SAMPLER(7) and affected TREE- SAMPLER(U)s such that after an update:
contains all nodes v E T with weight w(v) L(v) 7(0) (if non-
negative),
NODE- (AMPLER(1) for all E T contains all children u of v with weight (a(u) if C
Note that EVeT 7(0) = |A| S hence TREE-SAMPLER(7) contains at most n elements all times. Similarly, for any T for the set of child nodes U of T' holds that Σnev (u < |A| hence all
also contain at most n elements (and hence updates and answers queries in Olog n)) time by Lemma 2.3).
The following pseudo-codes describes how queries are handled by the algorithm of Section 3.1.2. For single query, we invoke Algorithm 4.
Algorithm 2 SAMPLER ( (A) procedure
1: Sample vertex of I using SAMEL-R)
2: Return SAMPLER-FIND(1)
Algorithm 3 SAMPLER-FINDIA procedure
1: if is a leaf of quad-tree tree 7' then
2: return a contained
3: else
4: Sample child using NODE-SAMPLER(1 (v)
5: CAMPLER-FINDD(I1
6: end if'
19

---

Algorithm 4 QUERY-CHAMFRR A, o)) procedure
1: ji 0
2: m 120- 1 max(a" o²
m 0
log n-max (a
3: for to m do
4: a < SAMPLER
5: Ia NN(a, B, 0.444 Eoer L(v) 1(va))
6: === ja 3i
7:
end for
8: Return m1-1++/2)
D Missing Figures in Section 4
In this section we give the missing Figures 4 and 5.
1.5
Probability
0.5
0.0
0.2
0.4
0.6
0.8
1.0
Index
1e6
Figure 4: The value dist(a, B)/ EN'E E dist(a', B) over all points a e A for SIFT dataset, which the "ideal" probabilities for importance sampling.
0.218
Ours
Text Embedding
outlier
00.627
Benchmark
Uniform
0.011
Datasets
ShapeNet
0.014
0.001
1.098
65.123
outlier
3.014
118.640
with outlier
10
10-2
10-1
100
101
10²
Running Time (ms)
Figure 5: Average running time per window update for algorithms on datasets with outliers.
E Additional Experiments
Table 2: Experiment parameters when both A and B are dynamic.
dataset
window size
sample size
Text Embedding
1.5k
100
ShapeNet
1.5k
100
Pashion-MNIS"
3.5k
100
SIFT
50k
500
To evaluate the case when both A and B are dynamic, we simulate the dynamic updates via sliding window, similar to the default setting where only B is dynamic. However, the main difference is
20

---

Text Embedding
0.25
Unifomm
Reletive End
0.20
0.15
0.10
0.05
0.00
1600
1800
2000
2200
2400
2600
2800
3000
Shapefint
Uniform
Relative BroP
0.20
0.15
0.10
0.05
0.00
2000
2500
3000
3500
4000
Steps Fashion MNIST
0.06
Ours
0.05
Relative Erer
0.04
0.02
0.01
0.00
Steps SIFT
0.07
Ours Uniform
0.06
Relative Enor
0.05
0.04
0.03
0.02
0.01
0.00
0.2
0.4
0.6
Figure 6: Relative
when both A and B dynamic, with the setup in Figure 1.
that the window not only consists of insertions of points in B. but also those in A. Specifically, we insert alternatively between A and B in proportion their dataset sizes (e.g., for MNIST dataset, |A]: : |B] = 6 1, we perform six insertions from A followed by one from B). Experiment parameters for this case are summarized in Table 2. depict the relative error curve in Figure 6 and report average running time sliding window update in Figure 7.
21

---

Text Embedding
0.3375
Benchmark
0.275
Uniform
0.009
Datasets
ShapeNet 0.002
0.006
1.110
MNIST
4.520
0.234
4.018
SIFT
14.556
0.176
10-3
101
Running Time (ms)
Figure 7: Average running time per window update for all algorithms when both A and B are dynamic.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes, the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope, encompassing both theoretical guarantees and practical results.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The paper discusses theoretical run-time bounds for the proposed algorithm. Additionally, the paper provides a comprehensible comparison with the "Benchmark" and "Uniform" baseline algorithms. The results highlight the limitations of our technique on the SIFT dataset, where our algorithm performs slightly worse than the "Uniform" benchmark, likely due to the highly uniform nature of the SIFT data.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
22

---

The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: All theoretical claims provide the full set of assumptions and are supported by detailed proofs, either presented the main body of the paper or outlined through concise sketches, with full proofs deferred to the appendices.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Yes, the paper fully discloses all the information necessary reproduce the main experimental results relevant to its claims and conclusions. The code included as part of the supplementary material, and all datasets used in the experiments are publicly available online.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same
23

---

dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-sonnee open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The supplementary material includes clear instructions and all necessary resources, including open access to the datasets and code.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.c cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nips. wccppbblc/gguieeeoococeeoocoepce http//uides/eee// http:/uddde//oeSuuuiiiiiiiin
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
24

---

The paper specifies all relevant training and testing details. Additionally, it provides comprehensive of experimental plots that support and illustrate the theoretical guarantees of the algorithm.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The plots present clear relative bounds that effectively convey the variability and statistical significance of the experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by enror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments were conducted the same machine, with its specifications clearly stated in the paper
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
25

---

9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: http::///eeupppppp http.c//ppbcceeeiiiccciiiiiiiiia
Answer: [Yes]
Justification:
The research adheres fully to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper does not explicitly discuss societal impacts, but the nature of the work does not suggest any apparent negative societal implications.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (c.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
26

---

Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We added references to the datasets we use. We do not use any external library in the code.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is available online, the authors encouraged to reach out the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes)
Justification: Yes, the code provided as supplementary material and well documented. Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mmoel part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing. editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the method development in this research does involve L.MMs as any important, original, or non-standard components.
Please refer to our LLM policy (https : //tpur/eesp../eeeee cc/ /oe//ooorencce//225//////// for what should or should not be described.
28


Reviews:
[{"review_id": "8POFCxhF6t", "reviewer": "Reviewer_v6v4", "summary": "This paper presents the first dynamic algorithm for maintaining approximations of the Chamfer distance between two evolving point sets A and B under L1 and L2 norms, achieving $(1+\\epsilon)$-approximation in $\\widetilde{O}(\\epsilon^{-d})$ update time for low dimensions, and $O({1}/{\\epsilon})$-approximation in $\\widetilde{O}\\left(dn^{\\epsilon^2}\\epsilon^{-4}\\right)$ update time for high dimensions. The authors address a fundamental gap in computational geometry by developing a data structure that can efficiently handle point insertions and deletions while maintaining distance approximations with provable guarantees.", "questions": "- What is the total memory overhead of the quad-tree structure and multiple dynamic samplers compared to storing the point sets explicitly?\n- Can you provide experiments where both sets A and B undergo frequent updates to demonstrate the complete dynamic capabilities?\n- Given that symmetric Chamfer distance is more common in practice, how efficiently could your approach compute                                      $dist_{CH}(A,B) + dist_{CH}(B,A)$  and would this require maintaining two separate data structures?\n- The paper motivates the work with applications like point cloud completion and medical imaging - can you provide experiments on these actual use-cases to demonstrate practical relevance beyond generic benchmark datasets?", "limitations": "While the authors discuss some theoretical limitations, they should better address practical concerns including memory overhead of maintaining multiple dynamic samplers and quad-tree structures. Additionally, the paper lacks analysis of algorithm sensitivity to the bounded aspect ratio assumption, or worst-case point distributions that might cause the importance sampling to degrade significantly. A brief Limitations section addressing these scalability and practical deployment challenges would strengthen the paper's contribution.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n- The paper addresses a genuine gap in dynamic computational geometry - no prior work existed for dynamic Chamfer distance. The problem is well motivated with several example use-cases and the need for a faster alternative to EMD.\n- Rigorous theoretical analysis - detailed proofs for approximation guarantees, time complexity, and correctness has been provided. Clever reduction to well-studied ANN data structures, allowing the algoritjm to inherit existing performance guarantees.\n- Sophisticated sampling scheme that samples cells proportionally to their size and point count, leading to provably good approximations. Well-designed integration of multiple dynamic samplers (TREE-SAMPLER and NODE-SAMPLER) with efficient maintenance procedures.\n\n**Weaknesses**\n- The paper uses the asymmetric definition of Chamfer distance, while the symmetric version is more commonly seen in practice. The authors should better emphasise this choice and discuss its implications for applications.\n- Experiments focus primarily on dynamic B with static A, not fully demonstrating the algorithm's dynamic capabilities on both sets.\n- There are some restrictive assumptions like bounded aspect ratio poly(n) and points in $[U]^d$, which may not hold in real applications with arbitrary point cloud data.\n- The algorithm suffers from exponential dependence $\\epsilon^{-d}$ in low dimensions, while high-dimensional guarantees only provide weak $O(1/\\epsilon)$-approximation, possibly limiting practical applicability for moderate dimensions.", "was_revised": true, "final_justification": "I am satisfied with the authors' response and would recommend Accept.", "rebuttal": "We thank the reviewer for insightful comments. We start with presenting some new experiment results, and then we address other comments.\n\n## New Experiments\n\n> The paper motivates the work with applications like point cloud completion and medical imaging - can you provide experiments on these actual use-cases? Experiments focus primarily on dynamic B with static A. \n\nWe address these comments in the following aspects: \n- We add a new dataset called ShapeNet, which consists of 3D point clouds, to better justify our motivation about point cloud. We also tried to look for medical imaging datasets, but we did not find publicly available datasets suitable for our experiments.\n- We let $A$ undergo dynamic updates besides having a dynamic point set $B$, in all our error and running time evaluations.\n\nHere we report preliminary experiment results only on the new dataset ShapeNet and an existing one Fashion-MNIST. We will expand to run on the other datasets, and add the results in the next version of the paper. In our experiments, both $A$ and $B$ evolve within a sliding window, where points from $A$ and $B$ are alternately inserted. The specifications and parameters of these two datasets are summarized below.\n\n| dataset       | dimension $d$ | $\\|A\\|$ | $\\|B\\|$ | window size | sample size |\n| ------------- | ------------- | ------- | ------- | ----------- | ----------- |\n| Fashion-MNIST | 784           | 60000   | 10000   | 3500        | 100         |\n| ShapeNet      | 3             | 2048    | 2048    | 1500        | 100         |\n\n\nThe detailed error and running time result can be found below. We can see that both the error and running time results exibit a similar behavior as in our current experiments in the manuscript: we achieve a comparable/slightly better error (which is relative to a brute-force benchmark) compared with the uniform sampling baseline, and we achieve a speedup compared with the brute-force benchmark. \n\nWe note that due to the small size of ShapeNet, our more complicated data structure may lead to a slightly worse performance than the simple brute-force, but the speedup in larger datasets remains significant.\n\n### Detailed Results: Error\nWe report the min, max and average relative error for both our algorithm and the uniform baseline, evaluated for the ShapeNet dataset as follows. Due to the space limit, we only report the result for ten evenly picked time steps over the entire process.\n\n|   step |   our_err_max |   our_err_min |   our_err_avg |   uni_err_max |   uni_err_min |   uni_err_avg |\n|--------|---------------|---------------|---------------|---------------|---------------|---------------|\n|   1638 |      0.089081 |      0.002748 |      0.039075 |      0.224242 |      0.02824  |      0.094302 |\n|   1911 |      0.025965 |      0.006845 |      0.014477 |      0.127802 |      0.013832 |      0.061511 |\n|   2184 |      0.10265  |      0.002022 |      0.038719 |      0.190679 |      0.033378 |      0.095957 |\n|   2457 |      0.036942 |      0.000126 |      0.011609 |      0.140769 |      0.014554 |      0.075501 |\n|   2730 |      0.061071 |      0.011159 |      0.024967 |      0.303421 |      0.055861 |      0.136652 |\n|   3003 |      0.05533  |      0.009615 |      0.026081 |      0.157239 |      0.010693 |      0.079922 |\n|   3276 |      0.101199 |      0.001433 |      0.030674 |      0.160321 |      0.038384 |      0.097889 |\n|   3549 |      0.048694 |      0.002294 |      0.015526 |      0.045202 |      0.012967 |      0.027885 |\n|   3822 |      0.09417  |      0.011482 |      0.046436 |      0.090955 |      0.012316 |      0.055232 |\n|   4095 |      0.022748 |      0.000265 |      0.008279 |      0.115665 |      0.011511 |      0.061347 |\n\nError evaluation for Fashion-MNIST dataset:\n\n|   step |   our_err_max |   our_err_min |   our_err_avg |   uni_err_max |   uni_err_min |   uni_err_avg |\n|--------|---------------|---------------|---------------|---------------|---------------|---------------|\n|   7000 |      0.017379 |      0.000587 |      0.008961 |      0.035783 |      0.006126 |      0.021922 |\n|  14000 |      0.102088 |      0.00783  |      0.053603 |      0.05268  |      0.008025 |      0.032996 |\n|  21000 |      0.027711 |      0.005504 |      0.013561 |      0.0638   |      0.011997 |      0.030353 |\n|  28000 |      0.040468 |      0.000548 |      0.020453 |      0.042721 |      0.009207 |      0.026044 |\n|  35000 |      0.04584  |      0.00178  |      0.024478 |      0.046525 |      0.008337 |      0.030551 |\n|  42000 |      0.056667 |      0.003062 |      0.03221  |      0.062291 |      0.01514  |      0.029729 |\n|  49000 |      0.054735 |      0.003067 |      0.026688 |      0.035132 |      0.007734 |      0.019372 |\n|  56000 |      0.080342 |      0.013182 |      0.040157 |      0.035516 |      0.000867 |      0.015012 |\n|  63000 |      0.054645 |      0.010068 |      0.026413 |      0.067964 |      0.016561 |      0.040617 |\n|  70000 |      0.07546  |      0.019382 |      0.043388 |      0.038847 |      0.004134 |      0.023396 |\n\n\n### Detailed Results: Running Time\n\nWe report the average update and query time per step, as well as the total running time over the entire run. The running time results on Fashion-MNIST dataset are as follows:\n\n|| Ours | Uniform | Brute-force |\n|-----------| -------- | -------- | -------- |\n|Average update time   | 0.1368 ms      | 0.000242 ms   | 0.6973 ms       |\n|Average query time    | 18.0278 ms     | 16.2884 ms    | 0.000019 ms     |\n|Total time            | 9757.672 ms    | 179.855540 ms | 48813.260192 ms |\n\nThe running time results on ShapeNet dataset are as follows: \n\n|| Ours | Uniform | Brute-force |\n|-----------| -------- | -------- | -------- |\n|Average update time   | 0.0041 ms    | 0.000078 ms  | 0.0033 ms     |\n|Average query time    | 0.106 ms     | 0.063 ms     | 0.00002 ms    |\n|Total time            | 18.028888 ms | 0.945685 ms  | 13.443101 ms  |\n\n## Other comments\n\n> Given that symmetric Chamfer distance is more common in practice, how efficiently could your approach compute $dist_{CH}(A, B) + dist_{CH}(B, A)$ and would this require maintaining two separate data structures?\n\nOur results can readily be applied in a black-box manner to handle the symmetric case. Specifically, we can maintain $dist_{CH}(A,B) + dist_{CH}(B,A)$ by using two copies of the data structure with swapped $A$ and $B$. This has at most twice the overhead.\n\nIn fact, we can even do better than this: by using a single quad-tree shared between both data structures and maintaining two separate dynamic ANN instances, we maintain the symmetric Chamfer distance using only one copy of data structure.\n\n> There are some restrictive assumptions like bounded aspect ratio poly(n) and points in $[U]^d$, which may not hold in real applications with arbitrary point cloud data.\n\nThis assumption is only for the sake of presentation, and our results work without it, since our algorithm is oblivious to the aspect ratio $\\phi$. Then, this $\\phi$ only appears in the analysis where we show that the update time is $\\mathrm{poly}(\\log \\phi)$ (this holds even if we do not know $\\phi$ in advance). \n\nAs we are aiming for a dynamic algorithm with poly-logarithmic update time dependence on $n$, the assumption that $\\phi = \\text{poly(n)}$ is natural and saves the complication of writing $\\phi$ in the result.\n\nFinally, we note that the polylogarithmic dependence on the aspect ratio $\\phi$ is not avoidable, because for a point set with aspect ratio $\\phi$, their representation can be of $\\Omega(\\log \\phi)$ bits. Hence, just reading the updates already necessitates an update time which is poly-logarithmic with respect to $\\phi$, making our dependence near-optimal. \n\n> The algorithm suffers from exponential dependence $\\epsilon^{-d}$ in low dimensions, while high-dimensional guarantees only provide weak O(1/\\epsilon)-approximation, possibly limiting practical applicability for moderate dimensions.\n\nSince our algorithm reduces to ANN with minimal overhead, the resulting running-time guarantees asymptotically match the best-known bounds for static ANN. Here, the mentioned $\\epsilon^{-d}$ and $O(1 / \\epsilon)$ bounds are known ANN bounds for typical low and high dimension regimes, but of course, there might be more suitable bounds for other dimension regimes, such as the \"moderate\" dimensions which you mentioned.\n\nIn fact, when $d = \\sqrt{\\log n}$ which may be considered moderate dimension, the $\\epsilon^{-d}$ bound is already useful since $2^d = 2^{O(\\sqrt{\\log n})}$ is sub-polynomial, and our algorithms still guarantee a $(1 + \\epsilon)$-approximation. \n\n> What is the total memory overhead?\n\nThe worst-case blowup is a $\\mathrm{poly}\\log$ factor. \n\nWe also examined the practical memory blowup in our experiments. We examined the run on the large-scale SIFT dataset, which has high dimensionality. We observed that loading the dataset alone used 564.6 MB of memory. Running all the algorithms, including our method, uniform, and the benchmark, raised to 4110.3 MB. This means our algorithm uses at most 6.28x the memory required to hold the dataset itself.\n\n> worst-case point distributions that might cause the importance sampling to degrade significantly. \n\nIf we interpret this question correctly, this seems to suggest that our importance sampling does not have a decent worst-case bound. \n\nThis may be a misconception, since we prove that our importance sampling always requires no more than poly-logarithmic number of samples to achieve the claimed error bound, regardless of the point distributions. This poly-logarithmic dependence is usually optimal for sampling methods to achieve high success probability.\n\n> A brief Limitations section addressing these scalability and practical deployment challenges would strengthen the paper's contribution.\n\nWe will include a discussion of the limitations and assumptions of our algorithm from a practical perspective in the next version of the paper."}, {"review_id": "5QE7b4hkeF", "reviewer": "Reviewer_jAgu", "summary": "The paper studies the problem of computing Chamfer distance in the fully dynamic setting, and evaluates the proposed method on real-world datasets and demonstrates that it performs competitively against natural baselines. Actually, I am not an expert in this field, so my comments are based on low confidence. If I make basic mistakes, I hope it will not influence the meta-review at the final decision stage.", "questions": "See the weaknesses part.", "limitations": "The authors adequately addressed the limitations.", "rating": 4, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe speedup of Chamfer Distance is very useful.\n2.\tThe experimental verification is relatively complete\n\nWeaknesses:\n\n1.\tIt is advised to present experiment results in some point cloud datasets such as ShapeNet because Chamfer Distance is widely used as loss function in point cloud processing.\n2.\tThe current approximation is one-sided (from A to B). Would the same dynamic framework support symmetric Chamfer distance efficiently?\n3.\tWhile runtime speedups are demonstrated, it would be helpful to understand the algorithm’s space complexity, especially for high-dimensional datasets.", "was_revised": true, "final_justification": "I thanks for the authors' response. I think this paper is solid and shows comprehensive experimental results. Considering I am not an expert in this field, I will maintain my original rating as borderline accept.", "rebuttal": "We thank the reviewer for insightful comments. We address the major comments as follows.\n\n> It is advised to present experiment results in some point cloud datasets, such as ShapeNet, because Chamfer Distance is widely used as a loss function in point cloud processing.\n\nTo address this question, we have conducted new experiments on the ShapeNet point cloud dataset. As suggested by other reviewers, we also added evaluations where both $A$ and $B$ are dynamic.\n\nHere we report preliminary experiment results only on the new dataset ShapeNet and an existing one Fashion-MNIST. We will expand to run on the other datasets, and add the results in the next version of the paper. In our experiments, both $A$ and $B$ evolve within a sliding window, where points from $A$ and $B$ are alternately inserted. The specifications and parameters of these two datasets are summarized below.\n\n| dataset       | dimension $d$ | $\\|A\\|$ | $\\|B\\|$ | window size | sample size |\n| ------------- | ------------- | ------- | ------- | ----------- | ----------- |\n| Fashion-MNIST | 784           | 60000   | 10000   | 3500        | 100         |\n| ShapeNet      | 3             | 2048    | 2048    | 1500        | 100         |\n\n\nThe detailed error and running time results can be found below. We can see that both the error and running time results exibit a similar behavior as in our current experiments in the manuscript: we achieve a comparable/slightly better error (which is relative to a brute-force benchmark) compared with the uniform sampling baseline, and we achieve a speedup compared with the brute-force benchmark. \n\nWe note that due to the small size of ShapeNet, our more complicated data structure may lead to a slightly worse performance than the simple brute-force, but the speedup in larger datasets remains significant.\n\n### Detailed Results: Error\nWe report the min, max and average relative error for both our algorithm and the uniform baseline, evaluated for the ShapeNet dataset as follows. Due to the space limit, we only report the result for ten evenly picked time steps over the entire process.\n\n|   step |   our_err_max |   our_err_min |   our_err_avg |   uni_err_max |   uni_err_min |   uni_err_avg |\n|--------|---------------|---------------|---------------|---------------|---------------|---------------|\n|   1638 |      0.089081 |      0.002748 |      0.039075 |      0.224242 |      0.02824  |      0.094302 |\n|   1911 |      0.025965 |      0.006845 |      0.014477 |      0.127802 |      0.013832 |      0.061511 |\n|   2184 |      0.10265  |      0.002022 |      0.038719 |      0.190679 |      0.033378 |      0.095957 |\n|   2457 |      0.036942 |      0.000126 |      0.011609 |      0.140769 |      0.014554 |      0.075501 |\n|   2730 |      0.061071 |      0.011159 |      0.024967 |      0.303421 |      0.055861 |      0.136652 |\n|   3003 |      0.05533  |      0.009615 |      0.026081 |      0.157239 |      0.010693 |      0.079922 |\n|   3276 |      0.101199 |      0.001433 |      0.030674 |      0.160321 |      0.038384 |      0.097889 |\n|   3549 |      0.048694 |      0.002294 |      0.015526 |      0.045202 |      0.012967 |      0.027885 |\n|   3822 |      0.09417  |      0.011482 |      0.046436 |      0.090955 |      0.012316 |      0.055232 |\n|   4095 |      0.022748 |      0.000265 |      0.008279 |      0.115665 |      0.011511 |      0.061347 |\n\nError evaluation for Fashion-MNIST dataset:\n\n|   step |   our_err_max |   our_err_min |   our_err_avg |   uni_err_max |   uni_err_min |   uni_err_avg |\n|--------|---------------|---------------|---------------|---------------|---------------|---------------|\n|   7000 |      0.017379 |      0.000587 |      0.008961 |      0.035783 |      0.006126 |      0.021922 |\n|  14000 |      0.102088 |      0.00783  |      0.053603 |      0.05268  |      0.008025 |      0.032996 |\n|  21000 |      0.027711 |      0.005504 |      0.013561 |      0.0638   |      0.011997 |      0.030353 |\n|  28000 |      0.040468 |      0.000548 |      0.020453 |      0.042721 |      0.009207 |      0.026044 |\n|  35000 |      0.04584  |      0.00178  |      0.024478 |      0.046525 |      0.008337 |      0.030551 |\n|  42000 |      0.056667 |      0.003062 |      0.03221  |      0.062291 |      0.01514  |      0.029729 |\n|  49000 |      0.054735 |      0.003067 |      0.026688 |      0.035132 |      0.007734 |      0.019372 |\n|  56000 |      0.080342 |      0.013182 |      0.040157 |      0.035516 |      0.000867 |      0.015012 |\n|  63000 |      0.054645 |      0.010068 |      0.026413 |      0.067964 |      0.016561 |      0.040617 |\n|  70000 |      0.07546  |      0.019382 |      0.043388 |      0.038847 |      0.004134 |      0.023396 |\n\n\n### Detailed Results: Running Time\n\nWe report the average update and query time per step, as well as the total running time over the entire run. The running time results on Fashion-MNIST dataset are as follows:\n\n|| Ours | Uniform | Brute-force |\n|-----------| -------- | -------- | -------- |\n|Average update time   | 0.1368 ms      | 0.000242 ms   | 0.6973 ms       |\n|Average query time    | 18.0278 ms     | 16.2884 ms    | 0.000019 ms     |\n|Total time            | 9757.672 ms    | 179.855540 ms | 48813.260192 ms |\n\nThe running time results on ShapeNet dataset are as follows: \n\n|| Ours | Uniform | Brute-force |\n|-----------| -------- | -------- | -------- |\n|Average update time   | 0.0041 ms    | 0.000078 ms  | 0.0033 ms     |\n|Average query time    | 0.106 ms     | 0.063 ms     | 0.00002 ms    |\n|Total time            | 18.028888 ms | 0.945685 ms  | 13.443101 ms  |\n\n> The current approximation is one-sided (from A to B). Would the same dynamic framework support symmetric Chamfer distance efficiently?\n\nOur results can readily be applied in a black-box manner to handle the symmetric case. Specifically, we can maintain $dist_{CH}(A,B) + dist_{CH}(B,A)$ by using two copies of the data structure with swapped $A$ and $B$. This has at most twice the overhead.\n\nIn fact, we can even do better than this: by using a single quad-tree shared between both data structures and maintaining two separate dynamic ANN instances, we maintain the symmetric Chamfer distance using only one copy of the data structure.\n\n> While runtime speedups are demonstrated, it would be helpful to understand the algorithm’s space complexity, especially for high-dimensional datasets.\n\nThe space complexity of the samplers of our algorithm is $O(n \\cdot \\text{poly}(\\log n))$. In addition, our algorithm requires the maintenance of a dynamic approximate nearest neighbour data structure on $n$ points, which requires $O(n)$ and $O(nd + n^{1+\\epsilon^2 + o(1)})$ space for low and high dimensions, respectively, using state-of-the-art results from literature."}, {"review_id": "PPHKA6orsW", "reviewer": "Reviewer_GBSz", "summary": "This paper studies the problem of fully dynamic Chamfer Distance approximation. The Chamfer Distance is a “distance” (quotes since not actually a metric) between two sets of points A,B in R^d. It is a well known relaxation of the Earth Mover Distance, which can be computed easily in quadratic time via a simple all-pairs brute force distance computation. This metric is also well studied in its own right in the computer vision and ML literature. The similarity version of Chamfer (where distances are replaced with dot product, which is essentially equivalent for normalized vectors), is also very important in information retrieval, especially for the training of multi-vector embedding models, where it is the measure by which two sets of embeddings are compared. Thus, algorithmic improvements for handling the Chamfer distance are quite important.\n\nThe current paper studies the maintenance of an approximation of the Chamfer distance in the fully dynamic setting, where points can be added and removed from both A and B. The main result is an algorithm with O(1/eps) approximation and n^{eps^2} update time (for any eps in (0,1)). In fact, their update time is the same as the query time of an approximate nearest neighbor (ANN) search data structure in (R^d, ell_2); if that runtime is tau, their algorithm has update time tau*poly(log n). This is a significant improvement over a naive tilde{O}(n) update time required to update all the mappings from points in A to nearest neighbors in B (for each point, one could store all their neighbors in B in sorted order, and update each sorted order after each insertion or deletion).\n\nNaively, the main result is very easy to obtain if B is fixed and only insertions or deletions are allowed to A: every time you insert a new point a to A, just run ANN and you are done. The hard part is when points are deleted or added to B, since this may change the nearest neighbors of O(n) points in A.\n\nRecently, Bakshi et. al. (NeurIPS 23’) showed that a (1+eps) approximation to the Chamfer distance can be obtained in roughly n*poly(1/eps) time using an importance sampling technique. First, rough approximate distances to B for each point a in A are obtained using a standard quadtree construction. Then, poly(1/eps)*log(n) points are sampling with probability proportional to these approximate distances. The true nearest neighbors for these points are then computed exactly via brute force. The current paper’s main contribution is a technique to implement this in a fully dynamic fashion. The main challenge is maintaining an algorithm that can dynamically sample from the distribution of approximate distances from A to B (when this distribution is changing). Once 1/eps points are sampled, one can just run ANN to get the approximate neighbors in B (giving the resulting ANN runtime guarantee). To solve the key challenge of maintaining a dynamic sampler, they show that they can implicitly sample from the distribution over A (without explicitly maintaining the weights) by keeping track of the count of points in A in each node in the quadtree that has no points in B. Since the highest node in the quadtree for which a point a in A collides with no other b in B determines its approximate distance (and therefore sampling probability), one can first sample a node from the quadtree (which has no B nodes in it) proportional to the number of nodes from A that are in it (and proportional to the 2^{level} of that node in the quadtree), and then sample a point uniformly from that node\n\nTechnically, this is a very clean idea, if perhaps somewhat straightforward. I’d venture to say that, if you asked someone who is an expert in ANN algorithms to solve this problem by making the algorithm of Bakshi et. al. dynamic, they probably would be able to do so without terrible difficulty. But hindsight is powerful (and the idea that making Bakshi et. al. dynamic is the right approach is non-trivial), thus the algorithm in this paper is quite interesting and important regardless. Moreover, it is quite practical, since the data structures are essentially no more complicated than the original quadtree data structure. It is also appealing because the final ANN algorithm can be implemented with any ANN algorithm in practice, such as HSNW / DiskANN, and does not need to be the theoretically optimal LSH based algorithms (that give the theoretical trade-offs). \n\nExperimentally, they outperform uniform sampling methods primarily on datasets where outliers are injected. This makes sense, since importance sampling is only different from uniform sampling when outliers exist. The fact that artificial injection of outliers was necessary is likely due to the choice of datasets; likely other datasets exist with outliers present, and it is clear that this technique is preferable for such datasets.\n\nOverall, this paper was very nicely written and enjoyable to read. The result is a strong theoretical advance for an important distance measure, and is likely to be useful in practice. Thus, I think this paper should be accepted.", "questions": "It would be good to see experiments on datasets that are naturally dynamic, perhaps one that has build in temporal data. This would allow for a more interesting ANN algorithm to be used which searching for the nearest neighbors.\n\nHow often do the samples changes from update to update? If the distribution does not change significantly, then perhaps it is possible to reuse most of the samples from the last step. The samples between consecutive updates are no longer independent, but this should not be a big issue. In theory, in the worst case, the distribution can totally change, thus you get no gain. In practice though, you may have big wins since the distribution may not change much on each step.\n\nAlso, you can imagine other optimizations, such as storing the k-NN for each point in A, and using the \"living\" points in that set to answer ANN queries for that point (instead of re-querying the ANN data structure for that point from scratch). It would be interesting to see how these methods improve runtime (note that this would probably improve the runtime of uniform sampling even more).", "limitations": "Yes", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 4, "strengths_and_weaknesses": "In Summary", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for insightful comments. We address the major comments as follows.\n\n> It would be good to see experiments on datasets that are naturally dynamic, perhaps one that has build in temporal data. This would allow for a more interesting ANN algorithm to be used which searching for the nearest neighbors.\n\n\nUnfortunately, we did not manage to find publicly available naturally dynamic datasets suitable for our experiments.\n\n> How often do the samples changes from update to update? If the distribution does not change significantly, then perhaps it is possible to reuse most of the samples from the last step. The samples between consecutive updates are no longer independent, but this should not be a big issue. In theory, in the worst case, the distribution can totally change, thus you get no gain. In practice though, you may have big wins since the distribution may not change much on each step.\n\nThis is an interesting suggestion. However, we tried to test this in the Fashion-MNIST dataset, and we find that the overlap of samples between two consecutive queries seems to be small, which is about 2 percent. Hence, at least for this dataset the suggested idea may not lead to significant improvement.\n\n> Also, you can imagine other optimizations, such as storing the k-NN for each point in A, and using the \"living\" points in that set to answer ANN queries for that point (instead of re-querying the ANN data structure for that point from scratch). It would be interesting to see how these methods improve runtime (note that this would probably improve the runtime of uniform sampling even more).\n\nUnfortunately, the recourse of a k-NN assingment for each point in $A$ can be $\\Omega(n)$ in the dynamic setting. In specific the $k$-NN assignment for $k=1$ is the same as the assignment describing the Chamfer distance which can not be efficiently maintained in the dynamic model."}, {"review_id": "VTvfH1ouxf", "reviewer": "Reviewer_ARp9", "summary": "This manuscript proposes a near-linear time approximated algorithm for estimating Chamfer Distance (CD) for two dynamic point sets $A$ and $B$. \n\nThe closest literature [BIJ+23] solves the static problem through approximating the closest distance from $a\\in A$ to $B$ with LSH and performing importance sampling for a bounded-variance estimation of CD. This paper follows this method and tackles the ‘linear-time update barrier’ when transferring to the dynamic setting, i.e., maintaining the $\\alpha$-approximate assignment from A to B costs $\\Omega(N)$ time even when only reporting the recourse (L70). \n\nThe authors bypass the challenge by proposing a dynamic sampler that no longer maintains the specific closest distances, but can yield samples $a\\in A$ obeying the desired distribution probability proportional to importance (i.e., closest distance from $a$ to $B$).", "questions": "1.\tHow does the algorithm perform on lower-dimensional datasets, such as point cloud datasets? I think this is important since you mentioned point cloud completion and up-scaling in L26 as potential applications.\n\n2.\tHow can we quantify the distributional uniformity of a certain dataset apart from the visualization in Fig. 4? Furthermore, can we assess the model’s performance with different degrees of uniformity (likely through a simulated dataset)?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "Strengths:\n\n1.\tThe paper is well written and well organized. The idea is original and results bears great significance in terms of fast algorithms for point cloud processing. All conclusions are accompanied with sufficient proof and backed up with experimental results.\n\n2.\tThe core idea of turning the explicit point assignment into an implicit assignment is very intuitive once fully explained. This trick may be of great use in other problems as well.\n\n3.\tThe experimental results well support the claims of bounded-error approximation, achieving outstanding robustness to outliers compared to the baseline methods.\n\nWeaknesses:\n\nN/A. I am not familiar with this field of research and may not be able to justify any doubts.", "was_revised": true, "final_justification": "My questions are all addressed by the author rebuttal, and the authors promised to include more experiments during revision. In terms of performance, while the proposed algorithm runs slower than brute-force on low-dimensional point cloud data, their real advantage lies in update time of high-dimensional data like MNIST. After carefully checking other reviewers' comments (especially Reviewer GBSz) and the author rebuttal, this paper appears to contain solid novel knowledge and can be practically implemented and validated. Therefore, I lean towards accepting this paper, although with very low confidence.", "rebuttal": "We thank the reviewer for insightful comments. We address the major comments as follows.\n\n> How does the algorithm perform on lower-dimensional datasets, such as point cloud datasets? I think this is important since you mentioned point cloud completion and up-scaling in L26 as potential applications.\n\nTo address this question, we have conducted new experiments on the ShapeNet point cloud dataset. As suggested by other reviewers, we also added evaluations where both $A$ and $B$ are dynamic.\n\nHere we report preliminary experiment results only on the new dataset ShapeNet and an existing one Fashion-MNIST. We will expand to run on the other datasets, and add the results in the next version of the paper. In our experiments, both $A$ and $B$ evolve within a sliding window, where points from $A$ and $B$ are alternately inserted. The specifications and parameters of these two datasets are summarized below.\n\n| dataset       | dimension $d$ | $\\|A\\|$ | $\\|B\\|$ | window size | sample size |\n| ------------- | ------------- | ------- | ------- | ----------- | ----------- |\n| Fashion-MNIST | 784           | 60000   | 10000   | 3500        | 100         |\n| ShapeNet      | 3             | 2048    | 2048    | 1500        | 100         |\n\n\nThe detailed error and running time results can be found below. We can see that both the error and running time results exhibit a similar behavior as in our current experiments in the manuscript: we achieve a comparable/slightly better error (which is relative to a brute-force benchmark) compared with the uniform sampling baseline, and we achieve a speedup compared with the brute-force benchmark. \n\nWe note that due to the small size of ShapeNet, our more complicated data structure may lead to a slightly worse performance than the simple brute-force, but the speedup in larger datasets remains significant.\n\n### Detailed Results: Error\nWe report the min, max, and average relative error for both our algorithm and the uniform baseline, evaluated for the ShapeNet dataset as follows. Due to the space limit, we only report the result for ten evenly picked time steps over the entire process.\n\n|   step |   our_err_max |   our_err_min |   our_err_avg |   uni_err_max |   uni_err_min |   uni_err_avg |\n|--------|---------------|---------------|---------------|---------------|---------------|---------------|\n|   1638 |      0.089081 |      0.002748 |      0.039075 |      0.224242 |      0.02824  |      0.094302 |\n|   1911 |      0.025965 |      0.006845 |      0.014477 |      0.127802 |      0.013832 |      0.061511 |\n|   2184 |      0.10265  |      0.002022 |      0.038719 |      0.190679 |      0.033378 |      0.095957 |\n|   2457 |      0.036942 |      0.000126 |      0.011609 |      0.140769 |      0.014554 |      0.075501 |\n|   2730 |      0.061071 |      0.011159 |      0.024967 |      0.303421 |      0.055861 |      0.136652 |\n|   3003 |      0.05533  |      0.009615 |      0.026081 |      0.157239 |      0.010693 |      0.079922 |\n|   3276 |      0.101199 |      0.001433 |      0.030674 |      0.160321 |      0.038384 |      0.097889 |\n|   3549 |      0.048694 |      0.002294 |      0.015526 |      0.045202 |      0.012967 |      0.027885 |\n|   3822 |      0.09417  |      0.011482 |      0.046436 |      0.090955 |      0.012316 |      0.055232 |\n|   4095 |      0.022748 |      0.000265 |      0.008279 |      0.115665 |      0.011511 |      0.061347 |\n\nError evaluation for Fashion-MNIST dataset:\n\n|   step |   our_err_max |   our_err_min |   our_err_avg |   uni_err_max |   uni_err_min |   uni_err_avg |\n|--------|---------------|---------------|---------------|---------------|---------------|---------------|\n|   7000 |      0.017379 |      0.000587 |      0.008961 |      0.035783 |      0.006126 |      0.021922 |\n|  14000 |      0.102088 |      0.00783  |      0.053603 |      0.05268  |      0.008025 |      0.032996 |\n|  21000 |      0.027711 |      0.005504 |      0.013561 |      0.0638   |      0.011997 |      0.030353 |\n|  28000 |      0.040468 |      0.000548 |      0.020453 |      0.042721 |      0.009207 |      0.026044 |\n|  35000 |      0.04584  |      0.00178  |      0.024478 |      0.046525 |      0.008337 |      0.030551 |\n|  42000 |      0.056667 |      0.003062 |      0.03221  |      0.062291 |      0.01514  |      0.029729 |\n|  49000 |      0.054735 |      0.003067 |      0.026688 |      0.035132 |      0.007734 |      0.019372 |\n|  56000 |      0.080342 |      0.013182 |      0.040157 |      0.035516 |      0.000867 |      0.015012 |\n|  63000 |      0.054645 |      0.010068 |      0.026413 |      0.067964 |      0.016561 |      0.040617 |\n|  70000 |      0.07546  |      0.019382 |      0.043388 |      0.038847 |      0.004134 |      0.023396 |\n\n\n### Detailed Results: Running Time\n\nWe report the average update and query time per step, as well as the total running time over the entire run. The running time results on Fashion-MNIST dataset are as follows:\n\n|| Ours | Uniform | Brute-force |\n|-----------| -------- | -------- | -------- |\n|Average update time   | 0.1368 ms      | 0.000242 ms   | 0.6973 ms       |\n|Average query time    | 18.0278 ms     | 16.2884 ms    | 0.000019 ms     |\n|Total time            | 9757.672 ms    | 179.855540 ms | 48813.260192 ms |\n\nThe running time results on ShapeNet dataset are as follows: \n\n|| Ours | Uniform | Brute-force |\n|-----------| -------- | -------- | -------- |\n|Average update time   | 0.0041 ms    | 0.000078 ms  | 0.0033 ms     |\n|Average query time    | 0.106 ms     | 0.063 ms     | 0.00002 ms    |\n|Total time            | 18.028888 ms | 0.945685 ms  | 13.443101 ms  |\n\n> How can we quantify the distributional uniformity of a certain dataset apart from the visualization in Fig. 4? Furthermore, can we assess the model’s performance with different degrees of uniformity (likely through a simulated dataset)?\n\nThe distribution our algorithms sample complexity depends on, is the distribution over $A$ such that the probabily of $a \\in A$ is proportional to $d(a,B)$. The less uniform this distribution is, the better the algorithm performs compared to uniform sampling (as shown by the experiments run with and without outliers). \n\nWhile we could describe this uniformity using standard measures (such as entropy), the performance of our algorithm cannot be characterized purely as a function of this uniformity. In particular, we can prove that our importance sampling also produces results comparable to uniform sampling, if this distribution is uniform but the sets $A$ and $B$ are *well separated*. This requires opening the black-box of our analysis and utilizing the special structure of the quadtree."}]

Author rebuttal:

Meta-review: The chamfer distance between two pointsets A and B is the sum of the nearest neighbor distances from A to B. It has wide applications throughout ML (computer vision, information retrieval), and the paper gives the first algorithm to maintain this value when A and B are subject to dynamic updates. Their main claim is a tradeoff between maintaining a $1+\epsilon$ approximation factor, versus the update time of $O(n^{\epsilon^2})$ maintaining their data structure, significantly improving upon the naive $O(n)$ solution of recomputing the chamfer distance after every update.

The reviewers noted the 'clean' technical algorithms and the intuitive approach of making the 'right' algorithm dynamic. The simplicity of the solution makes it very practical as well, although it was noted that perhaps more thorough experiments are needed to fully demonstrate the power of the algorithm, rather than the somewhat synthetic settings of injecting outliers. The changes include more experiments on point cloud datasets which partially addresses this (minor) weakness. 

Overall, all the reviewers were supportive of the paper and I agree with them.
Decision: Accept (poster)