3 ms·
O˜(N and Poly(k))-Time Algorithm for Bounded Tree Edit Distance
- belter 4y ago"...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... The existence of an O~(n+poly(k))-time algorithm for tree edit distance has been posed as an open question...In this paper, we answer this question positively..." - https://arxiv.org/pdf/2209.07524.pdf https://arxiv.org/pdf/2209.07524.pdf