Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic

Our Results

• For every 0 < δ < 1, TED admits a (log n)^O(1/δ)-approximation in O(n^(1+δ)) time.This gives a near-linear-time guarantee matching ED up to a subpolynomial factor.Source: §1 · p. 4
• Adapting an ED approximation scheme to TED requires new notions, and reducing the number of dynamic-programming states recovers the ED running-time trade-off.Without that reduction, the adaptation would take O(n^(1+δ) · k) time.Source: §1 · p. 5
• A randomized algorithm approximates 1 + ted(F, G) within a (log n log log n)-approximation in O(n/τ) time using balanced-parentheses query access.The access model provides constant-time queries for node labels and matching-parenthesis positions, but accessing a node’s parent may take time proportional to its degree.Source: §1 · p. 5
• The sublinear result implies a first linear-time TED approximation, with a 2^O(√(log n log log n))-approximation.The paper notes that distinguishing ted = 0 from ted > 0 is easy, allowing the approximation of 1 + ted to yield one for ted itself.Source: §1 · p. 5
• For a threshold k and 0 < ε ≤ 1, a randomized dynamic algorithm maintains a (1 + ε)-approximation or reports ted(F, G) > k in amortized Õ(k ε^-O(1)) update time.It is correct with high probability against an oblivious adversary.Source: §1 · p. 5
• A deterministic dynamic algorithm reports ted(F, G) or ted(F, G) > k in amortized Õ(k^7) update time.The paper identifies a regime k ≪ n^(1/7) where this algorithm beats recomputation after every update.Source: §1 · p. 6

• The section introduces the basic notation used in the paper.Source: §2 · p. 6
• It focuses on the static algorithms behind Main Theorems 1 and 2 in Section 2.2.Source: §2 · p. 6
• The tools and insights developed for the static algorithms also apply to the dynamic algorithms behind Main Theorems 3 and 4.Source: §2 · p. 6

• A string alignment pairs positions in order, with unmatched characters costing 1, unequal matched pairs costing 1, and equal matched pairs costing 0.Source: §2.1 · pp. 6–7
• Figure 1 illustrates an optimal edit sequence deleting v2 and v9 and inserting u4, with the other nodes matched.Aligned parentheses occur in pairs and do not cross.Source: Figure 1 · p. 7
• A tree alignment matches preserved nodes while respecting both preorder and postorder orderings; its cost is the number of unmatched nodes plus the cost of matched unequal labels.TED is equivalently the minimum alignment cost [Tai79].Source: §2.1 · pp. 6–7
• Each node appears twice in the bi-order traversal, and its two occurrences are paired by the twin function.The traversal interleaves the root twice around the traversal of the forest left after removing it.Source: §2.1 · p. 7
• A tree alignment induces a string alignment by matching both occurrences of each aligned node, and paired parentheses must remain aligned together.This constrained-string view allows ED techniques to be lifted to TED.Source: §2.1 · p. 8

2.2 Static Approximation Algorithms

• The framework achieves the ED-style trade-off of O(c log_c n) approximation and O(nc · (log n)^O(log_c n)) time, but adapting it to TED requires new constructions.The constructions address subforest fragments, decomposition, and the added cost of considering pairs of shifts.Source: §2.2 · pp. 8–9, §2.2.2 · p. 11

2.2.1 Generalizing Tree Edit Distance to Subforests

• TED dynamic-programming states use subforests represented by mono- or bi-intervals; bi-intervals accommodate paired parentheses that may be far apart in the traversal.Only fully contained nodes can align, and spine nodes have their two occurrences in separate parts of a bi-interval.Source: §2.2.1 · pp. 9–10

2.2.2 Robust Hierarchical Decomposition

• The hierarchical decomposition has O(n/c^t) level-t subforests of size O(c^t), and a random level-t subforest can be sampled in Õ(c^t) time with high probability.For dynamic updates, the decomposition changes by modifying O(d) subforests amortized, enabling a dynamic-programming scheme that changes only a few states.Source: §2.2.2 · pp. 10–11

2.2.4 State Sparsification

• Shift sparsification uses Õ(k) candidate shifts for coupled bi-interval states; when few spine nodes align, it decouples the intervals and pays additional alignment cost.The paper also uses this sparsification to support Õ_ε(k), rather than Õ_ε(k^2), update time in its dynamic approximation algorithm.Source: §2.2.4 · pp. 11–12

2.2.5 Static Approximation in Almost-Linear Time

• Combining sparsification with efficient dynamic-programming transitions yields the near-linear-time approximation algorithm.The transitions use weighted-point queries, with precision assignments preserving the precision-sampling scheme.Source: §2.2.5 · p. 12

2.2.6 Static Approximation in Sublinear Time

• For any τ ≥ 1, the reduction cuts running time by a factor of τ while increasing the approximation ratio by Õ(τ), approximating 1 + ted(F, G).It samples level-t subforests using query access to the balanced-parentheses representation, without preprocessing.Source: §2.2.6 · p. 13

2.3 Dynamic Exact and Approximation Algorithms

• The dynamic algorithms build on a forest-decomposition DP whose label substitutions require recomputing only ˜O(k^7) states; its approximation variant runs in ˜O_ε(nk) time [BGHS19].The localized state recomputation contrasts with classical TED dynamic programs that require at least Ω(n) states to be recomputed after one update, even for k = ˜O(1).Source: §2.3 · pp. 13–14

2.3.1 An ˜𝓞(𝒏𝒌6)-time DP Algorithm for Exact Tree Edit Distance

• ˜O(nk^6) time suffices to recover exact TED whenever ted(F, G) ≤ k by restricting the DP to k-bounded alignments.The restricted recursion yields an upper bound on TED and a lower bound on the distance limited to k-bounded alignments, which coincide when TED is at most k.Source: §2.3.1 · p. 15

2.3.2 Sparsifying the DP Algorithm to Achieve a (1 + 𝜺)-Approximation in Time ˜𝓞𝜺(𝒏𝒌)

• ˜O_ε(nk) time yields a (1 + ε)-approximation by sparsifying the DP values stored for each decomposition node.The scheme samples spine nodes for dependent cases and handles decoupled cases separately; logarithmic-height error accumulation is absorbed by scaling ε.Source: §2.3.2 · pp. 15–16

2.3.3 An Exact Dynamic Algorithm with ˜𝓞(𝒌8) Update Time

• ˜O(k^7) recomputation handles a label substitution by updating only states near its positions, but deletions can shift indices and force work across all decomposition nodes.The affected-node set has O(k log n) nodes, and the method initially described does not preserve this locality for deletions or insertions.Source: §2.3.3 · p. 16

2.3.4 Finding Nearby Isomorphic Subforests

• ˜O(1)-time identifier queries find nearby isomorphic subforests, while maintaining the identifiers costs ˜O(k^5) per update.The identifiers use dynamic labeled-parenthesis strings, with a range-emptiness structure ensuring the matching subforests share the same spine nodes.Source: §2.3.4 · p. 17

2.3.5 Improving the Update Time to ˜𝓞(𝒌7)

• ˜O(k^7) amortized update time follows from maintaining an invariant over epochs of k updates and charging recomputation to a decreasing potential.The initial potential is ˜O(k^6), amortizing the potential-decrease cost across each epoch.Source: §2.3.5 · p. 18

2.3.6 Dynamic (1 + 𝜺)-Factor Approximation

• Restricting maintained mono-intervals to length at most |I_v,1|ε^-1 is proposed to avoid quadratic dependence on k in dynamic approximation updates.For a fixed interval length q, at most q such intervals intersect a given update position; corresponding restrictions apply to the other side and the bi-intervals.Source: §2.3.6 · p. 19
• Dynamic grid nearest-neighbor queries use dynamic 2D range emptiness, while distance structures within F and between F and G reuse the same samples.The manuscript addresses these challenges in Section 7.Source: §2.3.6 · p. 19

Trees, Forests, and Subforests

• Each forest node appears twice in a bi-order traversal, whose paired occurrences are nested or separate, yielding a balanced-parenthesis representation.A node's left and right occurrence positions are paired; ancestor pairs nest, while pairs for non-ancestor nodes can be separate.Source: §3 · p. 20
• A subforest selects traversal positions from an interval collection; it is balanced when it retains both occurrences of each selected node or neither, and padding positions cannot be aligned.For a bi-interval, spine nodes have their two occurrences in different intervals.Source: §3 · p. 20

Tree Alignments

• Alignments pair corresponding first or second occurrences without crossings; matches cost zero, substitutions cost 1/4, and each deleted occurrence costs 1/2.On intervals spanning both complete forests, minimum alignment cost equals their tree edit distance.Source: §3 · pp. 21–23

Properties and Decompositions

• For shifted interval collections, TED changes by at most 2 times the sum of absolute shift differences; partitioning collections gives an upper bound by the sum of the component distances.The shift bound also holds for k-bounded TED.Source: §3 · pp. 23–24, Figure 8 · p. 24

Augmented Alignments

• Augmented alignments assign positions to deleted as well as aligned positions, producing a nondecreasing map whose range contains the aligned positions between any two input positions.This augmentation enables local analysis even where the original alignment is undefined for deleted positions.Source: §3 · p. 25

3 Preliminaries

• Restricting an optimal alignment to a disjoint interval collection and its image yields an optimal alignment for the corresponding subforests, including in the k-bounded variant.The image collection is defined using the alignment’s interval map.Source: §3 · pp. 26–27
• When a partition keeps both occurrences of each node in the same piece, the edit distances of the corresponding subforests sum to the original distance.The equality also holds for k-bounded distances when the original alignment is optimal among k-bounded alignments.Source: §3 · p. 27
• For positions a ≤ b in a balanced subforest interval, the difference in their alignment displacements is at most 2 · ted(F_ℐ, G_𝒥′).The displacement uses the alignment map when a position is aligned and the interval-image map otherwise.Source: §3 · p. 27
• If ted(F, G) ≤ k, then ted(F, G) = ted^(k)(F, G), because every alignment of cost at most k is k-bounded.For any position b, the displacement |b − π′(b)| is at most twice the alignment cost.Source: §3 · p. 27

Hierarchical decomposition

• The hierarchy has O(log_c n) levels, O(n) total nodes, and degree O(c), with O(n/c^t) level-t subforests of size O(c^t).A finer decomposition partitions each coarser piece into at most 6c pieces.Source: §4 · pp. 27, 29, 30

Relation to prior decompositions

• Earlier decompositions achieved some structural properties separately, while this construction combines them; the authors note that previous work lacked a close analogue of its sampling property.The cited comparison covers properties (1)–(4), including uniform subforest sampling.Source: §4 · pp. 27–28

Construction and properties

• The construction assigns each node’s two traversal positions to one partition element, producing balanced subforests bounded in size by the largest block.The resulting pieces are intervals or pairs of intervals, and their number is at most 3b for b blocks.Source: §4 · pp. 28–29
• Each decomposition element touches only a constant number of blocks in aggregate: for any subset S, |S| is at most three times its number of incident blocks.In particular, the single-level decomposition contains at most 3b pieces.Source: §4 · p. 29

Sensitivity

• Changing one partition boundary changes only a constant number of pieces, and the difference can be determined by scanning one or two blocks.The symmetric difference contains at most 12 pieces on one side and at most one on the other.Source: §4 · pp. 30–31
• Inserting a node changes only a constant number of decomposition pieces outside the pieces preserved by the position embedding.The section bounds each of the two sets of non-preserved pieces by three.Source: §4 · p. 31

5 A Near-Linear-Time Approximation Algorithm for TED

• For every 0 < δ < 1, a randomized algorithm gives a (log n)^O(1/δ)-approximation of ted(F, G) in O(n^(1+δ)) time with high probability.This is Main Theorem 1 for n-node forests F and G.Source: §5 · p. 32

5.1 Tree Distance (not to be Confused with Tree Edit Distance)

• Tree Distance lower-bounds TED and, when ted(F, G) ≤ k, is at most 48 · c^D · ted(F, G), where D is the number of partition-tree levels.The framework recursively evaluates shifted interval collections; the two bounds make its root value a controlled proxy for TED.Source: §5.1 · p. 33

5.2 Warm-up: An ˆ𝒪(nk)-Time Algorithm

• The precision-sampling warm-up gives a (log n)^O(1/ε)-approximation in O((k + 1)n^(1+ε)) time, while its baseline runs in ˜O(nk) time.The warm-up algorithm approximates Tree Distance across shifts, combining child values with precision sampling.Source: §5.2 · pp. 35, 37

5.3 A Near-Linear Time Algorithm

• For bi-intervals, the near-linear approach limits shifts by trading off edit distance against spine-node count, either testing matched-node shifts or decoupling into mono-intervals.The partition DAG adds nodes for the two individual intervals of each bi-interval, supporting this decoupling; the passage presents this as the approach toward the runtime target.Source: §5.3 · pp. 37–38
• For arbitrary shifts, ted(F, G) ≤ TD_r,⟨0⟩(F, G); with good shifts, TD_r,⟨0⟩(F, G) ≤ 48^c · 2^D · ted(F, G).Here r is the root of T_c(F), and D is the number of levels of T_c(F).Source: §5.3 · pp. 39–40
• For each bi-interval, Algorithm 2 returns a shift selection good with respect to an optimal alignment with probability at least 1 − n^-4γ.It samples ⌈γ log n⌉ spine nodes; the resulting shift selection has size O((k + 1) log n).Source: §5.3 · pp. 42–43
• With K ≥ k, Algorithm 4 approximates each TD_v,s within (α_v, 1/r_v) with probability at least 0.9 and runs in O(n^c (log n)^O(log^c n)) time with probability at least 0.98.The algorithm computes Tree Distance values recursively over T_c(F), including left and right values for bi-intervals.Source: §5.3 · p. 43

4 else

• Precision sampling combines successor estimates into an (α_v, 1/r_v)-approximation of TD_v,s when the successor precisions are mutually independent.Source: §4 · p. 45
• The algorithm samples shift selections for bi-interval nodes, and all such nodes receive good selections with probability at least 1 − n^-6.Source: §4 · p. 45
• For 0 < δ < 1, the randomized algorithm gives a (log n)^O(1/δ)-approximation of ted(F, G) in O(n^(1+δ)) time with high probability.Source: §4 · p. 46
• The algorithm supports TED computation on balanced mono-intervals or disjoint bi-intervals, with running time depending on |ℐ| when the subforest contents are known.Source: §4 · p. 46

5.4 Deferred Proofs

• Lemma 5.21 computes min_p{v_p + 2||p − q||_1} for all query points in Õ(|P| + |Q|) total time.Source: §5.4 · pp. 46–47
• Algorithm 1 has O(n/K · (log n)^O(log_c(n))) active nodes with probability at least 0.98.Source: §5.4 · p. 47

6 A Simple Sublinear Algorithm for TED

• The reduction samples blocks at selected decomposition levels, queries traversal intervals intersecting each block, and tests the induced forest pairs with the gap oracle.A no answer from any local call makes the reduction return no; otherwise it returns yes.Source: §6 · p. 48
• A (k, K)-Gap-TED instance reduces to an expected O(n/K) calls to a (21k, τ)-Gap-TED oracle, with error probability at most e^-1.The reduction’s expected total size and time exclude execution of the gap oracle.Source: §6 · p. 48
• For each node’s associated interval collection, the induced forest pair has TED at most 21 times the original distance.This bound supports the yes-case correctness of the reduction when ted(F, G) ≤ k.Source: §6 · pp. 48–49
• When ted(F, G) > K, the reduction returns no with probability at least 1 − e^-1.The correctness analysis marks nodes whose induced forest-pair distance exceeds τ and bounds the probability of missing them during sampling.Source: §6 · pp. 49–50
• The randomized algorithm approximates 1 + ted(F, G) in O(n/τ) time.The theorem’s approximation factor is not fully legible in the supplied passage.Source: §6 · pp. 51–52

7 Dynamic Exact and Approximate Algorithms

• The randomized dynamic algorithm reports a (1 + ε)-approximation of ted(F, G), or reports ted(F, G) > k, in amortized Õ(k ε^-O(1)) time per update.It is correct with high probability against an oblivious adversary.Source: §7 · p. 52
• The dynamic results assume a known upper bound N on total nodes and polynomially many updates; randomized guarantees also assume an oblivious adversary.The hidden polylogarithmic factors are in N.Source: §7 · pp. 52–53
• The deterministic dynamic algorithm reports ted(F, G) exactly, or reports ted(F, G) > k, in amortized Õ(k^7) time per update.Source: §7 · p. 53

The Decomposition Tree

• The dynamic decomposition tree has O(log n) depth, binary internal nodes, balanced-subforest representations, and O(log^2 N) amortized update time.All leaves share a depth, and an update affects O(log N) amortized nodes.Source: §7.1 · pp. 53–54

Maintaining Bi-Intervals using Pointers

• Unique occurrence identifiers let intervals continue to reference the same forest content when insertions or deletions shift positional indices.The identifiers replace raw positions as interval endpoints, so an unchanged subforest remains identifiable across updates.Source: §7.1 · pp. 54–55

Maintaining a Decomposition Tree under Updates on F

• A weight-balanced B-tree induces the decomposition partitions, and maintaining its hierarchy and relinking affected parts takes O(log^2 N) amortized time per update.Rebalancing work at each height is charged to updates in the affected subtree, yielding O(log N) amortized cost per height.Source: §7.1 · pp. 55, 57, 58

The Decomposition Tree

• Replacing each node of the intermediate tree with a gadget yields a binary decomposition whose child interval collections partition the parent’s while preserving spine-node requirements.The gadget can be constructed in O(c) time for a node with c children, and its interval partitions follow five mono/bi-interval relation types.Source: §7.1 · p. 58

7.1 Restructuring Bi-Intervals and Tree Decomposition

• Recursive mono-/bi-interval splits preserve the partition and spine-node invariants, and produce a gadget of size O(c) for c children.A mono-to-bi step is followed by a binary split, ensuring the recursion terminates.Source: §7.1 · pp. 59–60
• The decomposition tree has depth O(log n), at most two children per internal node, balanced subforests, and interval collections that partition each parent and the full range at each level.Each child interval is a prefix or suffix of a parent interval.Source: §7.1 · p. 60
• O(log^2 N) is the amortized update time for maintaining the decomposition tree under node insertions and deletions.The number of affected nodes is O(log N) amortized per update.Source: §7.1 · p. 60
• The construction replaces nodes of a dynamic tree with mini binary-tree gadgets and pads gadget leaves to a common depth to preserve level-wise partitions.Rebuilding gadgets for new nodes takes O(log N) time per node, while the number of new nodes remains O(log N) amortized per update.Source: §7.1 · pp. 60–61

7.2 Allowed Windows and Oracles

• Allowed intervals have endpoints within 2k of the original, while rounding selects sparse lengths and limits length error to ε times the original length deviation.For prefix- or suffix-aligned intervals, rounding also preserves endpoint proximity within 2k.Source: §7.2 · p. 62
• For mono-interval queries, the oracle rounds to a stored interval and adds a length-difference correction, yielding an upper bound of α(1+8ε) times the k-bounded distance.The correction lets the estimate apply to the original query rather than only the rounded interval.Source: §7.2 · pp. 64–65
• With probability at least 1−N^-γ, each node admits an extended α(1+21ε)-approximation oracle using stored values on sparsified interval families and spine-node samples.The stored values cover sparsified single-interval families and, for bi-intervals, sampled spine-node queries.Source: §7.2 · p. 64
• For bi-intervals, if an optimal alignment matches at most an ε fraction of spine nodes, the oracle’s estimate is at most α(1+13ε) times the k-bounded distance.A good sample contains a spine node aligned by any optimal alignment matching more than an ε fraction, enabling the other case to be handled through a sampled node.Source: §7.2 · pp. 64, 66

Allowed Windows and Oracles

• If some window J_i has |J_i| ≥ |I_v,i|/ε, then t ≤ α(1 + 17ε) · ted^(k)(F_{I_v}, G_J).This bound applies when at least one allowed window is large relative to its corresponding input interval.Source: §7.2 · p. 66
• If the alignment matches more than εm_v spine nodes and every window J_i has |J_i| ≤ |I_v,i|/ε, then t ≤ α(1 + 21ε) · ted^(k)(F_{I_v}, G_J).This is the complementary small-window case, subject to the spine-alignment condition.Source: §7.2 · pp. 66, 68
• Algorithm 8 computes t in O(Tk^2) time with ted(Fℐᵥ, G𝒥) ≤ t ≤ α·ted⁽ᵏ⁾(Fℐᵥ, G𝒥); substituting L with ˜L at Line 8 gives O(Tε⁻² log² N) time.Source: §7.2 · p. 68
• When ℓ_v = 2 and child oracles are extended, Algorithm 9 computes a part-specific value in O(Tε^-1 log N) time.The method restricts recomputation to one part and queries extended child oracles when an interval is only one side of a bi-interval.Source: §7.2 · pp. 68–69

7.3 Maintaining Distances within F

• Theorem 7.21 maintains per-node exact-window values deterministically and approximate-window values randomly, with high-probability success, amortized update time O(k ε^-15 log^17 N), and O(log N) access.The theorem also maintains good spine-node samples in the approximate setting.Source: §7.3 · pp. 71–72
• The exact algorithm’s recomputation for nodes in A° takes O(k^7 log^2 N) time per update, using O(k^4) windows per node and O(k^2 log N) time per value.The bound uses |A°| = O(k log n).Source: §7.3 · pp. 72, 76
• For old nodes outside A°, the identifier sets remain unchanged and stored values remain valid, so no stored information needs updating.For the distance-preservation claim at nodes in A° \ A•, the result assumes matching identifiers and update positions outside the window union; deletions require the additional stated convex-hull condition.Source: §7.3 · pp. 74, 76
• For approximate values at nodes in A° \ A•, the symmetric difference of identifier sets is O(k ε^-6 log^6 N) and can be computed in O(k ε^-6 log^7 N) total time.The algorithm updates values for added and removed identifiers and recomputes retained values when the distance-preservation conditions do not hold.Source: §7.3 · pp. 74, 76
• The exact setting has amortized update time O(k^7 log^2 N), dominated by A◦ computations.Newly added nodes invoke Claim 7.22 at most O(k^4 log n) times on average, contributing O(k^6 log^2 N).Source: §7.3 · p. 76
• For nodes in A• ∪ Pnew, the approximate algorithm recomputes O(k ε^-5 log^5 N) entries per node, at O(ε^-9 log^11 N) time per entry.Since both node sets have O(log n) nodes on average, their total recomputation contribution is O(k ε^-14 log^17 N).Source: §7.3 · p. 76
• The approximate setting has overall amortized update time O(k ε^-15 log^17 N).For nodes in A• ∪ Pnew, recomputation contributes O(k ε^-14 log^17 N); the remaining nodes also require recomputing entries and updating identifiers and auxiliary information.Source: §7.3 · p. 76

7.4 Handling any Updates in F or G

• Rather than recomputing all terms for F and G from scratch, the algorithm copies existing maintained values when subforests are equivalent; if neither lookup succeeds, it decreases potential recursively.It computes tv(J) in O((1 + φ)·k^2 log^3 N) time, or ˜tv,i(J) and ˜tv(J) in O((1 + φ)·ε^-9 log^13 N) time, decreasing Φc by φ.Source: §7.4 · pp. 77, 79
• The randomized approximate algorithm has amortized update time O(k ε^-15 log^19 N) and amortized access time O(log^3 N) for maintained values.It maintains approximate values for the stated tree and window families and succeeds with high probability.Source: §7.4 · p. 77
• The epoch invariant bounds the number of unresolved pairs or triples by the potential when the trees’ TED at the epoch start is at most 2k.If the potential is exhausted, the algorithm reports TED(F, G) > k; epochs contain k updates, with F’s baseline structures refreshed in bulk at epoch end.Source: §7.4 · p. 77
• For unaffected windows with matching identifiers, an update preserves the TED value and the stated bounded-distance relation, while touched identifiers can be listed in O(k ε^-6 log^7 N) time.The preservation result applies when the windows avoid the update positions; the touched-identifier bound is stated for the approximate setting.Source: §7.4 · p. 81
• Intervals disjoint from the update positions retain their stored invariant data, while affected nodes are processed bottom-up and their values recomputed.In the approximate procedure, touched identifiers are recomputed while untouched identifiers preserve their invariants.Source: §7.4 · p. 82
• When ted(F, G) ≤ 2k, at most O(k^6 log n) exact-setting instances violate Invariant (b) at initialization, with an approximate-setting bound of O(k^2 ε^-6 log^6 N).Setting the initial potential Φ0 to a sufficiently large constant times the respective bound ensures the invariant holds at batch start.Source: §7.4 · p. 82
• Amortized O~(k ε^-O(1)) updates maintain a (1 + ε)-approximation or report ted(F, G) > k, with high probability against an oblivious adversary.The analysis gives O(k ε^-15 log^19 N) total update time.Source: §7.4 · p. 84
• Amortized O~(k^7) updates maintain exact ted(F, G) or report ted(F, G) > k deterministically.The total update analysis gives O(k^7 log^4 N) time.Source: §7.4 · pp. 84–85

7.5.1 Proof of Lemma 7.40

• The range-search construction returns a point within (1 + ε) times the optimal L1 distance, using binary search over approximating L1 balls.For the large-distance case, each search tests a union of O(ε^-1) rectangles; the runtime is O(Tε^-1 log(n + m) + Tε^-2).Source: §7.5.1 · p. 86

7.5.2 Proof of Lemma 7.41

• The interval-counting proof bounds relevant node sets by O(log n) and O(k log n), and bounds the counted interval and tuple families by O(kε^-2 log^2 N) and O(kε^-6 log^6 N).The O(log n) set forms a root-to-leaf path, while the O(k log n) set forms a connected subtree rooted at the tree root.Source: §7.5.2 · p. 88

7.5.3 Proof of Lemma 7.47

• For equal-length mono-intervals, subforests are equivalent exactly when their labeled-parenthesis substrings match; bi-interval equivalence requires extra information about at most two spine nodes.The forest strings mark each node’s first and second occurrences with labeled opening and closing symbols, respectively.Source: §7.5.3 · p. 90
• The algorithms use deterministic fragment fingerprints of O(log(n+Q)) bits, with equality exactly characterizing matching fragments and O(log^1+o(1)(n+Q)) worst-case query and update time [KK22, Section 8].Fingerprints encode interval relative position and, for separated bi-intervals, spine-node offsets; stored matches provide a witness window after a fingerprint lookup.Source: §7.5.3 · pp. 91–92
• A deterministic dynamic algorithm answers interval-collection matching queries in O(log^3 N) time and has O(k^5 log^4 N) amortized update time.Given v and an interval collection J, it determines whether a window L in W_4k(I_v) satisfies F_L ≡ G_J and returns one if it exists.Source: §7.5.3 · p. 91
• A second deterministic algorithm answers mono- or bi-interval matching queries in O(log^3 N) time and has O(kε^-6 log^9 N) amortized update time.It supports queries indexed by i or z, respectively, and the bi-interval variant uses a set Z_v of O(ε^-1 log N) spine nodes, redrawn when v is created or F_I_v changes.Source: §7.5.3 · p. 92

A A Comparison Between Bi-Intervals, Super-Windows and Contexts

• Bi-intervals generalize super-windows [SS22] and contexts [DGH+22, DGH+23, KS25, DGH+25], which are defined to be balanced.Balanced means they cannot partially contain any node.Source: A A Comparison Between Bi-Intervals,… · p. 98
• Unlike super-windows and contexts, a bi-interval subforest need not be balanced.That permits an aligned image to be represented even when it is imbalanced.Source: A A Comparison Between Bi-Intervals,… · p. 98
• In the example, the only aligned image of the balanced subforest partially contains u4, making that image imbalanced.The corresponding subforest in G must include u2 and u3 but exclude nodes matched outside the selected subforest in F.Source: A A Comparison Between Bi-Intervals,… · p. 98