Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance

Debarati Das, Jacob Gilbert, Mohammad Taghi Hajiaghayi, Tomasz Kociumaka, Barna Saha, Hamed Saleh

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

2 Scopus citations

Abstract

Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of edit distance in which the task is to compute a measure of dissimilarity between two (unweighted) rooted trees with node labels. Perhaps the most notable recent application of tree edit distance is in NoSQL big databases, such as MongoDB, where each row of the database is a JSON document represented as a labeled rooted tree and finding dissimilarity between two rows is a basic operation. Until recently, the fastest algorithm for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann; TALG'10); however, Mao (FOCS'21) broke the cubic barrier for the tree edit distance problem using fast matrix multiplication.Given a parameter k as an upper bound on the distance, an O(n+k2)-time algorithm for edit distance has been known since the 1980s due to works of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88). The existence of an O(n+poly(k))-time algorithm for tree edit distance has been posed as open question, e.g., by Akmal and Jin (ICALP'21), who give a stateof-the-art O(nk2)-time algorithm. In this paper, we answer this question positively.

Original languageEnglish (US)
Title of host publicationProceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
PublisherIEEE Computer Society
Pages686-697
Number of pages12
ISBN (Electronic)9781665455190
DOIs
StatePublished - 2022
Event63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 - Denver, United States
Duration: Oct 31 2022Nov 3 2022

Publication series

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

Conference

Conference63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022
Country/TerritoryUnited States
CityDenver
Period10/31/2211/3/22

All Science Journal Classification (ASJC) codes

  • General Computer Science

Fingerprint

Dive into the research topics of 'Õ(n+poly(k))-time Algorithm for Bounded Tree Edit Distance'. Together they form a unique fingerprint.

Cite this