Approximating edit distance within constant factor in truly sub-quadratic time

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

52 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(logn). In this paper, we provide an algorithm with running time Õ(n 2-2/7 ) that approximates the edit distance within a constant factor.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages979-990
Number of pages12
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Country/TerritoryFrance
CityParis
Period10/7/1810/9/18

All Science Journal Classification (ASJC) codes

  • General Computer Science

Keywords

  • Approximation algorithm
  • Edit distance
  • 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