Edit Distance in Near-Linear Time: It’s a Constant Factor
SIAM Journal on Computing · 31.08.2026 · 55 (4) · 708-786
DOI: 10.1137/21m1392322 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 17.08.2026. Verfasst von Alexandr Andoni und 1 weiteren Autor:innen. Die Arbeit nennt 47 Literaturangaben. Gefördert von: National Science Foundation, Simons Foundation, Columbia-IBM center for Blockchain and Data Transparency.
Abstract (Originalsprache)
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.
Förderung
- National Science Foundation
- Simons Foundation
- Columbia-IBM center for Blockchain and Data Transparency
- JPMorgan Chase and Company
Zitieren
APA
Andoni, A., & Nosatzki, N. S. (2026). Edit Distance in Near-Linear Time: It’s a Constant Factor. SIAM Journal on Computing, 55(4), 708-786. https://doi.org/10.1137/21m1392322
Vancouver
Andoni A, Nosatzki NS. Edit Distance in Near-Linear Time: It’s a Constant Factor. SIAM Journal on Computing. 2026;55(4):708-786. doi:10.1137/21m1392322
BibTeX
@article{Andoni2026,
author = {Andoni, Alexandr and Nosatzki, Negev Shekel},
title = {Edit Distance in Near-Linear Time: It’s a Constant Factor},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {4},
pages = {708--786},
doi = {10.1137/21m1392322}
}
EUVIMED