Edit Distance in Near-Linear Time: It’s a Constant Factor

Abstract.

We present an algorithm for approximating the edit distance between two strings of length [Formula: see text] in time [Formula: see text] up to a constant factor for any [Formula: see text]. Our result completes a research direction set forth in the recent breakthrough paper [ CDG[Formula: see text]18 ], which showed the first constant-factor approximation algorithm with a (strongly) subquadratic running time. Recent results [ KS20b ,  BR20 ] have shown near-linear time algorithms that obtain an additive approximation, near-linear in [Formula: see text] (equivalently, constant-factor approximation when the edit distance value is close to [Formula: see text]). In contrast, our algorithm obtains a constant-factor approximation in near-linear time for any input string. In contrast to prior algorithms, which are mostly recursing over smaller substrings, our algorithm gradually smoothes out the local contribution to the edit distance over progressively larger substrings. To accomplish this, we iteratively construct a distance oracle data structure for the metric of edit distance on all substrings of input strings of length [Formula: see text] for [Formula: see text]. The distance oracle approximates the edit distance over these substrings in a certain average sense, just enough to estimate the overall edit distance.