Fully Dynamic Algorithms For Chamfer Distance | Awesome Similarity Search Papers

Fully Dynamic Algorithms For Chamfer Distance

We study the problem of computing Chamfer distance in the fully dynamic setting, where two set 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 (\mathrm{dist}{\mathrm{CH}}(A,B) = \sum{a \in A} \min_{b \in B} \textrm{dist}(a,b)), where (\textrm{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.

Explore more on:
ANN Search
Similar Work
Loading…