Practical Threshold-based Tree Edit Distance Lower-Bounds

Practical Threshold-based Tree Edit Distance Lower-Bounds Lukáš Moravec, Radim Bača VSB - Technical Universitty of Ostrava Ostrava, Czech Republic lukas.moravec.st2@vsb.cz,radim.baca@vsb.cz

arXiv:2609.03078v1 [cs.DB] 2 Sep 2026

ABSTRACT Threshold-based similarity search over tree-structured data using tree edit distance (TED) is computationally intensive. Given a query tree and a database of trees, the goal is to retrieve all trees within a predefined TED threshold 𝜏. Because exact TED computation is expensive, practical methods employ lower-bounds to prune dissimilar candidates before verification. Existing lower-bounds exhibit a fundamental trade-off: inexpensive statistical and structural bounds provide limited pruning power, whereas the more precise traversal-based string edit distance (SED) bound is expensive to compute using standard quadratic dynamic programming. Moreover, previous comparative studies do not cover recent structural filters or threshold-aware SED implementations, leaving their practical trade-offs unclear. In this article, we first provide a comprehensive experimental comparison of state-of-the-art TED lower-bounds in terms of pruning precision and computational cost. We then accelerate the SED lower-bound using Ukkonen’s bounded string edit distance algorithm, substantially reducing its runtime without affecting its pruning power. Finally, we introduce the SED-struct threshold filter, which strengthens SED with axes-aware constraints capturing structural relationships among tree nodes. Experiments on synthetic and real-world datasets show that SED-struct consistently achieves the highest filtering precision while retaining practical filtering costs. The results suggest that SED-struct is particularly beneficial for heterogeneous tree collections in which the standard SED lower-bound achieves relatively low precision. PVLDB Reference Format: Lukáš Moravec, Radim Bača. Practical Threshold-based Tree Edit Distance Lower-Bounds. PVLDB, xx(x): 1111 - 1122, 2027. doi:10.14778/xxxxxx.xxxxxx PVLDB Artifact Availability: The source code, data, and/or other artifacts have been made available at https://github.com/LukMRVC/tree_similarity_extension & https://github. com/LukMRVC/ted-search.

1

INTRODUCTION

The search for similar trees is an underlying problem that can be applied in linguistics [3] for syntactical analysis of treebank patterns, in bioinformatics [17] [16] for comparing secondary RNA This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment. Proceedings of the VLDB Endowment, Vol. xx, No. x ISSN 2150-8097. doi:10.14778/xxxxxx.xxxxxx

structures, in web data [12] to detect near-duplicate websites, or in code plagiarism detection [29, 30] that is based on an AST similarity. The most common similarity measure for ordered labeled trees is the tree edit distance [31] (TED), counting the minimum number of tree node edits such as node insertion, node relabel, and node deletion. Several important problems involve computing the tree edit distance under a threshold constraint, a setting we refer to as the bounded tree edit distance problem. Typical examples include threshold-based similarity search, where the goal is to find all trees within a given TED from a query tree [23], and similarity join, which aims to identify all tree pairs whose TED is below a specified threshold [9]. Due to the high computational cost of exact TED computation, the most efficient approaches adopt a filter-verify paradigm [8, 9, 15, 23]. In this approach, a fast lower-bound is first applied to eliminate pairs of trees that cannot possibly satisfy the threshold, followed by an exact verification phase that computes the TED only for the remaining candidates. A wide spectrum of lower-bound techniques for TED has been proposed [8–10, 36]. The simplest bounds exploit only tree size or label multiset statistics [10], while more advanced approaches incorporate limited structural information, for instance through binary branch representations [36], traversal-based encodings [8], or tree decompositions [9]. Among these techniques, the string edit distance (SED) lower-bound [8], obtained by linearizing trees via traversals and computing edit distance over the resulting strings, has repeatedly been shown to provide the highest pruning power [15]. However, this superior precision comes at a significant computational cost. The standard dynamic programming algorithm for SED requires quadratic time and space in the traversal length, which directly translates into quadratic complexity in the tree size. As a result, SED becomes a performance bottleneck for large tree collections or higher distance thresholds. A further limitation of existing work lies in the lack of a comprehensive and reproducible experimental comparison of stateof-the-art TED lower-bounds. Although a survey of lower-bound techniques exists [15], it primarily focuses on conceptual comparisons and asymptotic properties. Importantly, it does not consider efficient bounded implementations of SED, such as those based on Ukkonen-style algorithms, and lacks later advances in structural filtering. As a consequence, the conclusions drawn in that survey no longer reflect the current state-of-the-art. In particular, the more recent structural filter lower-bound [9] is not covered. Structural filter exploits detailed positional and hierarchical information of tree nodes and has been shown to outperform all classical lower-bounds except SED. This paper presents four key contributions to advance TED lower-bound filtering:

• We perform a comprehensive experimental comparison of state-of-the-art lower-bounds, evaluating their trade-offs in precision and cost, including efficient bounded implementations not covered in prior surveys. • We improve the efficiency of the SED lower-bound by incorporating Ukkonen’s bounded SED implementation. We demonstrate that SED-based filtering is superior to all existing lower-bound approaches when using the Ukkonen optimization, despite SED’s historically high computational cost. • Most importantly, we introduce the SED-struct threshold filter, which combines SED with axes-aware structural constraints. We prove the soundness of the filter and introduce an Ukkonen-based algorithm for its efficient bounded computation. This tailored approach achieves significantly higher precision than other filtering methods, without significant computational overhead. • We make our implementation freely available and provide a PostgreSQL extension that makes the evaluated filtering methods available directly within a database system. The axes-aware structural difference is the key technical novelty enabling the SED-struct filter. Extensive evaluation on both synthetic and real-world datasets confirms that our SED-struct filter achieves the best balance of precision and speed, making it a practical and effective component for threshold-based TED similarity search applications.

2

RELATED WORK

Research on tree edit distance (TED) has evolved along three complementary directions: exact TED algorithms, complexity-theoretic limits, and threshold-oriented filtering for similarity search and joins.

2.1

Exact TED Algorithms

Tai [31] introduced the first polynomial-time algorithm for ordered TED. Subsequent work significantly reduced practical and theoretical cost through dynamic programming refinements, including the Zhang–Shasha decomposition [37], the heavy-path decomposition of Klein [13], and robust strategy optimization in RTED (and later APTED) [23]. In 2021 Mao [18] broke the cubic barrier for unweighted version of TED using max-plus matrix product, resulting in 𝑂 (𝑛 2.9546 ). Nogler et al. [22] improved this to 𝑂 (𝑛 2.6857 ) while also proving fine-grained equivalence to APSP. To bridge the gap between these theoretical bounds and practical large-scale applications, Fan et al. [7] introduced X-TED, a GPU-accelerated execution framework that employs dependency-driven preprocessing and adaptive scheduling for dynamic programming tasks, significantly enhancing throughput and memory efficiency for extensive TED workloads.

2.2

Bounded Tree Edit Distance

In many scenarios, the exact distance value is secondary to a simple binary check: whether TED between 𝑇1 and 𝑇2 is lower than a given threshold 𝜏. This requirement motivated bounded TED algorithms parameterized by 𝜏, which aim for a running time of 𝑂 (𝑛 + poly(𝜏)).

These methods are significantly more efficient than standard approaches when the threshold 𝜏 is much smaller than the tree size 𝑛. Touzet [34] introduced the first such algorithm with a complexity of 𝑂 (𝑛𝜏 3 ). Akmal et al. [1] later reduced this to 𝑂 (𝑛𝜏 2 log 𝑛) for unweighted tree edit distance. Das et al. [5] reached a major milestone by achieving a running time of 𝑂˜ (𝑛 + poly(𝜏)). Most recently, Kociumaka and Shahali [14] further improved both weighted and unweighted settings, proving a runtime of 𝑂 (𝑛 + 𝑘 6 log 𝑘). While these theoretical results show that small 𝜏 values allow for much faster computation than the general 𝑂 (𝑛 3 ) baseline, many of these advancements have yet to be fully realized in practice. For real-world applications, the TopDiff algorithm by Pawlik and Augsten [24] remains the current state-of-the-art.

2.3

TED Lower-bounds for Search and Join

Bounded retrieval typically follows a filter-and-verify paradigm: compute cheap lower-bounds first, then run exact TED only on surviving candidates [9, 15]. Early lower-bounds use coarse statistics such as size and label overlap [10]. Tighter lower-bounds exploit structural signals, including binary-branch representations [36] and traversal-based string encodings [8]. While the 𝑝𝑞-gram distance [2] is another fast way to filter trees, it only serves as a lower-bound for fanout-weighted TED and is therefore inapplicable to the widely used TED studied in this paper. Prior comparative studies consistently report that the SED lower-bound achieves the highest precision, but at the highest computational cost [15]. Recent work has also improved the scalability of candidate generation itself. Karpov and Zhang [11] introduce SyncSignatures, a signature framework that enables efficient parallel candidate generation via hash joins, substantially outperforming legacy single-threaded tree similarity join pipelines. In addition, dedicated index structures for subtree similarity search have broadened the practical scope of TED-based retrieval, enabling efficient discovery of matching hierarchical fragments in large forests. This cost-quality trade-off motivates bounded SED implementations (e.g., Ukkonen-style pruning [35]) and drives our focus on improving both efficiency and tightness. Relative to prior surveys [15] and recent structural filters [9], we provide an updated empirical comparison and contribute an enhanced SED-based filter that combines bounded SED computation with additional structural information. All empirical comparisons and evaluations in this paper use the unweighted (unit-cost) variant of TED.

3

PROBLEM DEFINITION

A tree 𝑇 is a rooted, directed acyclic graph with a node set 𝑁 (𝑇 ) and an edge set 𝐸 (𝑇 ) ⊆ 𝑁 (𝑇 ) × 𝑁 (𝑇 ). The tree has a root(𝑇 ). Since 𝑇 is ordered, each node 𝑢 ∈ 𝑁 (𝑇 ) induces four disjoint subsets of 𝑁 (𝑇 ). These subsets are shown in Figure 1, where we consider the node 𝑏 1 . Specifically, we are interested in the sizes of these subsets: • a(𝑏 1 ) – the number of ancestors of 𝑏 1 , • f (𝑏 1 ) – the number of following nodes of 𝑏 1 , • d (𝑏 1 ) – the number of descendants of 𝑏 1 , • p(𝑏 1 ) – the number of preceding nodes of 𝑏 1 .

Binary branch lower-bound, and the Traversal String lower-bound (also known as the String Edit Distance lower-bound or SED lowerbound).

4.1

Size Lower-Bound

The simplest lower-bound for TED is based on the sizes of the trees. Intuitively, if one tree has more nodes than another, at least the difference in node count must be accounted for by edit operations (insertions or deletions). Definition 1 (Size Lower-Bound). 𝐿𝐵𝑠𝑖𝑧𝑒 (𝑇1,𝑇2 ) = ||𝑇1 | − |𝑇2 || Figure 1: Disjoint subsets for 𝑏 1

Every node 𝑢 has a structural vector svafdp (𝑢) = (𝑎(𝑢), 𝑓 (𝑢), 𝑑 (𝑢), 𝑝 (𝑢)) We sometimes call svafdp (𝑢) a complete structural vector since it considers all four relationship axes. In addition, for any subset of axes, we may define a partial structural vector. For example, svaf (𝑢) = (𝑎(𝑢), 𝑓 (𝑢)),

svdp (𝑢) = (𝑑 (𝑢), 𝑝 (𝑢)).

Partial structural vectors allow the capture of only selected relationship axes of a node. These structural vectors play a central role in the structural filter (Section 4) and in our SED-struct threshold filter (Section 5). Every node 𝑢 has a label 𝑙𝑏𝑙 (𝑢). |𝑇 | denotes the number of nodes in a tree 𝑇 . Let 𝛿 (𝑇1,𝑇2 ) denote the tree edit distance between trees 𝑇1 and 𝑇2 . It is defined as the minimum number of operations required to transform 𝑇1 into 𝑇2 . The allowed operations are: • insert (𝑢, 𝑣, 𝑆) – insert a node 𝑢 as a child of node 𝑣, making a consecutive subsequence 𝑆 of 𝑣’s children the children of 𝑢 (preserving order), • delete(𝑢) – delete node 𝑢 and reattach its children to the parent of 𝑢 (preserving order), • relabel(𝑢, ℓ) – change the label of node 𝑢 to ℓ. Example 1 (Tree edit distance). Consider trees in Figure 2. The dashed lines between T1 and T2 show one optimal edit mapping: the four node pairs 𝑎 1 ↔𝑎 1 , 𝑎 2 ↔𝑎 2 , 𝑎 3 ↔𝑎 3 , and 𝑎 4 ↔𝑎 4 are matched with identical labels (cost 0 each). The remaining nodes 𝑏 1 and 𝑎 5 in T1 are deleted, while 𝑏 1 and 𝑎 5 in T2 are inserted, giving a total cost of 4. The tree edit distance between T1 and T2 is therefore 𝛿 (𝑇 1,𝑇 2) = 4, whereas 𝛿 (𝑇 1,𝑇 3) = 1.

4

LOWER-BOUND FOR TREE EDIT DISTANCE

In computing the edit distance between trees, many tree pairs can be quickly ruled out as dissimilar using lower-bounds before performing any expensive exact TED computation. A lower-bound computes a cheap approximation that is guaranteed to be no greater than the true tree edit distance (TED); if this lower-bound exceeds a given threshold, the pair can be safely pruned. We discuss several fundamental lower-bounds for TED, following established terminology: the Size lower-bound, the Intersection lower-bound, the

It can be computed in 𝑂 (1) time given the size of the trees, which makes it extremely fast, and we use it as the first lowerbound before any other one. However, it is often not very selective, since it ignores both the labels and the structural arrangement of the trees.

4.2

Label intersection Lower-Bound

A more refined lower-bound incorporates information on node labels. The label intersection lower-bound [10] is based on the idea that if a node label appears in one tree but not the other, that mismatch will force at least one edit operation (either inserting a missing node, deleting an extra node, or renaming a mismatched node). We can formalise this by looking at the multiset of node labels in each tree and counting the overlap. Definition 2 (Label intersection Lower-Bound). Let 𝐿1 and 𝐿2 be the multisets of node labels in trees 𝑇1 and 𝑇2 , respectively. 𝐿𝐵𝑖𝑛𝑡 (𝑇1,𝑇2 ) = 𝑚𝑎𝑥 {|𝑇1 |, |𝑇2 |} − |𝐿1 ∩ 𝐿2 | where 𝐿1 ∩𝐿2 is the multiset intersection (common label occurrences in both trees). This lower-bound clearly improves upon the size bound by considering node labels. Nevertheless, the intersection lower-bound can still be quite coarse: it completely ignores tree structure beyond label frequencies. For example, assuming the trees in Figure 2, the 𝐿𝐵𝑖𝑛𝑡 (𝑇 1,𝑇 2) = 0 whereas 𝐿𝐵𝑖𝑛𝑡 (𝑇 1,𝑇 3) = 1 suggests that the TED between T1 and T2 is lower than the TED between T1 and T3. However, it is the other way around, as mentioned in Example 1.

4.3

Binary Branch Lower-Bound

The binary branch lower-bound [36] incorporates local structure by transforming a tree 𝑇 into its binary left-child, right-sibling representation 𝐵𝑇 . Each node 𝑢 induces a branch BB(𝑢) = (𝑢, 𝑢𝑙 , 𝑢𝑟 ), where a missing left or right child is represented by 𝜖. Let BBV(𝑇 ) = (𝑏 1, . . . , 𝑏 𝑁 ) count occurrences of the 𝑁 distinct branches in the ′ ), dataset. For trees with vectors (𝑏 1, . . . , 𝑏 𝑁 ) and (𝑏 1′ , . . . , 𝑏 𝑁 BBDist(𝑇1,𝑇2 ) =

𝑁 ∑︁

|𝑏𝑖 − 𝑏𝑖′ | ≤ 5 𝛿 (𝑇1,𝑇2 ).

𝑖=1

Thus, BBDist(𝑇1,𝑇2 )/5 is a TED lower-bound. It is computable in 𝑂 (𝑛) time but is generally loose.

T1

T2

T3

Figure 2: Sample trees

4.4

String Edit Distance (SED) Lower-Bound

Another way to incorporate structural information is to linearize the trees into sequences of labels via a traversal, and then compare these sequences using string edit distance. The SED lower-bound [8] uses this approach: it converts each tree into a sequence (string) of node labels by performing a tree traversal (more on possible tree traversals in Section 5.1), and then computes the classic string edit distance [20] between the two resulting sequences. The key observation is that any edit operation on the tree will induce at most one edit operation on a traversal string of that tree. Therefore, the SED between the traversal strings will never exceed the edit distance between the trees. In formula form:

Definition 3 (SED Lower-Bound). Let pre(𝑇 ) and post(𝑇 ) denote the preorder and postorder traversal strings of tree 𝑇 , respectively (i.e., sequences of node labels obtained by listing nodes in preorder or postorder). Let SED(𝑆 1, 𝑆 2 ) be the standard string edit distance between sequences 𝑆 1 and 𝑆 2 . The SED lower-bound for two trees 𝑇1 and 𝑇2 is defined as:

prefixes 𝑆 1 [1..𝑖] and 𝑆 2 [1..𝑗]. The recursion is given by   0, 𝑖 = 𝑗 = 0,     𝑖, 𝑗 = 0,     𝑗,  𝑖 = 0, 𝐷 [𝑖, 𝑗] =  min{𝐷 [𝑖 − 1, 𝑗] + 1,     𝐷 [𝑖, 𝑗 − 1] + 1,  otherwise.     𝐷 [𝑖 − 1, 𝑗 − 1] + 1 }, 𝑆 1 [𝑖 ]≠𝑆 2 [ 𝑗 ]  The SED(𝑆 1, 𝑆 2 ) = 𝐷 [𝑚, 𝑛]. Although computing an SED with an edit distance matrix is 𝑂 (𝑛 · 𝑚) in the length of the sequences, this is still far cheaper than an exact tree edit distance computation in many cases (exact TED algorithms are often exponential or high-polynomial in the worst case). The SED lower-bound thus strikes a balance between tightness of the bound (by preserving some structural information) and efficiency of computation, making it a powerful tool in tree similarity queries. Example 2 (SED lower-bound). Consider the trees 𝑇1 and 𝑇2 from Figure 2. The preorder traversal strings are: pre(𝑇1 ) = a1 a2 a3 b1 a4 a5 pre(𝑇2 ) = a1 a2 a3 b1 a4 a5 Hence,

𝐿𝐵𝑆𝐸𝐷 (𝑇1,𝑇2 ) = 𝑚𝑎𝑥 {𝑆𝐸𝐷 (𝑝𝑟𝑒 (𝑇1 ), 𝑝𝑟𝑒 (𝑇2 )), 𝑆𝐸𝐷 (𝑝𝑜𝑠𝑡 (𝑇1 ), 𝑝𝑜𝑠𝑡 (𝑇2 ))}

SED(pre(𝑇1 ), pre(𝑇2 )) = 0. The postorder traversal strings are: post(𝑇1 ) = a3 a4 b1 a2 a5 a1 post(𝑇2 ) = b1 a3 a4 a5 a2 a1

Taking the maximum over both preorder and postorder traversals is important. A single traversal can sometimes miss structural differences – for instance, two distinct trees might yield identical preorder strings (SED = 0) even though their TED is non-zero, as long as their nodes appear in a coincident order by chance. In such cases, the postorder strings will typically differ and provide a non-zero edit distance. Thus, using both traversals ensures a more robust lower-bound. The standard dynamic programming computation of SED constructs an edit distance matrix 𝐷 ∈ N (𝑚+1) × (𝑛+1) , where 𝑚 = |𝑆 1 | and 𝑛 = |𝑆 2 |. Entry 𝐷 [𝑖, 𝑗] stores the edit distance between the

The corresponding dynamic-programming matrix is: − 𝑎3 𝑎4 𝑏1 𝑎2 𝑎5 𝑎1

− 0 1 2 3 4 5 6

𝑏1 1 1 2 2 3 4 5

𝑎3 2 1 1 2 2 3 4

𝑎4 3 2 1 2 2 2 3

𝑎5 4 3 2 2 2 2 2

𝑎2 5 4 3 3 2 2 2

𝑎1 6 5 4 4 3 2 2

Therefore, SED(post(𝑇1 ), post(𝑇2 )) = 𝐷 [6, 6] = 2,

Only 𝜏-valid label match node pairs can participate in an edit mapping of cost at most 𝜏. This motivates the following definition.

Since the preorder distance is zero, 𝐿𝐵 SED (𝑇1,𝑇2 ) = 2 and, consequently, 𝛿 (𝑇1,𝑇2 ) ≥ 2.

Definition 8 (𝜏-valid label intersection). For trees 𝑇1,𝑇2 and threshold 𝜏, the 𝜏-valid label intersection is

The SED lower-bound forms the foundation for our enhanced approach. In Section 5, we discuss algorithmic optimizations (including tree traversal strategies and bounded SED computation via Ukkonen’s algorithm) and introduce the SED-struct threshold filter, which augments SED with structural constraints.

|𝑁 (𝑇1 ) ∩𝜏 𝑁 (𝑇2 )| = max{|𝑃 |},

4.5

Structural Filter

Another type of TED lower-bound that combines information about structure and labels is the structural filter [9]. Its definition builds upon the notion of an edit mapping. Definition 4 (Edit Mapping). Let 𝑇1,𝑇2 be two ordered labeled trees. An edit mapping 𝑀 ⊆ 𝑁 (𝑇1 ) × 𝑁 (𝑇2 ) is a set of node pairs (𝑣, 𝑤) such that: • One-to-one: 𝑣 = 𝑣 ′ iff 𝑤 = 𝑤 ′ for any (𝑣, 𝑤), (𝑣 ′, 𝑤 ′ ) ∈ 𝑀. • Ancestor preservation: 𝑣 is ancestor of 𝑣 ′ iff 𝑤 is ancestor of 𝑤 ′ . • Order preservation: 𝑣 is to the left of 𝑣 ′ iff 𝑤 is to the left of 𝑤 ′. Definition 5 (Edit-Mapping Cost). Let 𝑀1 = {𝑣 | (𝑣, 𝑤) ∈ 𝑀 } and 𝑀2 = {𝑤 | (𝑣, 𝑤) ∈ 𝑀 } be the projections of an edit mapping 𝑀. Under unit edit costs, its cost is ∑︁ cost(𝑀) = |𝑁 (𝑇1 ) \ 𝑀1 | + |𝑁 (𝑇2 ) \ 𝑀2 | + 1𝑙𝑏𝑙 (𝑣)≠𝑙𝑏𝑙 (𝑤 ) . (𝑣,𝑤 ) ∈𝑀

The first two terms count deletions and insertions, respectively, and the last term counts relabelings. The standard edit-mapping characterization of TED gives 𝛿 (𝑇1,𝑇2 ) = min cost(𝑀), 𝑀

where the minimum ranges over all edit mappings between 𝑇1 and 𝑇2 . A central idea is that only specific node pairs can belong to a valid mapping under a given threshold. Definition 6 (Structural Difference). Let 𝑣 ∈ 𝑁 (𝑇1 ) and 𝑤 ∈ 𝑁 (𝑇2 ). The structural difference between 𝑣 and 𝑤 is defined as the 𝐿1 distance between their structural vectors: Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑣, 𝑤) = 𝑠𝑣 𝑎𝑓 𝑑𝑝 (𝑣) − 𝑠𝑣 𝑎𝑓 𝑑𝑝 (𝑤) 1 , Note that the subscript 𝑎𝑓 𝑑𝑝 denotes the set of relationship axes taken into account when computing the structural difference. The structural filter is defined with all four axes (i.e. it uses complete structural vectors). Still, in Section 5 we demonstrate that considering only a subset of axes can be advantageous when combined with the SED lower-bound. Definition 7 (𝜏-valid node pair). Let 𝑇1,𝑇2 be two trees and 𝜏 a distance threshold. A node pair (𝑣, 𝑤) ∈ 𝑁 (𝑇1 ) × 𝑁 (𝑇2 ) is called 𝜏-valid if Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑣, 𝑤) ≤ 𝜏 . If additionally lbl(𝑣) = lbl(𝑤), then (𝑣, 𝑤) is called a 𝜏-valid label match.

𝑃

where 𝑃 is a one-to-one mapping between nodes of 𝑇1 and 𝑇2 such that all pairs in 𝑃 are 𝜏-valid label matches. Hütter et al. [9] describe an efficient algorithm for 𝜏-valid label intersection search for a pair of trees; the implementation relaxes the strict one-to-one mapping to favour runtime at the cost of slightly looser bounds. For details, see their paper. Definition 9 (Structural Filter). For any two trees 𝑇1,𝑇2 and threshold 𝜏,
𝐿𝐵𝑠𝑡𝑟𝑢𝑐𝑡 (𝑇1,𝑇2, 𝜏) = max |𝑇1 |, |𝑇2 | − |𝑁 (𝑇1 ) ∩𝜏 𝑁 (𝑇2 )|. Example 3 (Structural filter). Figure 3 contains trees T1 and T2 with structural vectors. We want to know whether their TED can be two or less; therefore, we compute 𝐿𝐵𝑠𝑡𝑟𝑢𝑐𝑡 (𝑇 1,𝑇 2, 2). The most important step is to find 𝜏-valid label intersection for 𝜏 = 2. We compute structural difference between nodes with the same labels and find the following 2-valid label intersection: (𝑎 1, 𝑎 1 ), (𝑎 2, 𝑎 2 ), (𝑎 3, 𝑎 3 ), (𝑎 4, 𝑎 4 ), (𝑎 5, 𝑎 5 ). Clearly, the 𝐿𝐵𝑠𝑡𝑟𝑢𝑐𝑡 (𝑇 1,𝑇 2, 2) = 1 and the structural filter pass the 𝜏 = 2 threshold.

5

SED-STRUCT THRESHOLD FILTER

The SED lower-bound is a highly robust method that achieves precision close to one across many real-world collections. However, in some collections, the structural variability of trees is higher, and the precision decreases. In this section, we introduce the SED-struct threshold filter, which augments SED with axes-aware structural constraints to achieve better precision in such cases. The computational overhead of the SED-struct filter is minimal relative to SED, making it the first usable filter of this kind that outperforms SED. Let us begin by reviewing the key algorithmic enhancements that form the foundation of the SED-struct filter.

5.1

Tree Traversal

There are several different ways to linearize the tree into a sequence of labels. In this article we recognise a total of four traversals: • Preorder (pre) • Postorder (post) • Reverse preorder (rpre) • Reverse postorder (rpost) Here, reverse preorder and reverse postorder visit siblings from right to left, while retaining the root-before-descendants and rootafter-descendants conventions, respectively. For each traversal, two relationship axes occur before a node and the complementary two occur after it, as summarized in Table 1. Definition 10 (Traversal-Specific Axis Set). For a traversal order 𝑇𝑇 , let 𝑋𝑇𝑇 be the pair of relationship axes occurring after a

T1

T2

Figure 3: Sample trees from Figure 2 with afdp structural vectors Table 1: Relationship axes before and after a node for each traversal 𝑇𝑇 pre post rpre rpost

Axes before the node 𝑎𝑝 𝑑𝑝 𝑎𝑓 𝑑𝑓

Axes after the node 𝑑𝑓 𝑎𝑓 𝑑𝑝 𝑎𝑝

node in 𝑇𝑇 . Formally,

𝑋𝑇𝑇 =

 𝑑𝑓 ,     𝑎𝑓 ,   𝑑𝑝,    𝑎𝑝, 

if 𝑇𝑇 is preorder, if 𝑇𝑇 is postorder, if 𝑇𝑇 is reverse preorder, if 𝑇𝑇 is reverse postorder.

Since an edit mapping preserves ancestor relationships and leftto-right order, mapped nodes occur in the same relative order in both traversal sequences for each of the four traversals. In Section 6.4, we show that the combination of pre and post does not always have to be the best option.

5.2

Ukkonen SED Algorithm

One possibility of optimizing expensive edit distance matrix computation is applying the Ukkonen SED algorithm [4, 35], which takes advantage of a given distance threshold 𝜏 and focuses only on the diagonal strip. This transformed approach utilizes diagonal indexes 𝑘, which are mapped from the matrix coordinates: 𝑘 = 𝑗 − 𝑖. The main diagonal (also referred to as 0th diagonal) corresponds to 𝑘 = 0, the diagonal above it corresponds to 𝑘 = 1, the one below it corresponds to 𝑘 = −1, and so on. We use the extension of Ukkonen’s algorithm introduced by Berghel and Roach [4]. Their adjustment allows the algorithm to more precisely track the minimal-cost path within the dynamic programming matrix. If string 𝑆 1 has length 𝑚 and string 𝑆 2 has length 𝑛 (where 𝑚 ≥ 𝑛), their SED is at least 𝑚 − 𝑛. The diagonal terminating at the lower-right entry of the 𝐷 matrix is called the target diagonal. The key idea is that an optimal alignment between 𝑆 1 and 𝑆 2 cannot deviate from the target diagonal by more than 𝜏. Hence, only the diagonals 𝑘 ∈ ⟨−𝜏 + (𝑚 − 𝑛), 𝜏 + (𝑚 − 𝑛)⟩ need to

be maintained. This method is further refined by the minimizing path condition. Algorithm 1 presents the pseudocode of the extended Ukkonen’s algorithm. Definition 11 (Ukkonen Matrix). Let 𝐶 ∈ Z (𝜏+1) × (2𝜏+1) be the matrix used in Ukkonen’s algorithm. Its row index 𝑝 ∈ {0, . . . , 𝜏 } is an edit budget, and its column index 𝑘 ∈ {−𝜏, . . . , 𝜏 } identifies the diagonal 𝑘 = 𝑖 − 𝑗 of the SED matrix. Entry 𝐶 [𝑝, 𝑘] stores the largest 𝑋 such that the prefixes 𝑆 1 [1..𝑋 +𝑘] and 𝑆 2 [1..𝑋 ] can be transformed into each other using at most 𝑝 edits. Thus, 𝑋 is the consumed prefix length of 𝑆 2 , while 𝑋 + 𝑘 is the consumed prefix length of 𝑆 1 . The target diagonal is 𝑘 = 𝑚 − 𝑛. The algorithm terminates successfully when 𝐶 [𝑝, 𝑚 − 𝑛] = 𝑛, equivalently when 𝑋 = |𝑆 2 | and 𝑋 + 𝑘 = |𝑆 1 |, which confirms that SED(𝑆 1, 𝑆 2 ) ≤ 𝜏. The minimizing path condition states that for every row 𝑝 ′ ∈ ⟨0; 𝜏⟩ we only need to compute diagonals 𝑘, which satisfy the following inequality: 𝜏 ≥ 𝑝 ′ + |𝑚 − 𝑛 − 𝑘 | At low values of 𝑝 ′ we know that we only need to compute diagonals 𝑘 ∈ ⟨𝑝 ′, 𝑝 ′ + 1). However, as 𝑝 ′ increases, the minimizing path condition progressively restricts the search space, narrowing the range of diagonals that must be considered. Hence we compute 𝑘𝑠 (starting diagonal) and 𝑘𝑒 (ending diagonal) in Algorithm 1 on lines 6 and 7, respectively. Intuitively, line 9 in Algorithm 1 accounts for a substitution, insertion, or deletion, and lines 10 and 11 extend the match greedily along the diagonal. The algorithm runs in 𝑂 (𝜏 · min(|𝑆 1 |, |𝑆 2 |)) time and 𝑂 (𝜏) space, providing a substantial improvement over the quadratic dynamic programming algorithm. Example 4 (Ukkonen SED Algorithm). Let us apply Ukkonen’s bounded SED algorithm (Algorithm 1) to the trees from Example 2 linearized by the postorder: 𝑆 1 = post(𝑇1 ) = a3 a4 b1 a2 a5 a1 𝑆 2 = post(𝑇2 ) = b1 a3 a4 a5 a2 a1 We choose the threshold 𝜏 = 2, since the edit distance between the two sequences was computed as 2.

Algorithm 1: Ukkonen Bounded String Edit Distance Input: Strings 𝑆 1 and 𝑆 2 , threshold 𝜏 Output: Boolean value whether SED(𝑆 1, 𝑆 2 ) ≤ 𝜏 1 𝑚 = |𝑆 1 | ; 2 𝑛 = |𝑆 2 | ; 3 𝑘 = 𝑚 − 𝑛 ; // 𝑚 ≥ 𝑛 4 for 𝑗 ← −𝜏 to 𝜏 do 𝐶 [−1, 𝑗] ← −1; 5 for 𝑝 ← 0 to 𝜏 do 6 𝑘𝑠 = 𝑚𝑎𝑥 (−𝑝, 𝑘 − (𝜏 − 𝑝)) ; 7 𝑘𝑒 = 𝑚𝑖𝑛(𝑝, 𝑘 + (𝜏 − 𝑝)) ; 8 for 𝑘 ′ ← 𝑘𝑠 to 𝑘𝑒 do 𝑋 ← max{𝐶 [𝑝 − 1, 𝑘 ′ − 1], 𝐶 [𝑝 − 1, 𝑘 ′ ] + 1,

9

5.3

Structural Difference

The structural filter introduced by Hutter et al. [9] uses the concept of structural difference to determine which node pairs can feasibly be matched within a given edit distance threshold. Definition 6 formalizes this concept. While Hutter’s approach uses the complete structural difference across all axes, our approach generalizes this by restricting to a subset of axes that is optimal for a given traversal order. This yields an axes-aware variant: Definition 12 (Structural Difference (Axes-Aware Variant)). For a subset of axes 𝑋 ⊆ {𝑎, 𝑑, 𝑓 , 𝑝}, the axes-aware structural difference is: 𝑋 Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑣, 𝑤) = ∥ 𝑠𝑣 𝑋 (𝑣) − 𝑠𝑣 𝑋 (𝑤) ∥ 1 ,

;

′

10 11 12 13 14

15

𝐶 [𝑝 − 1, 𝑘 + 1] + 1} while 𝑆 1 [𝑋 + 𝑘 ′ + 1] = 𝑆 2 [𝑋 + 1] do 𝑋 ←𝑋 +1; 𝐶 [𝑝, 𝑘 ′ ] ← 𝑋 ; if 𝑋 = 𝑛 and 𝑘 ′ = 𝑘 then return true; return false;

𝑝\𝑘 −1 0 1 2

−1 −1 − 1 −

0 −1 0 2 6

1 −1 − 2 −

Figure 4: Ukkonen matrix 𝐶 for our running example

The algorithm maintains a matrix 𝐶 [𝑝, 𝑘] of maximal prefix matches along diagonals. Initialization and subsequent updates produce the Ukkonen matrix 𝐶 in Figure 4 The target diagonal is determined by the length difference 𝑘 = 𝑚 − 𝑛 = 0. Hence, the algorithm ultimately checks whether the alignment on this diagonal reaches the end of the sequence. Consider the value 𝐶 [2, 0]. According to Algorithm 1, line 9 initializes 𝑋 from the three predecessor diagonals:

𝑋 = max{𝐶 [1, −1], 𝐶 [1, 0] + 1, 𝐶 [1, 1] + 1}. Using the values from the previous row of the matrix we obtain 𝑋 = 3. Then, lines 10–11 extend the match greedily along the same diagonal, incrementing 𝑋 while 𝑆 1 [𝑋 + 1] = 𝑆 2 [𝑋 + 𝑗 + 1]. In this case the suffixes match completely, so 𝑋 increases until 𝑋 = 6, yielding 𝐶 [2, 0] = 6. Thus, Ukkonen’s algorithm result states that the SED can be lower or equal to 2, which is consistent with the full dynamic-programming computation in Example 2. However this algorithm uses only 𝑂 (𝜏) space and 𝑂 (𝜏 · min(|𝑆 1 |, |𝑆 2 |)) time.

For the selected traversal 𝑇𝑇 , the SED-struct filter instantiates the axes-aware structural difference with the traversal-specific axis 𝑋𝑇𝑇 set 𝑋𝑇𝑇 from Definition 10, that is, it uses Δ𝑠𝑡𝑟𝑢𝑐𝑡 . The axes-aware variant allows us to combine structural differences with specific traversal orders, providing tighter bounds. For instance, a preorder traversal processes nodes in a depth-first manner, encoding ancestor and preceding axes in the sequence. By restricting the structural difference to the axes not encoded by the traversal (descendants and followers for preorder), we capture only the structural constraints that the traversal order does not already enforce, leading to improved lower-bound precision without significant computational overhead.

5.4

Combining SED with Structural Constraints

Now we introduce the SED-struct filter, which combines the SED lower-bound with axes-aware structural constraints to achieve better precision. We first define the numerical score used by the filter. Definition 13 (SED-struct Score). Let 𝑆 1 and 𝑆 2 be linearized node sequences of trees 𝑇1 and 𝑇2 obtained by a tree traversal 𝑇𝑇 , and let 𝜏 be a distance threshold. The SED-struct score is defined by a dynamic-programming matrix 𝐷𝜏 , where entry 𝐷𝜏 [𝑖, 𝑗] stores the guarded edit score between prefixes 𝑆 1 [1..𝑖] and 𝑆 2 [1..𝑗]. The recursion is given by   0, 𝑖 = 𝑗 = 0,      𝑖, 𝑗 = 0,      𝑗,  𝑖 = 0, 𝐷𝜏 [𝑖, 𝑗] =   min{𝐷𝜏 [𝑖 − 1, 𝑗] + 1,      𝐷𝜏 [𝑖, 𝑗 − 1] + 1, otherwise,     𝐷 [𝑖 − 1, 𝑗 − 1] + 𝑐 }, 𝜏 𝑖,𝑗  where structural guard 𝑋𝑇𝑇   ∞, if Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑥𝑖 , 𝑦 𝑗 ) + 𝐷𝜏 [𝑖 − 1, 𝑗 − 1] > 𝜏,     𝑐𝑖,𝑗 = 0, if 𝑙𝑏𝑙 (𝑥𝑖 ) = 𝑙𝑏𝑙 (𝑦 𝑗 ),     1, otherwise,  , 𝑋𝑇𝑇 is the traversal-specific axis set and 𝑥𝑖 , and 𝑦 𝑗 is a node in 𝑆 1 , and 𝑆 2 respectively. The SED-struct score is SED-struct(𝑆 1, 𝑆 2, 𝜏) = 𝐷𝜏 [𝑚, 𝑛], where 𝑚 = |𝑆 1 | and 𝑛 = |𝑆 2 |.

Lemma 5.1 (Prefix–Complement Accounting). Let 𝑀 be an edit mapping, let (𝑥𝑖 , 𝑦 𝑗 ) ∈ 𝑀, and let 𝐴𝑀 be the alignment induced by 𝑀 under traversal 𝑇𝑇 . If 𝑞 is the cost of the prefix of 𝐴𝑀 immediately before the diagonal step matching 𝑥𝑖 to 𝑦 𝑗 , then 𝑋𝑇𝑇 𝑞 + Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑥𝑖 , 𝑦 𝑗 ) ≤ cost(𝑀).

Proof. By the traversal-axis correspondence in Table 1, the alignment prefix consumes exactly the nodes before 𝑥𝑖 and 𝑦 𝑗 . Its cost 𝑞 counts the unmatched nodes there and the label mismatches of mapped pairs there. Having an axis 𝑧 ∈ 𝑋𝑇𝑇 , and let 𝑟𝑧 be the number of pairs in 𝑀 whose first and second components lie on axis 𝑧 of 𝑥𝑖 and 𝑦 𝑗 , respectively. Because 𝑀 contains (𝑥𝑖 , 𝑦 𝑗 ) and preserves ancestor and order relationships, every mapped node on axis 𝑧 of either node is paired with a node on the same axis of the other node. Consequently, |𝑧 (𝑥𝑖 ) − 𝑧 (𝑦 𝑗 )| ≤ (𝑧(𝑥𝑖 ) − 𝑟𝑧 ) + (𝑧 (𝑦 𝑗 ) − 𝑟𝑧 ), where the right-hand side counts nodes on these two axes that are unmatched by 𝑀. The axes in 𝑋𝑇𝑇 are disjoint, so summing 𝑋𝑇𝑇 this inequality over them shows that Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑥𝑖 , 𝑦 𝑗 ) is at most the number of unmatched nodes on the axes after 𝑥𝑖 and 𝑦 𝑗 . These nodes are disjoint from all edit costs counted by 𝑞. Both sets of costs are included in cost(𝑀), proving the claim. □ Theorem 5.2 (Soundness of the SED-struct Threshold Filter). Under the unit-cost edit model, let𝑇𝑇 be one of the four traversal orders, and let 𝑆𝑟 = 𝑇𝑇 (𝑇𝑟 ) for 𝑟 ∈ {1, 2}. For every 𝜏 ∈ N0 , SED(𝑆 1, 𝑆 2 ) ≤ SED-struct(𝑆 1, 𝑆 2, 𝜏) 𝛿 (𝑇1,𝑇2 ) ≤ 𝜏

=⇒

≤ 𝛿 (𝑇1,𝑇2 ) ≤ 𝜏 .

In particular, SED-struct(𝑆 1, 𝑆 2, 𝜏) > 𝜏

=⇒

𝛿 (𝑇1,𝑇2 ) > 𝜏 .

Proof. Put 𝑑 = 𝛿 (𝑇1,𝑇2 ) and suppose that 𝑑 ≤ 𝜏. Let 𝐷 denote the ordinary SED dynamic-programming matrix and write ℓ𝑖,𝑗 = 1𝑙𝑏𝑙 (𝑥𝑖 )≠𝑙𝑏𝑙 (𝑦 𝑗 ) for its diagonal cost. First, 𝐷𝜏 [𝑖, 𝑗] ≥ 𝐷 [𝑖, 𝑗] for all 𝑖, 𝑗. The boundary entries agree. For an interior entry, assuming the inequality for its three predecessors, the SED-struct recurrence can only replace the ordinary diagonal cost ℓ𝑖,𝑗 by ∞; monotonicity of min therefore proves the inequality by induction on 𝑖 + 𝑗. Consequently, SED(𝑆 1, 𝑆 2 ) ≤ SED-struct(𝑆 1, 𝑆 2, 𝜏). Let 𝑀 be an optimal edit mapping, so cost(𝑀) = 𝑑. Since edit mappings preserve traversal order, 𝑀 induces an alignment 𝐴 of 𝑆 1 and 𝑆 2 : unmatched nodes yield horizontal or vertical steps, and each matched pair yields a diagonal step whose cost is 0 or 1 according to its labels. Hence, cost(𝐴) = 𝑑. Next, consider prefixes of 𝐴. For a prefix ending at (𝑖, 𝑗) with cost 𝑞, let the invariant be that all of its steps are admitted by the SED-struct recurrence and that 𝐷𝜏 [𝑖, 𝑗] ≤ 𝑞. The base case is the empty prefix: it ends at (0, 0), has cost 0, and satisfies 𝐷𝜏 [0, 0] = 0. For the induction step, let a prefix ending at (𝑖 ′, 𝑗 ′ ) have cost 𝑞 and satisfy the invariant. If the next alignment step consumes only one node, then it is horizontal or vertical, which is always admitted, and the recurrence gives 𝐷𝜏 [𝑖, 𝑗] ≤ 𝐷𝜏 [𝑖 ′, 𝑗 ′ ] + 1 ≤ 𝑞 + 1. This is the cost of the extended prefix.

It remains to consider a diagonal step, for which (𝑖 ′, 𝑗 ′ ) = (𝑖 − 1, 𝑗−1) and (𝑥𝑖 , 𝑦 𝑗 ) ∈ 𝑀. Its extended-prefix cost is 𝑞+ℓ𝑖,𝑗 . Lemma 5.1 gives 𝑋𝑇𝑇 𝑞 + Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑥𝑖 , 𝑦 𝑗 ) ≤ 𝑑. The induction hypothesis is 𝐷𝜏 [𝑖 − 1, 𝑗 − 1] ≤ 𝑞. Combining it with the preceding inequality yields the guard condition 𝑋𝑇𝑇 𝑋𝑇𝑇 𝐷𝜏 [𝑖 − 1, 𝑗 − 1] + Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑥𝑖 , 𝑦 𝑗 ) ≤ 𝑞 + Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑥𝑖 , 𝑦 𝑗 ) ≤ 𝑑 ≤ 𝜏 .

Thus the guard does not block this diagonal, so 𝑐𝑖,𝑗 = ℓ𝑖,𝑗 . The recurrence then establishes the induction conclusion for the extended prefix: 𝐷𝜏 [𝑖, 𝑗] ≤ 𝐷𝜏 [𝑖 − 1, 𝑗 − 1] + ℓ𝑖,𝑗 ≤ 𝑞 + ℓ𝑖,𝑗 . By induction, the invariant holds for all prefixes of 𝐴. For the full alignment, this gives SED-struct(𝑆 1, 𝑆 2, 𝜏) = 𝐷𝜏 [𝑚, 𝑛] ≤ cost(𝐴) ≤ 𝑑. Combining the two inequalities proves the first statement; the second follows by contraposition. □ Guard Semantics. The structural guard is a necessary feasibility test, not a sufficient one. By Theorem 5.2, it never blocks the diagonal step of an edit mapping whose total cost is at most 𝜏. Conversely, if the guard blocks a diagonal step, that step may be discarded when searching for an edit mapping of cost at most 𝜏. Passing the guard does not by itself establish that the two nodes can be matched within 𝜏, since label, order, and other structural constraints may still make the full mapping infeasible. The guard becomes progressively tighter as the alignment cost grows: early in the alignment, when 𝐷𝜏 [𝑖 − 1, 𝑗 − 1] is small, a moderately large structural difference may still be tolerated; later, when most of the budget has been spent, even a small structural mismatch can block the diagonal transition. Definition 14 (SED-struct Threshold Filter). For any two trees 𝑇1,𝑇2 , tree traversals 𝑇𝑇1,𝑇𝑇2 , and threshold 𝜏, define the aggregate SED-struct score as scoreSED-struct (𝑇1,𝑇2, 𝜏) = max{SED-struct(𝑇𝑇1 (𝑇1 ),𝑇𝑇1 (𝑇2 ), 𝜏), SED-struct(𝑇𝑇2 (𝑇1 ),𝑇𝑇2 (𝑇2 ), 𝜏)}. The SED-struct threshold filter accepts the pair if this score is at most 𝜏 and rejects it otherwise. By Theorem 5.2, the filter is sound: scoreSED-struct (𝑇1,𝑇2, 𝜏) > 𝜏

=⇒

𝛿 (𝑇1,𝑇2 ) > 𝜏 .

When 𝛿 (𝑇1,𝑇2 ) ≤ 𝜏, it satisfies scoreSED-struct (𝑇1,𝑇2, 𝜏) ≤ 𝛿 (𝑇1,𝑇2 ). Since the score depends on 𝜏, no unrestricted numerical lowerbound claim is made when 𝛿 (𝑇1,𝑇2 ) > 𝜏; only the filter’s threshold decision is used. The only traversal combination proposed in prior work is pre/post [8]. In Section 6.4, we show that the most effective combination for the SED-struct filter is rpre/pre. Example 5 (SED-struct on postorder, 𝜏 = 3). Let the postorder traversals be post(𝑇 1) = a3 a4 b1 a2 a5 a1 post(𝑇 2) = b1 a3 a4 a5 a2 a1

(0,3) (3,1) (2,1) (1,1) (1,0) (0,0)

𝑎3 𝑎4 𝑏1 𝑎2 𝑎5 𝑎1

0 1 2 3 × × ×

(3,2) 𝑏1 1 2 2 3 × × ×

(2,2) 𝑎3 2 3 3 3 × × ×

(2,1) 𝑎4 3 × × × × × ×

(2,0) 𝑎5 × × × × × × ×

(1,0) 𝑎2 × × × × × × ×

(0,0) 𝑎1 × × × × × × ×

Algorithm 2: Ukkonen SED-struct Algorithm Input: Strings 𝑆 1 and 𝑆 2 , threshold 𝜏 Output: Boolean value whether the SED-struct score is at most 𝜏 1 𝑚 ← |𝑆 1 | ; 2 𝑛 ← |𝑆 2 | ; 3 𝑘 ← 𝑚 − 𝑛 ; // 𝑚 ≥ 𝑛

for 𝑘 ← −𝜏 to 𝜏 do 𝐶 [−1, 𝑘] ← −1 ; 6 𝐶 [−1, 𝑘].𝑠𝑡𝑜𝑝 ← 𝑓 𝑎𝑙𝑠𝑒 ;

4

5

Figure 5: 𝐷𝜏 matrix for postorder linearized trees from Figure 3

for 𝑝 ← 0 to 𝜏 do 𝑘𝑠 = 𝑚𝑎𝑥 (−𝑝, 𝑘 − (𝜏 − 𝑝)) ; 9 𝑘𝑒 = 𝑚𝑖𝑛(𝑝, 𝑘 + (𝜏 − 𝑝)) ; 10 for 𝑘 ′ ← 𝑘𝑠 to 𝑘𝑒 do 11 𝐶 [𝑝, 𝑘 ′ ].𝑠𝑡𝑜𝑝 ← 𝑓 𝑎𝑙𝑠𝑒 ; 𝑋 ← max{𝐶 [𝑝 − 1, 𝑘 ′ − 1], 7

8

For each node 𝑢 we attach its partial structural vector sv𝑎𝑓 (𝑢). The dynamic-programming matrix 𝐷𝜏 is shown in Figure 5 truncated by the threshold 𝜏 = 3. A diagonal transition is allowed when the structural guard is satisfied; its cost is 0 when the labels are equal and 1 otherwise. Cells where 𝑐 is computed as ∞ (they do not pass the structural guard) are highlighted using grey. For example, in cell 𝐷𝜏 [𝑎 3, 𝑏 1 ] the structural difference evaluates 𝑎𝑓 to Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑎 3, 𝑏 1 ) = 4. Since the threshold in this example is 𝜏 = 3, the structural difference value exceeds the error budget allowed (𝑐 > 𝜏) and the guard is not satisfied. Consequently, the candidate alignment represented by this diagonal cannot correspond to a feasible edit path within the threshold. The dynamic programming recurrence therefore ignores this transition and the value of 𝐷𝜏 [𝑎 3, 𝑏 1 ] is determined only from the remaining two admissible predecessor cells. Therefore, computation ends very quickly with a result ‘above threshold’. We display 𝐷𝜏 [𝑖, 𝑗] only if 𝐷𝜏 [𝑖, 𝑗] ≤ 𝜏; otherwise we print a cross “×”. Thus, the SED-struct filter is the only evaluated filter capable of establishing that 𝛿 (𝑇 1,𝑇 2) > 3.

12

𝐶 [𝑝 − 1, 𝑘 ′ ] + 1¬𝐶 [𝑝 −1,𝑘 ′ ].𝑠𝑡𝑜𝑝 , ;

13

𝐶 [𝑝 − 1, 𝑘 ′ + 1] + 1} if not StrGuard(𝑝, 𝑘 ′, 𝑋, 𝜏, 𝑆 1, 𝑆 2, 𝐶) then 𝐶 [𝑝, 𝑘 ′ ] ← 𝑋 ; continue ;

14 15 16 17 18 19 20 21 22

23

while 𝑆 1 [𝑋 + 𝑘 ′ + 1] = 𝑆 2 [𝑋 + 1] do if not StrGuard(𝑝, 𝑘 ′, 𝑋, 𝜏, 𝑆 1, 𝑆 2, 𝐶) then break ; 𝑋 ←𝑋 +1; 𝐶 [𝑝, 𝑘 ′ ] ← 𝑋 ; if 𝑋 = 𝑛 and 𝑘 ′ = 𝑘 then return true; return false;

Function StrGuard(𝑝, 𝑘 ′, 𝑋, 𝜏, 𝑆 1, 𝑆 2, 𝐶):;
𝑋𝑇𝑇 𝑆 1 [𝑋 + 𝑘 ′ + 1], 𝑆 2 [𝑋 + 1] + 𝑝 > 𝜏 then 25 if Δ𝑠𝑡𝑟𝑢𝑐𝑡 26 𝐶 [𝑝, 𝑘 ′ ].𝑠𝑡𝑜𝑝 ← 𝑡𝑟𝑢𝑒 ; 27 return false; 24

5.5

Ukkonen SED-struct Algorithm

We extend Ukkonen’s SED algorithm with a structural guard based 𝑋𝑇𝑇 on the structural difference Δ𝑠𝑡𝑟𝑢𝑐𝑡 (·, ·) introduced in Section 6.4 and in Section 5. Our Ukkonen SED-struct algorithm uses the matrix 𝐶 in the same manner as Algorithm 1. Each 𝐶 cell carries, in addition to the longest matched prefix length, a boolean flag stop indicating whether the path used to obtain this cell’s value violated the structural guard. While greedily extending matches along a diagonal 𝑘, we stop 𝑋𝑇𝑇 it when Δ𝑠𝑡𝑟𝑢𝑐𝑡 (𝑆 1 [𝑋 +𝑘+1], 𝑆 2 [𝑋 +1]) + 𝑝 > 𝜏 (structural guard), resolves to false, and refuse to increase 𝑋 even if the labels are equal (see line 16 and 17). Moreover, when computing 𝐶 [𝑝, 𝑘], if the vertical predecessor 𝐶 [𝑝−1, 𝑘] has stop flag equal to true, we do not increase the matched prefix length by +1 to that predecessor (see line 12). Example 6 (Ukkonen SED-struct algorithm). Let us demonstrate Ukkonen bounded SED-struct algorithm (Algorithm 2) on our running example (i.e. postorder linearized trees T1 and T2 from Figure 3) with threshold 𝜏 = 3. The algorithm functionality is best described by the matrix 𝐶 in Figure 6. Cells whose diagonal computation is stopped by the structural

28

return true;

guard (i.e., with stop = true) are highlighted in the matrix with grey shading. For instance, consider the cell 𝐶 [0, 0] in the matrix 𝐶. In this case, the call to StrGuard evaluates its condition as true, indicating that the structural difference between the corresponding nodes already exceeds the threshold 𝜏. Consequently, the algorithm sets 𝐶 [0, 0].𝑠𝑡𝑜𝑝 ← true and the diagonal extension step is not performed, i.e., the variable 𝑋 remains equal to 0 (lines 14-15). Intuitively, this means that no prefix of the two sequences can be matched along this diagonal under the current error budget. The same structural guard condition also prohibits the diagonal alignment in the cell 𝐷𝜏 [𝑎 3, 𝑏 1 ] as we mentioned in Example 5. We observe that many fields in the matrix have a stop value of true. The Ukkonen matrix 𝐶 in Figure 6 corresponds to the 𝐷𝜏 from Example 5 where the row reached on the main diagonal is 2. Recall

𝑝\𝑘 −1 0 1 2 3

−1 −1 − 1 2 −

0 −1 0 0 1 2

1 −1 − 0 0 −

Figure 6: Adjusted Ukkonen matrix

that the column 0 corresponds to the target diagonal and the TED is 4 in our running example. Our Ukkonen bounded SED needs to reach the row 6 in column 0 at least in 𝐶 [3, 0]. However, it does not. Therefore, the algorithm rejects string similarity within 𝜏 = 3 bound.

6

EXPERIMENTAL EVALUATION

This section reports on the experimental evaluation of TED filtering methods, comparing current state-of-the-art lower-bounds from prior work with our novel SED-struct threshold filter. Our evaluation includes: (1) algorithmic efficiency when using Ukkonen’s optimized algorithm for SED-based lower-bounds, (2) impact of different tree traversals for SED-based methods. (3) lower-bound quality with holistic end-to-end search queries measuring lower-bound runtime, precision and overall query runtime, All experiments employ the filter-verify framework, a standard approach in similarity search. In the filtering phase, a lower-bound is used to generate a set of candidate trees that could potentially satisfy the query. Subsequently, in the verification phase, the exact TED for each candidate is computed using the TopDiff algorithm [24]. All evaluated filtering methods implement a trivial size lower-bound as a preliminary check before the actual computation begins. To ensure measurement stability, each experiment was executed three times, and the best (minimum) runtime is reported. This methodology is standard practice in systems research, where reporting the best of multiple trials reduces the influence of unexpected system waits, context switches, and other transient performance variations. The lower-bounds were implemented in Rust 1 . Verification algorithm TopDiff is available from [25]. All experiments were evaluated on an AMD Ryzen 5800X processor with 32GB of RAM.

6.1

Datasets

We used a total of 7 real-world datasets from different domains, such as bioinformatics (Swissprot [33], RNA [32], Treefam [27]), bibliography (DBLP [6]), NLP (PTB [19], Sentiment [28]) and code structures (Python [26]). While real-world datasets provide authentic evaluation scenarios for performance benchmarks, they do not allow us to isolate and measure the impact of specific properties on lower-bound performance. To systematically assess how individual factors affect lower-bound effectiveness of different algorithms, we created three 1 https://github.com/LukMRVC/ted-search

collections of synthetic datasets: Syntheticsize , Syntheticstruct , and Syntheticlabel , where key properties can be controlled independently[21]. This controlled experimental approach enables us to understand the behavior of lower-bounds under varying conditions that would be difficult to achieve with real data alone. 6.1.1 Syntheticsize . This collection of datasets varies the primary factor of tree size while keeping structure and labels constant. By systematically increasing tree sizes across a predefined range, we can examine how computational performance scales, allowing us to examine the impact of Ukkonen’s optimized algorithm. 6.1.2 Syntheticstruct . To isolate the effect of tree structure, this collection varies the average fanout (out-degree) while maintaining constant tree size and label count. A high fanout produces shallow and bushy tree structures, whereas a low fanout generates narrow and deep hierarchies. These structural differences affect how effectively structural information can improve lower-bound precision. We systematically decrease the average fanout to alter the resulting tree structures in datasets. 6.1.3 Syntheticlabel . The final collection of datasets examines the impact of label diversity on lower-bound effectiveness by varying the pool of available distinct labels (from 10 down to 2) while keeping tree structure and size constant. When labels are sparse, structural similarity becomes a more critical signal for edit distance approximation, allowing us to isolate the benefit of incorporating structural information into lower-bounds. The summarized characteristics of all synthetic datasets are in Table 2. 6.1.4 Synthetic Dataset Generation. The three synthetic collections were generated using a copy-and-modify approach to ensure controlled variance across experiments. The process begins with the base generation phase, where an initial seed tree is constructed according to specific parameters: node count, label pool size, and target average fanout. Following the base generation, we employ iterative modification to populate the collection. Each new tree is derived from the seed by applying a sequence of random modifications. These operations consist of selecting nodes at random to perform either a child swap or a subtree move. During this phase, we monitor the properties of the tree to ensure that the intended parameters remain stable.

6.2

Query selection

For each real-world dataset, we selected 100 distinct queries whose result sets contain approximately 1% of the collection. This result rate represents searches for relatively similar trees while providing enough positive matches for stable precision measurements. We deliberately excluded queries that the size lower-bound alone can prune effectively, because such queries reveal little about the relative quality of the nontrivial filters evaluated here. The resulting workload is therefore intentionally challenging: it isolates differences among lower-bounds rather than estimating their average performance over an unrestricted query workload.

Collection

Real

Dataset

#Trees

Avg. size

Max. size

#Labels

Mean Fanout

Sentiment

9645

36

102

19468

1.92

DBLP

150000

26

1703

992865

1.85

Treefam

5000

2666

15065

1276006

1.75

Swissprot

250000

428

20490

3809254

1.79

PTB

3832

72

711

12966

1.54

RNA

16819

145

317

170

2.52

Python

50000

948

43270

1479589

1.59

S10

1000

7.8

14

1180

2.36

S50

1000

50.8

53

3754

2.59

S100

1000

100.0

106

3700

2.83

S1000

1000

1000.0

1006

3978

2.29

HF

5000

59

59

10

4.46

MF

5000

59

59

10

3.41

SF

5000

61

61

10

2.64

LF

5000

58

58

10

2.21

VLF

5000

61

61

10

1.92

L10

5000

58

58

10

2.07

L6

5000

60

60

6

2.07

L4

5000

60

60

4

2.00

L3

5000

62

62

3

2.10

L2 5000 59 59 2 Table 2: Tree collections used in the experiments.

1.99

Syntheticsize

Syntheticlabel

6.3

Evaluation of Ukkonen’s Algorithm for SED Lower-Bound

In the first set of experiments we examine the impact of Ukkonen’s algorithm for SED lower-bound computation within a given threshold. Since the SED lower-bound computes edit distance between preorder and postorder traversals, quadratic runtime may dominate. Ukkonen’s algorithm calculates the edit distance in time 𝑂 (𝜏 · min(𝑚, 𝑛)) when only testing against a threshold 𝜏, which is particularly efficient for small thresholds. We show that the use of Ukkonen’s algorithm significantly stabilises the runtime of the SED lower-bound and enables scaling. Figure 7 presents the measured SED lower-bound runtimes on Syntheticsize collection. Ukkonen’s algorithm consistently outperforms the traditional SED computation when operating under a threshold constraint. This performance advantage becomes increasingly pronounced as tree size grows, with the improvement reaching several orders of magnitude for larger trees. Given this consistent superiority in threshold-based computation, all subsequent experiments exclusively utilize the Ukkonen-based implementation of SED lower-bounds.

6.4

Evaluation of Different Tree Traversals

As discussed in Section 5.1, different types of tree traversals can be applied in the SED lower-bound. The classic selection is a preorder

105

Overall query runtime (ms)

Syntheticstruct

Method Regular Ukkonen

104 103 102 101 10

50

100

1000

Tree size (#nodes)

Figure 7: Comparison of SED lower-bound with and without Ukkonen’s algorithm for varying tree size

and postorder [8]. We evaluate the following traversal combinations for both the SED lower-bound and the SED-struct filter: • Preorder and Postorder (pre/post). • Reverse Postorder and Postorder (rpost/post). • Reverse Postorder and Preorder (rpost/pre). • Reverse Postorder and Reverse Preorder (rpost/rpre). • Reverse Preorder and Postorder (rpre/post). • Reverse Preorder and Preorder (rpre/pre).

100

40 20 0

L4

RNA

Sentiment

Figure 8: SED lower-bound precision for different tree traversal combinations

6.4.2 SED-struct Traversal Results. Figure 9 shows the corresponding results for the SED-struct filter. The variance between different traversal combinations is higher and each combination performs differently because of the structural component of the SED-struct score. Each traversal captures a different subset of structural axes (see 13). Overall, the best performing traversal combinations are rpre/pre. The assumption is that the structural axis of subtree size has higher impact on the lower-bound precision rather than the ancestors axis. Therefore, we always use rpre/pre tree traversal in the following experiments.

6.5

Comparison of Filtering Methods on Real Datasets

We evaluate the following filtering methods, as described in Section 4: • Binary branch bound [36], • Intersection lower-bound [10],

Figure 9: SED-struct filter precision for different tree traversal combinations • Structural lower-bound [9], • SED lower-bound [8], • SED-struct threshold filter (proposed in this paper). The SED lower-bound and SED-struct filter implementations both utilize Ukkonen’s algorithm. In accordance with the filterverify framework described earlier, the search process for each query begins with an initial filtering stage to generate a set of potential candidates. Every candidate in this set must subsequently undergo a verification phase to determine the exact TED. While the computational cost of filtering is generally negligible, the verification of these candidates represents the primary bottleneck in the total runtime. Therefore, the major aspect influencing overall search runtime is filter precision. To evaluate the performance of the filtering methods, we measure the overall search execution time and filter precision, defined as the ratio of candidates that are true positives. Sentiment 102 101 100 10 1 102 101 100 10 1

DBLP 102 101 100 10 1

Swissprot

102 101 100 10 1

Treefam 102 100 10 1

PTB

Label intersection Binary branch Structural filter SED SED-struct

101

102 101 100 10 1

RNA

Python Runtime (s)

60

Sentiment

Runtime (s)

pre/post rpost/post rpost/pre rpost/rpre rpre/post rpre/pre

RNA

Runtime (s)

Traversal

80

L4

Runtime (s)

Precision (%)

100

40

Runtime (s)

Consequently, this combination fails to provide additional structural information, leading to a less effective lower-bound. The same applies to rpre/post.

pre/post rpost/post rpost/pre rpost/rpre rpre/post rpre/pre

60

0

Runtime (s)

SED(rpost(𝑇1 ), rpost(𝑇2 )) = SED(pre(𝑇1 ), pre(𝑇2 ))

Traversal

80

20

Runtime (s)

6.4.1 SED Traversal Results. Figure 8 presents the precision of different traversal combinations for the SED lower-bound across selected datasets. The results indicate that the SED lower-bound is not improved by alternative traversal combinations. The highest precision is consistently achieved by the classic pre/post pair, as well as the rpost/post, rpost/rpre, and rpre/pre combinations. The remaining rpost/pre and rpre/post underperform. This is due to the fact that rpost/pre traversal sequences are mutually reversed. Because the SED between two strings is invariant under reversal – for instance, if SED(𝑆 1, 𝑆 2 ) = 2, then SED(reverse(𝑆 1 ), reverse(𝑆 2 )) = 2 – the distance between these sequences remains identical, in other words:

Precision (%)

To systematically evaluate which traversal combinations provide the best filtering performance, we computed precision across a total of 6 combinations of traversal types a mix of datasets. The goal was to identify which traversal pairs yield the tightest lower-bounds and are the most optimal. The datasets used for this evaluation include L4 dataset from the Syntheticlabel collection, RNA and Sentiment datasets from the real-world collection.

102 101 100 10 1

Figure 10: Overall query runtimes 6.5.1 Overall Query Runtime. The overall query runtimes are illustrated in Figure 10. The SED-struct filter significantly outperforms all the other approaches on the Sentiment and PTB dataset. That is influenced mainly by its superior precision as shown on Figure 11. 6.5.2 Filter Precision. Figure 11 shows the precision of each filtering method. These results mirror the runtime performance we saw earlier: the SED-struct filter achieves the highest precision across all datasets, which directly reduces the work needed during verification. The SED lower-bound is already highly precise on several datasets, which naturally limits the potential for further improvement by the SED-struct filter. Since the SED-struct filter is an extension

of SED, there is less room for additional pruning in cases where SED already identifies the true positives effectively. This behavior is particularly evident on the Swissprot and DBLP datasets. On these specific datasets, because the precision gains are minimal, the additional computational overhead required for the structural 𝐿1 distance can result in a minor increase in latency. However, this added overhead is very little and does not compromise the SED-struct filter’s overall efficiency.

0%

Swissprot

75% 50% 25% 0%

50% 25% 0%

PTB

40% 30% 20% 10% 0%

Label intersection Binary branch Structural filter SED SED-struct

75%

RNA

80% 60% 40% 20% 0%

100%

Python

75% 50%

DBLP

102 101

Swissprot

PTB

102 101

Python

103 Runtime (s)

101

RNA

103 Runtime (s)

Runtime (s)

103 102

101

102 101

HF

MF

SF

LF

VLF

Figure 13: Precision on Synthetic structure datasets

Label intersection Binary branch Structural filter SED SED-struct

102

103 Runtime (s)

101

Runtime (s)

Runtime (s)

Runtime (s)

102

103

40

0

0%

Treefam

103

60

20

25%

6.5.3 PostgreSQL extension. All above mentioned lower-bounds were implemented into a practically usable PostgreSQL extension 2 , capable of running similarity search queries. The same query set that was used for in-memory benchmarking was also tested in this DBMS, tuned for real-world use cases. The results in PostgreSQL (Figure 12) generally mirror the in-memory implementation, with the SED-struct filter consistently achieving the highest precision and lowest overall query runtime. Sentiment

SED SED-struct

80

Figure 11: Precision on real datasets

103

Synthetic structure

100

Precision (%)

25%

Treefam

Precision (%)

50%

Precision (%)

Precision (%)

100%

75%

100% Precision (%)

10%

DBLP

Precision (%)

20% 0%

100% Precision (%)

Precision (%)

Sentiment 30%

were discussed in section 6.1. Table 2 illustrates that for both synthetic collections, the pool of available labels is restricted to a maximum of 10 distinct entries. This restriction was done on the basis of our prior experiments. When the pool of available labels increases, the efficiency of SED algorithm drastically increases with it on synthetic collections, which makes it hard to identify how structural differences in trees affect the resulting precision of the SED-struct filter.

102 101

Figure 13 displays the results of the precision benchmarks across Syntheticstruct collection, where tree structures vary from highfanout (HF) to very low-fanout (VLF) datasets. As the average fanout decreases, the precision of both methods gradually declines. However, the SED-struct filter consistently maintains higher precision than SED across all datasets. While the baseline SED lower-bound’s precision drops, the SED-struct filter remains robust, preserving the slack. This gap confirms that incorporation of structural information is beneficial and results in a more selective SED-struct filter. The results visible in Figure 14 highlight the resilience of the SED-struct filter against a reduction in distinct labels, where the number of unique labels in datasets ranges from 10 (L10) down to 2 (L2). The SED lower-bound demonstrates a high sensitivity to label diversity, as its precision significantly decreases, from 98% to 40% when the label pool is reduced. In contrast, the SED-struct filter exhibits stability, maintaining a precision of approximately 95% even for the L2 dataset. These results indicate that the SED-struct filter effectively utilizes structural information to compensate for low label variety, ensuring high filtering efficacy even in label-poor environments.

Figure 12: PostgreSQL experiments runtime

6.7 6.6

Analysis of SED-struct versus SED

The aim of this experiment is to determine when the SED-struct filter outperforms the standard SED lower-bound. The goal is to identify conditions under which structural information provides a significant benefit. We use two synthetic collections: Syntheticstruct and Syntheticlabel . Both collections have a tiny number of different labels and a nearconstant tree size. The details of creating these synthetic datasets 2 https://github.com/LukMRVC/tree_similarity_extension

Combining Filters

Prior work on tree similarity search has advocated for combining multiple lower-bound filters to achieve an optimal balance between filtering speed and precision [15]. The rationale behind this approach is straightforward: simpler lower-bounds (e.g., binary branch bound, intersection bound) can be computed extremely quickly but provide loose approximations, while more sophisticated bounds require additional computation. By applying fast filters first and progressively refining the candidate set with tighter bounds, one can theoretically achieve better overall performance than using any single lower-bound in isolation.

Synthetic label

100

SED SED-struct

Precision (%)

80 60 40 20 0

L10

L6

L4

L3

L2

Figure 14: Precision on Synthetic label datasets

However, our experimental results challenge this idea in the context of optimized filter implementations. Figure 15 presents the filtering times for all evaluated methods across real-world datasets. The results reveal that our SED and SED-struct implementations, utilizing Ukkonen’s algorithm with the Berghel-Roach optimization, exhibit filtering times that are at most one order of magnitude slower than the simplest lower-bounds, while simultaneously achieving dramatically superior precision (as shown in Figure 11). The modest increase in filtering time is more than compensated by the substantial reduction in verification costs that stems from higher precision. Sentiment

DBLP

Treefam

104

104

104

103

103

103

102

102

102

Swissprot

PTB

Label intersection Binary branch Structural filter SED SED-struct RNA

Python

104

104

104

104

103

103

103

103

102

102

102

102

binary branch, structural, and SED lower-bounds—evaluating their trade-offs between precision and computational cost across both real-world and synthetic datasets. Second, we demonstrated that incorporating Ukkonen’s bounded string edit distance algorithm into the SED lower-bound yields substantial runtime improvements, reaching several orders of magnitude for larger trees, while preserving the same pruning power. This optimization makes the SED lower-bound practical even for large tree collections. Third, we proposed the SED-struct threshold filter, a novel extension of SED that integrates structural information through a structural guard mechanism. We formally proved its soundness: whenever the SED-struct filter rejects a tree pair at threshold 𝜏, the tree edit distance of the pair is greater than 𝜏. By exploiting positional relationships between tree nodes—specifically ancestors, descendants, preceding, and following axes—the SED-struct filter achieves higher precision than all other evaluated filtering methods. Our experiments on synthetic datasets show that the filter is particularly effective when label diversity is low: while the standard SED precision drops to approximately 40% with only two distinct labels, the SED-struct filter maintains precision around 95%. The choice of tree traversal also matters; we showed that the reverse preorder/preorder combination yields the best results for the SEDstruct filter. Our experimental evaluation further revealed that, with optimized Ukkonen-based implementations, the common strategy of cascading multiple simple lower-bounds offers little benefit. To support reproducibility and further research, we make our implementation and all experimental scripts publicly available. Our results can be independently verified and extended by the community. We also provide a PostgreSQL extension that makes the evaluated filtering methods available directly within a database system.

8

ACKNOWLEDGMENTS

This work was supported by SGS, VŠB – Technical University of Ostrava, Czech Republic, under grant no. SP2026/009 "Advanced big data processing".

Figure 15: Filtering times for different methods on real datasets

REFERENCES This finding has important practical implications. When the filtering phase represents only a small fraction of total search time—as is the case with our optimized SED based implementations—the benefits of multi-stage filtering diminish considerably. The overhead of applying multiple filters can outweigh the gains. Moreover, since the SED lower-bound provides the highest precision, applying multiple simple lower-bounds won’t significantly improve the resulting overall filtering precision.

7

CONCLUSION

This paper addressed the problem of efficient threshold-based tree edit distance computation through lower-bounds. We presented three contributions advancing the state of the art. First, we conducted a comprehensive experimental comparison of existing TED lower-bounds—including size, label intersection,

[1] Shyan Akmal and Ce Jin. 2021. Faster algorithms for bounded tree edit distance. arXiv preprint arXiv:2105.02428 (2021). [2] Nikolaus Augsten, Michael Böhlen, and Johann Gamper. 2010. The pqgram distance between ordered labeled trees. ACM Transactions on Database Systems (TODS) 35, 1 (2010), 1–36. Bolzano dataset available at https://dbresearch.uni-salzburg.at/projects/pq-gram-ordered-labeled-trees/ bolzano-address-trees.zip. [3] Liesbeth Augustinus, Vincent Vandeghinste, and Frank Van Eynde. 2012. Example-based treebank querying. In Proceedings of the 8th international conference on language resources and evaluation (LREC 2012). ELRA; Paris, 3161–3167. [4] Hal Berghel and David Roach. 1996. An extension of Ukkonen’s enhanced dynamic programming ASM algorithm. ACM Trans. Inf. Syst. 14, 1 (Jan. 1996), 94–106. doi:10.1145/214174.214183 [5] Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi, Tomasz Kociumaka, and Barna Saha. 2023. Weighted edit distance computation: Strings, trees, and dyck. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 377–390. [6] dblp Team. 2017. dblp computer science bibliography – Monthly Snapshot XML Release of November 2017. http://dblp.dagstuhl.de/xml/release/dblp-2017-1101.xml.gz. doi:10.4230/dblp.xml.2017-11-01 Persistent DOI: https://doi.org/10. 4230/dblp.xml.2017-11-01.

[7] Dayi Fan, Rubao Lee, and Xiaodong Zhang. 2024. X-TED: massive parallelization of tree edit distance. Proceedings of the VLDB Endowment 17, 7 (2024). [8] Sudipto Guha, HV Jagadish, Nick Koudas, Divesh Srivastava, and Ting Yu. 2002. Approximate XML joins. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data. 287–298. [9] Thomas Hütter, Mateusz Pawlik, Robert Löschinger, and Nikolaus Augsten. 2019. Effective filters and linear time verification for tree similarity joins. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 854–865. [10] Karin Kailing, Hans-Peter Kriegel, Stefan Schönauer, and Thomas Seidl. 2004. Efficient similarity search for hierarchical data in large databases. In Advances in Database Technology-EDBT 2004: 9th International Conference on Extending Database Technology, Heraklion, Crete, Greece, March 14-18, 2004 9. Springer, 676–693. [11] Nikolai Karpov and Qin Zhang. 2023. Syncsignature: A simple, efficient, parallelizable framework for tree similarity joins. Proceedings of the VLDB Endowment 16, 2 (2023). [12] Yeonjung Kim, Jeahyun Park, Taehwan Kim, and Joongmin Choi. 2007. Web information extraction by HTML tree edit distance matching. In 2007 International Conference on Convergence Information Technology (ICCIT 2007). IEEE, 2455–2460. [13] Philip N Klein. 1998. Computing the edit-distance between unrooted ordered trees. European Symposium on Algorithms (ESA) (1998), 91–102. [14] Tomasz Kociumaka and Ali Shahali. 2025. Faster Algorithm for Bounded Tree Edit Distance in the Low-Distance Regime. arXiv preprint arXiv:2507.02701 (2025). [15] Fei Li, Hongzhi Wang, Jianzhong Li, and Hong Gao. 2014. A survey on tree edit distance lower bound estimation techniques for similarity join on XML data. ACM SIGMOD Record 42, 4 (2014), 29–39. [16] Na Liu and Tianming Wang. 2006. A method for rapid similarity analysis of RNA secondary structures. BMC bioinformatics 7 (2006), 1–11. [17] Bin Ma, Lusheng Wang, and Kaizhong Zhang. 2002. Computing similarity between RNA structures. Theoretical Computer Science 276, 1-2 (2002), 111–132. [18] Xiao Mao. 0. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance. SIAM J. Comput. 0, 0 (0), FOCS21–195–FOCS21–223. arXiv:https://doi.org/10.1137/22M1480719 doi:10.1137/22M1480719 [19] Mitchell P Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational linguistics 19, 2 (1993), 313–330. [20] William J Masek and Michael S Paterson. 1980. A faster algorithm computing string edit distances. Journal of Computer and System sciences 20, 1 (1980), 18–31. [21] Lukas Moravec and Radim Baca. 2026. Tree Similarity Search Dataset. doi:10. 21227/0qns-nj33 [22] Jakob Nogler, Adam Polak, Barna Saha, Virginia Vassilevska Williams, Yinzhan Xu, and Christopher Ye. 2025. Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (Prague, Czechia) (STOC ’25). Association for Computing Machinery, New York, NY, USA, 2167–2178. doi:10.1145/3717823.3718116 [23] Mateusz Pawlik and Nikolaus Augsten. 2015. Efficient computation of the tree edit distance. ACM Transactions on Database Systems (TODS) 40, 1 (2015), 1–40. [24] Mateusz Pawlik and Nikolaus Augsten. 2020. Minimal Edit-Based Diffs for Large Trees. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management (Virtual Event, Ireland) (CIKM ’20). Association for Computing Machinery, New York, NY, USA, 1225–1234. doi:10.1145/3340531. 3412026 [25] Mateusz Pawlik, Thomas Hütter, Daniel Kocher, and Nikolaus Augsten. 2020. Scientific Software Library: Tree Similarity Algorithms. https://github.com/ DatabaseGroup/tree-similarity [26] Veselin Raychev, Pavol Bielik, and Martin Vechev. 2016. Probabilistic model for code with decision trees. ACM SIGPLAN Notices 51, 10 (2016), 731–747. Dataset available at https://www.sri.inf.ethz.ch/py150. [27] Fabian Schreiber, The TreeFam Consortium, et al. 2014. TreeFam v9: a new database infrastructure for the phylogeny of gene families. Nucleic Acids Research 42, D1 (2014), D422–D425. doi:10.1093/nar/gkt1055 Data available at http: //www.treefam.org/static/download/treefam_family_data.tar.gz. [28] Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Y Ng, and Christopher Potts. 2013. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing. 1631–1642. Dataset available at https://nlp.stanford.edu/~socherr/stanfordSentimentTreebank.zip. [29] Jeong-Woo Son, Tae-Gil Noh, Hyun-Je Song, and Seong-Bae Park. 2013. An application for plagiarized source code detection based on a parse tree kernel. Engineering Applications of Artificial Intelligence 26, 8 (2013), 1911–1918. [30] Yewei Song, Cedric Lothritz, Xunzhu Tang, Tegawendé Bissyandé, and Jacques Klein. 2024. Revisiting code similarity evaluation with abstract syntax tree edit distance. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). 38–46. [31] Kuo-Chung Tai. 1979. The tree-to-tree correction problem. Journal of the ACM (JACM) 26, 3 (1979), 422–433.

[32] Zhen Tan, Yinghan Fu, Gaurav Sharma, and David H Mathews. 2017. TurboFold II: RNA structural alignment and secondary structure prediction informed by multiple homologs. Nucleic Acids Research 45, 20 (Nov. 2017), 11570–11581. [33] The UniProt Consortium. 2025. UniProt: the Universal Protein Knowledgebase in 2025. Nucleic Acids Research 53, D1 (2025), D609–D617. doi:10.1093/nar/gkae1010 Data downloaded from ftp://ftp.uniprot.org/pub/databases/uniprot/current_ release/knowledgebase/complete/uniprot_sprot.xml.gz (Accessed: [Insert Date]). [34] Hélène Touzet. 2005. A linear tree edit distance algorithm for similar ordered trees. In Annual symposium on combinatorial pattern matching. Springer, 334– 345. [35] Esko Ukkonen. 1985. Algorithms for approximate string matching. Information and control 64, 1-3 (1985), 100–118. [36] Rui Yang, Panos Kalnis, and Anthony KH Tung. 2005. Similarity evaluation on tree-structured data. In Proceedings of the 2005 ACM SIGMOD international conference on Management of data. 754–765. [37] Kaizhong Zhang and Dennis Shasha. 1989. Simple fast algorithms for the editing distance between trees and related problems. SIAM J. Comput. 18, 6 (1989), 1245–1262.

Related documents

• M 1.2 - 15 km E of Seven Trees, CA#1121847
• The effect of gene tree dependence on summary methods for species tree inference#357402
• Embedding rooted blow-ups of tree posets#1049282
• Asymptotics for the harmonic descent chain and applications to critical beta-splitting trees#1050757
• Native diversity buffers against severity of non-native tree invasions#197703