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

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

doi:10.1109/FOCS.2018.00096

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

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

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Editors	Mikkel Thorup
Publisher	IEEE Computer Society
Pages	979-990
Number of pages	12
ISBN (Electronic)	9781538642306
DOIs	https://doi.org/10.1109/FOCS.2018.00096
State	Published - Nov 30 2018
Event	59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France Duration: Oct 7 2018 → Oct 9 2018

Publication series

Name	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	2018-October
ISSN (Print)	0272-5428

Conference

Conference	59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
Country/Territory	France
City	Paris
Period	10/7/18 → 10/9/18

All Science Journal Classification (ASJC) codes

General Computer Science

Access to Document

10.1109/FOCS.2018.00096

Cite this

Chakraborty, D., Das, D., Goldenberg, E., Koucký, M., & Saks, M. (2018). Approximating edit distance within constant factor in truly sub-quadratic time. In M. Thorup (Ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (pp. 979-990). Article 8555174 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2018.00096

Chakraborty, Diptarka ; Das, Debarati ; Goldenberg, Elazar et al. / Approximating edit distance within constant factor in truly sub-quadratic time. Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. editor / Mikkel Thorup. IEEE Computer Society, 2018. pp. 979-990 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

@inproceedings{789020d8c68b438c93cbcac1b95d7184,

title = "Approximating edit distance within constant factor in truly sub-quadratic time",

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 {\~O}(n 2-2/7 ) that approximates the edit distance within a constant factor.",

author = "Diptarka Chakraborty and Debarati Das and Elazar Goldenberg and Michal Kouck{\'y} and Michael Saks",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 ; Conference date: 07-10-2018 Through 09-10-2018",

year = "2018",

month = nov,

day = "30",

doi = "10.1109/FOCS.2018.00096",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "979--990",

editor = "Mikkel Thorup",

booktitle = "Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018",

address = "United States",

}

Chakraborty, D, Das, D, Goldenberg, E, Koucký, M & Saks, M 2018, Approximating edit distance within constant factor in truly sub-quadratic time. in M Thorup (ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018., 8555174, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2018-October, IEEE Computer Society, pp. 979-990, 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, 10/7/18. https://doi.org/10.1109/FOCS.2018.00096

Approximating edit distance within constant factor in truly sub-quadratic time. / Chakraborty, Diptarka; Das, Debarati; Goldenberg, Elazar et al.
Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. ed. / Mikkel Thorup. IEEE Computer Society, 2018. p. 979-990 8555174 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Chakraborty, Diptarka

AU - Das, Debarati

AU - Goldenberg, Elazar

AU - Koucký, Michal

AU - Saks, Michael

PY - 2018/11/30

Y1 - 2018/11/30

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85059809812&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059809812&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2018.00096

DO - 10.1109/FOCS.2018.00096

M3 - Conference contribution

AN - SCOPUS:85059809812

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 979

EP - 990

BT - Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

A2 - Thorup, Mikkel

PB - IEEE Computer Society

T2 - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018

Y2 - 7 October 2018 through 9 October 2018

ER -

Chakraborty D, Das D, Goldenberg E, Koucký M, Saks M. Approximating edit distance within constant factor in truly sub-quadratic time. In Thorup M, editor, Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018. IEEE Computer Society. 2018. p. 979-990. 8555174. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). doi: 10.1109/FOCS.2018.00096

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

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this