Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time

Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucký, Michael Saks

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time Õ(n2-2/7) that approximates the edit distance within a constant factor.

Original languageEnglish (US)
Article number36
JournalJournal of the ACM
Volume67
Issue number6
DOIs
StatePublished - Nov 2020

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • Edit distance
  • approximation algorithm
  • randomized algorithm
  • sub-quadratic time algorithm

Fingerprint

Dive into the research topics of 'Approximating Edit Distance within Constant Factor in Truly Sub-quadratic Time'. Together they form a unique fingerprint.

Cite this