论文标题
美元
$\tilde{O}(n+\mathrm{poly}(k))$-time Algorithm for Bounded Tree Edit Distance
论文作者
论文摘要
计算两个字符串的编辑距离是计算机科学和组合优化的最基本问题之一。树的编辑距离是编辑距离的自然概括，在该距离中，任务是计算带有节点标签的两个（未加权）生根的树之间的差异度量。也许最著名的树编辑距离应用是在NOSQL大数据库中，例如MongoDB，其中数据库的每一行都是一个JSON文档，称为标记的生根树，并且在两个行之间找到差异是一个基本操作。直到最近，树木编辑距离的最快算法以立方时间运行（Demaine，Mozes，Rossman，Weimann； Talg'10）；但是，MAO（FOCS'21）使用快速矩阵乘法破坏了树编辑距离问题的立方障碍。 给定一个参数$ k $作为距离上的上限，自1980年代以来，由于迈尔斯（Algorithmica'86）和兰道和维斯金（JCSS'88），自1980年代以来，已知$ O（N+K^2）$ - 时间算法。存在$ \ tilde {o}（n+\ mathrm {poly}（k））$ - 树编辑距离的时间算法是由Akmal and Jin（iCalp'21）提出的，他给出了一个肯定的$ \ tilde $ \ tilde {o alg alg {o al alg} $ - nk^2）。在本文中，我们积极回答这个问题。
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+k^2)$-time algorithm for edit distance has been known since the 1980s due to the works of Myers (Algorithmica'86) and Landau and Vishkin (JCSS'88). The existence of an $\tilde{O}(n+\mathrm{poly}(k))$-time algorithm for tree edit distance has been posed as an open question, e.g., by Akmal and Jin (ICALP'21), who gave a state-of-the-art $\tilde{O}(nk^2)$-time algorithm. In this paper, we answer this question positively.
