Document Open Access Logo

3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time

Authors Masoud Seddighin, Saeed Seddighin

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.115.pdf
  • Filesize: 0.98 MB
  • 22 pages

Document Identifiers

Author Details

Masoud Seddighin
  • Institute for Research in Fundamental Sciences (IPM), School of Computer Science, Tehran, Iran
Saeed Seddighin
  • Toyota Technological Institute at Chicago, IL, USA

Acknowledgements

We would like to thank Amir Abboud for very helpful discussions. The second author was supported by a Google Research Gift.

Cite AsGet BibTex

Masoud Seddighin and Saeed Seddighin. 3+ε Approximation of Tree Edit Distance in Truly Subquadratic Time. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 115:1-115:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.115

Abstract

Tree edit distance is a well-known generalization of the edit distance problem to rooted trees. In this problem, the goal is to transform a rooted tree into another rooted tree via (i) node addition, (ii) node deletion, and (iii) node relabel. In this work, we give a truly subquadratic time algorithm that approximates tree edit distance within a factor 3+ε. Our result is obtained through a novel extension of a 3-step framework that approximates edit distance in truly subquadratic time. This framework has also been previously used to approximate longest common subsequence in subquadratic time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • tree edit distance
  • approximation
  • subquadratic
  • edit distance

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shyan Akmal and Ce Jin. Faster algorithms for bounded tree edit distance. In ICALP, pages 12:1-12:15. Springer, 2021. Google Scholar
  2. Tatsuya Akutsu, Daiji Fukagawa, and Atsuhiro Takasu. Approximating tree edit distance through string edit distance. Algorithmica, 57(2):325-348, 2010. Google Scholar
  3. Alexandr Andoni and Negev Shekel Nosatzki. Edit distance in near-linear time: it’s a constant factor. In FOCS, pages 990-1001. IEEE, 2020. Google Scholar
  4. Philip Bille. A survey on tree edit distance and related problems. Theoretical Computer Science, 337(1):217-239, 2005. Google Scholar
  5. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, MohammadTaghi HajiAghayi, and Saeed Seddighin. Approximating edit distance in truly subquadratic time: Quantum and MapReduce. In SODA, pages 1170-1189. SIAM, 2018. Google Scholar
  6. Mahdi Boroujeni, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, and Saeed Seddighin. 1+ ε approximation of tree edit distance in quadratic time. In STOC, pages 709-720. ACM, 2019. Google Scholar
  7. Mahdi Boroujeni, Masoud Seddighin, and Saeed Seddighin. Improved algorithms for edit distance and lcs: beyond worst case. In SODA, pages 1601-1620. SIAM, 2020. Google Scholar
  8. Joshua Brakensiek and Aviad Rubinstein. Constant-factor approximation of near-linear edit distance in near-linear time. In STOC, pages 685-698. ACM, 2020. Google Scholar
  9. Karl Bringmann, PawełGawrychowski, Shay Mozes, and Oren Weimann. Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). In SODA, pages 1190-1206. SIAM, 2018. Google Scholar
  10. Peter Buneman, Martin Grohe, and Christoph Koch. Path queries on compressed XML. In VLDB, pages 141-152. VLDB Endowment, 2003. Google Scholar
  11. Horst Bunke and Kim Shearer. A graph distance metric based on the maximal common subgraph. Pattern Recognition Letters, 19(3):255-259, 1998. Google Scholar
  12. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Koucky, and Michael Saks. Approximating edit distance within constant factor in truly sub-quadratic time. In FOCS, pages 979-990. IEEE, 2018. Google Scholar
  13. Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Kouckỳ, and Michael Saks. Approximating edit distance within constant factor in truly sub-quadratic time. Journal of the ACM (JACM), 67(6):1-22, 2020. Google Scholar
  14. Sudarshan S. Chawathe. Comparing hierarchical data in external memory. In VLDB, pages 90-101. Morgan Kaufmann Publishers Inc., 1999. Google Scholar
  15. Erik D Demaine, Shay Mozes, Benjamin Rossman, and Oren Weimann. An optimal decomposition algorithm for tree edit distance. In ICALP, pages 146-157. Springer, 2007. Google Scholar
  16. Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, and S. Muthukrishnan. Compressing and indexing labeled trees, with applications. Journal of the ACM (JACM), 57(1):4:1-4:33, November 2009. Google Scholar
  17. Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, 1997. Google Scholar
  18. Dov Harel and Robert Endre Tarjan. Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing (SICOMP), 13(2):338-355, 1984. Google Scholar
  19. Philip N. Klein. Computing the edit-distance between unrooted ordered trees. In ESA, pages 91-102. Springer, 1998. Google Scholar
  20. Michal Kouckỳ and Michael Saks. Constant factor approximations to edit distance on far input pairs in nearly linear time. In STOC, pages 699-712. ACM, 2020. Google Scholar
  21. Gad M Landau, Eugene W Myers, and Jeanette P Schmidt. Incremental string comparison. SIAM Journal on Computing (SICOMP), 27(2):557-582, 1998. Google Scholar
  22. Xiao Mao. Breaking the cubic barrier for (unweighted) tree edit distance. In FOCS. IEEE, 2021. Google Scholar
  23. Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. Approximation algorithms for lcs and lis with truly improved running times. In FOCS, pages 1121-1145. IEEE, 2019. Google Scholar
  24. Stanley M Selkow. The tree-to-tree editing problem. Information processing letters, 6(6):184-186, 1977. Google Scholar
  25. Bruce A. Shapiro and Kaizhong Zhang. Comparing multiple RNA secondary structures using tree comparisons. Bioinformatics, 6(4):309-318, 1990. Google Scholar
  26. Kuo Chung Tai. The tree-to-tree correction problem. Journal of the ACM (JACM), 26(3):422-433, July 1979. Google Scholar
  27. Hélène Touzet. A linear tree edit distance algorithm for similar ordered trees. In CPM, pages 334-345. Springer, 2005. Google Scholar
  28. Michael S Waterman. Introduction to computational biology: maps, sequences and genomes. CRC Press, 1995. Google Scholar
  29. Kaizhong Zhang and Dennis E. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal on Computing (SICOMP), 18(6):1245-1262, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact