Approximating the Geometric Edit Distance

Abstract

Edit distance is a measurement of similarity between two sequences such as strings, point sequences, or polygonal curves. Many matching problems from a variety of areas, such as signal analysis, bioinformatics, etc., need to be solved in a geometric space. Therefore, the geometric edit distance (GED) has been studied. In this paper, we describe the first strictly sublinear approximate near-linear time algorithm for computing the GED of two point sequences in constant dimensional Euclidean space. Specifically, we present a randomized (O(n\log^2n)) time (O(\sqrt n))-approximation algorithm. Then, we generalize our result to give a randomized $\alpha$-approximation algorithm for any $\alpha \in [\sqrt{\log n},\sqrt{n/\log n}]$, running in time $O(n^2/{\alpha }^2\log n)$. Both algorithms are Monte Carlo and return approximately optimal solutions with high probability.

16 pages, ISAAC 2019