Fully Dynamic Algorithms for Chamfer Distance

We thank the reviewer for insightful comments. We address the major comments as follows.

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.

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

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

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

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

Detailed Results: Error

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

Error evaluation for Fashion-MNIST dataset:

Detailed Results: Running Time

We 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:

The running time results on ShapeNet dataset are as follows:

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)?

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

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

We thank the reviewer for insightful comments. We address the major comments as follows.

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.

Unfortunately, we did not manage to find publicly available naturally dynamic datasets suitable for our experiments.

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.

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

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

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

We thank the reviewer for insightful comments. We address the major comments as follows.

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.

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

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

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

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

Detailed Results: Error

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

Error evaluation for Fashion-MNIST dataset:

Detailed Results: Running Time

We 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:

The running time results on ShapeNet dataset are as follows:

The current approximation is one-sided (from A to B). Would the same dynamic framework support symmetric Chamfer distance efficiently?

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

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

While runtime speedups are demonstrated, it would be helpful to understand the algorithm’s space complexity, especially for high-dimensional datasets.

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

We thank the reviewer for insightful comments. We start with presenting some new experiment results, and then we address other comments.

New Experiments

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.

We address these comments in the following aspects:

• 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.
• We let $A$ undergo dynamic updates besides having a dynamic point set $B$, in all our error and running time evaluations.

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

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

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

Detailed Results: Error

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

Error evaluation for Fashion-MNIST dataset:

Detailed Results: Running Time

We 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:

The running time results on ShapeNet dataset are as follows:

Other comments

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?

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

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

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.

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

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

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

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.

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

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

What is the total memory overhead?

The worst-case blowup is a $\mathrm{poly}\log$ factor.

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

worst-case point distributions that might cause the importance sampling to degrade significantly.

If we interpret this question correctly, this seems to suggest that our importance sampling does not have a decent worst-case bound.

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

A brief Limitations section addressing these scalability and practical deployment challenges would strengthen the paper's contribution.

We will include a discussion of the limitations and assumptions of our algorithm from a practical perspective in the next version of the paper.