PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Threshold-based Tree Edit Distance Lower-Bounds

Lukáš Moravec, Radim Bača

arXiv:2609.03078v1cs.DB

TL;DR

Threshold-based TED search needs lower-bounds because exact distance computation is costly, while existing comparisons omit bounded SED implementations and newer structural filters. The paper compares current bounds, accelerates SED with Ukkonen’s algorithm, and adds an axes-aware SED-struct filter. SED-struct has higher precision than the evaluated alternatives, including a pronounced advantage on low-label-diversity synthetic data.

  • Problem

    Exact TED is costly, and prior comparisons omit threshold-aware SED implementations and recent structural filters, leaving their practical trade-offs unclear.

    Source: §1 · p. 1

  • Method

    The paper compares state-of-the-art lower-bounds, applies Ukkonen’s bounded algorithm to SED, and adds an axes-aware structural guard to form SED-struct.

    Source: §1 · pp. 1–2, §5.4 · p. 8

  • Results

    With two distinct labels, standard SED precision drops to approximately 40%, while SED-struct maintains precision around 95%.

    Source: §7 · p. 14

  • Takeaways & Limitations

    SED-struct achieves higher precision than all other evaluated filtering methods while retaining practical filtering costs.

    Source: §1 · p. 2, §7 · p. 14

    When SED is already highly precise on a dataset, the potential for further precision improvement from SED-struct is limited.

    Source: §6.5.2 · p. 12

Abstract

from arXiv · show

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 $\tau$. 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.

1 INTRODUCTION

Threshold-based tree similarity search uses TED, but exact computation is costly, so filter-verify methods use lower-bounds to prune candidates before exact verification. This paper compares current lower-bounds, accelerates SED, and introduces an axes-aware SED-struct filter that achieves strong precision at practical cost.

1 INTRODUCTION

  • Tree similarity search has applications in linguistics, bioinformatics, web data, and code-plagiarism detection.Examples include syntactical analysis, RNA structure comparison, near-duplicate website detection, and AST similarity.Source: §1 · p. 1
  • Threshold-based TED search prunes candidates with lower-bounds before computing exact distances for survivors.Exact TED is computationally expensive, motivating the filter-verify approach.Source: §1 · p. 1
  • SED offers high pruning power, but standard quadratic-time and space computation becomes a bottleneck as trees or collections grow.The paper identifies prior comparisons as incomplete because they omit bounded SED implementations and recent structural filtering.Source: §1 · p. 1
  • The paper compares state-of-the-art TED lower-bounds and improves SED efficiency with Ukkonen’s bounded algorithm.The comparison evaluates precision and cost, including bounded implementations missing from prior surveys.Source: §1 · p. 2
  • SED-struct achieves the best balance of precision and speed on synthetic and real-world datasets.The filter combines SED with axes-aware structural constraints.Source: §1 · p. 2

2 RELATED WORK

Related work spans exact TED algorithms, bounded-distance methods, and lower-bounds for search and joins. This paper updates empirical comparisons and combines bounded SED computation with structural information.

2 RELATED WORK

  • TED research covers exact algorithms, complexity limits, and threshold-oriented filtering for similarity search and joins.Source: §2 · p. 2

2.1 Exact TED Algorithms

  • Exact TED work progresses from Tai’s polynomial-time algorithm [31] through dynamic-programming refinements and practical frameworks such as RTED and APTED.Later theoretical improvements include runtimes of O(n^2.9546) and O(n^2.6857) [22], while X-TED uses GPU acceleration.Source: §2.1 · p. 2

2.2 Bounded Tree Edit Distance

  • Bounded TED algorithms target threshold decisions, with improved runtimes particularly relevant when τ is much smaller than tree size n.Prior work ranges from O(nτ^3) to O(n + k^6 log k) [14], while TopDiff remains the practical state of the art stated here.Source: §2.2 · p. 2

2.3 TED Lower-bounds for Search and Join

  • Lower-bounds range from size and label statistics to structural and traversal encodings; prior studies find SED most precise but most costly.The pq-gram distance is inapplicable to the widely used TED in this paper because it lower-bounds only fanout-weighted TED; comparisons here use unweighted TED.Source: §2.3 · p. 2
  • The paper updates prior comparisons and structural filters with an enhanced filter combining bounded SED and structural information.Source: §2.3 · p. 2

3 PROBLEM DEFINITION

The problem definition describes ordered trees through node relationships and measures their distance by the minimum number of allowed edits. It also introduces structural vectors that summarize relationship-axis counts.

3 PROBLEM DEFINITION

  • Each node has four disjoint relationship subsets: ancestors, descendants, preceding nodes, and following nodes.For node b1, Figure 1 depicts these subsets, whose sizes are denoted a(b1), d(b1), p(b1), and f(b1).Source: §3 · p. 2, Figure 1 · p. 3
  • A complete structural vector considers all four relationship axes, while partial vectors select only some axes.These vectors are used in the structural filter and SED-struct threshold filter.Source: §3 · p. 3
  • Tree edit distance is the minimum number of insert, delete, and relabel operations needed to transform one tree into another.Insertion makes a node a child while preserving order; deletion reattaches its children to its parent, also preserving order.Source: §3 · p. 3
  • In the example, the optimal mapping costs four edits between T1 and T2, while the distance between T1 and T3 is one.Source: §3 · p. 3

4 LOWER-BOUND FOR TREE EDIT DISTANCE

This section presents lower-bounds for pruning tree pairs before exact TED computation, moving from size and label statistics to bounds that incorporate structure. It details traversal-based SED and a threshold-aware structural filter.

4 LOWER-BOUND FOR TREE EDIT DISTANCE

  • Lower-bounds cheaply approximate TED, allowing a pair to be pruned when its bound exceeds the threshold; the section covers size, intersection, binary-branch, and traversal-string bounds.Surviving candidates require exact verification.Source: §4 · p. 3

4.1 Size Lower-Bound

  • The size lower-bound uses the node-count difference and runs in O(1) time, but ignores labels and structure and is often not selective.It is used first, before other lower-bounds.Source: §4.1 · p. 3

4.2 Label intersection Lower-Bound

  • The label-intersection lower-bound uses shared label occurrences, but ignores structure and can rank T1–T2 as closer than T1–T3 even when their TED ordering is the reverse.In the example, the intersection bound is 0 for T1–T2 and 1 for T1–T3, while their TED values are 4 and 1, respectively.Source: §4.2 · p. 3

4.3 Binary Branch Lower-Bound

  • The binary-branch bound represents a tree through its binary left-child, right-sibling form and uses BBDist(T1,T2)/5, an O(n)-time but generally loose TED lower-bound.Source: §4.3 · p. 3

4.4 String Edit Distance (SED) Lower-Bound

  • SED compares label strings from tree traversals; taking the maximum of preorder and postorder distances gives a more robust lower-bound, though standard dynamic programming costs O(n·m).Any tree edit operation induces at most one edit on a traversal string, so the SED does not exceed TED.Source: §4.4 · p. 4
  • In the example, the preorder distance is zero and the SED lower-bound is 2, implying TED is at least 2.Source: §4.4 · p. 5

4.5 Structural Filter

  • The structural filter uses threshold-valid label matches and structural differences between nodes to form a bound; its full structural vectors use four relationship axes, though a subset can be advantageous with SED.The cited implementation relaxes the strict one-to-one mapping in label-intersection search to favor runtime at the cost of slightly looser bounds.Source: §4.5 · p. 5

5 SED-STRUCT THRESHOLD FILTER

This section presents SED-struct, which augments SED with traversal-aware structural constraints, and develops its traversal-specific constraints, threshold soundness, and bounded algorithms. It also describes a structural guard in Ukkonen SED-struct that stops diagonal extensions when structural difference exceeds τ.

5 SED-STRUCT THRESHOLD FILTER

  • SED-struct adds axes-aware constraints to SED, aiming to improve precision on structurally variable collections with minimal computational overhead relative to SED.The section describes it as the first usable filter of this kind that outperforms SED.Source: §5 · p. 5

5.1 Tree Traversal

  • The four traversals are preorder, postorder, reverse preorder, and reverse postorder; the reverse variants visit siblings right to left.Mapped nodes retain the same relative order in both traversal sequences for each traversal.Source: §5.1 · pp. 5–6

5.2 Ukkonen SED Algorithm

  • Ukkonen’s bounded SED algorithm examines a threshold-limited diagonal range and runs in O(τ·min(|S1|, |S2|)) time and O(τ) space.It reduces computation relative to quadratic dynamic programming while preserving the bounded SED decision.Source: §5.2 · pp. 6–7

5.3 Structural Difference

  • The filter selects structural-difference axes not already encoded by the traversal, tightening lower bounds without significant computational overhead.For preorder, the selected axes are descendants and followers.Source: §5.3 · p. 7

5.4 Combining SED with Structural Constraints

  • SED-struct is sound: if its score exceeds τ, the tree edit distance also exceeds τ.The structural guard is necessary but not sufficient: it never blocks a match from an edit mapping within τ, but passing it alone does not prove a match is feasible.Source: §5.4 · p. 8

5.5 Ukkonen SED-struct Algorithm

  • The Ukkonen SED-struct algorithm augments each matrix cell with a stop flag and halts diagonal match extension when the structural guard fails.A stopped vertical predecessor also cannot increase the matched-prefix length.Source: §5.5 · p. 9
  • When structural difference exceeds τ, StrGuard sets stop=true and skips diagonal extension, leaving X=0.This means no prefix can be matched along that diagonal under the current error budget.Source: §5.5 · p. 9
  • In the running example, bounded SED rejects similarity within τ=3 because column 0 fails to reach required row 6, at least at C[3, 0], although TED is 4.Source: §5.5 · p. 10

6 EXPERIMENTAL EVALUATION

The evaluation compares TED lower-bounds across real-world and controlled synthetic tree collections, measuring efficiency, traversal effects, and end-to-end search behavior. Synthetic data vary tree properties independently to isolate their effects.

6 EXPERIMENTAL EVALUATION

  • The experiments compare lower-bound efficiency, traversal effects, and end-to-end search runtime within a filter-verify framework.Each method first filters candidates, then verifies survivors with exact TED; each experiment ran three times and reports the minimum runtime.Source: §6 · p. 10

6.1 Datasets

  • Seven real-world datasets cover bioinformatics, bibliography, NLP, and code structures.The collections include Swissprot, RNA, Treefam, DBLP, PTB, Sentiment, and Python.Source: §6.1 · p. 10
  • Three synthetic collections control key tree properties independently, complementing real data that cannot isolate individual effects.The collections are Syntheticsize, Syntheticstruct, and Syntheticlabel.Source: §6.1 · p. 10

6.1.1 Syntheticsize.

  • Tree size varies while structure and labels remain fixed, enabling measurement of computational scaling and Ukkonen’s impact.The collection systematically increases tree sizes across a predefined range.Source: §6.1.1 · p. 10

6.1.2 Syntheticstruct.

  • Average fanout varies while tree size and label count stay constant, contrasting shallow, bushy trees with narrow, deep ones.This isolates how tree structure affects the value of structural information in lower-bound precision.Source: §6.1.2 · p. 10

6.1.3 Syntheticlabel.

  • Label diversity varies from 10 to 2 distinct labels while tree size and structure stay constant.The design isolates structural information’s contribution when labels are sparse.Source: §6.1.3 · p. 10

6.1.4 Synthetic Dataset Generation.

  • Synthetic trees are generated from a parameterized seed, then diversified through random child swaps or subtree moves while intended properties are monitored.Seed parameters include node count, label-pool size, and target average fanout.Source: §6.1.4 · p. 10

6.2 Query selection

The query workload targets challenging comparisons among nontrivial filters, while the Ukkonen-based SED lower-bound improves runtime under a threshold constraint. Its advantage grows with tree size.

6.2 Query selection

  • Each real-world dataset contributes 100 queries with result sets near 1% of the collection, excluding queries prunable by size alone.This intentionally challenging workload isolates differences among nontrivial lower-bounds rather than estimating performance over unrestricted queries.Source: §6.2 · p. 10

6.3 Evaluation of Ukkonen’s Algorithm for SED Lower-Bound

  • Ukkonen’s algorithm consistently outperforms traditional SED under a threshold, with gains reaching several orders of magnitude for larger trees.All subsequent experiments therefore use Ukkonen-based SED lower-bounds.Source: §6.3 · p. 11

6.4 Evaluation of Different Tree Traversals

Traversal choice does not improve SED precision, but it affects SED-struct because its structural component captures different axes. The evaluation selects rpre/pre for subsequent SED-struct experiments.

6.4 Evaluation of Different Tree Traversals

  • The study evaluates six traversal combinations across L4, RNA, and Sentiment to compare SED and SED-struct precision.The combinations pair preorder, postorder, reverse preorder, and reverse postorder traversals.Source: §6.4 · pp. 11–12

6.4.1 SED Traversal Results.

  • For SED, pre/post, rpost/post, rpost/rpre, and rpre/pre achieve the highest precision, while rpost/pre and rpre/post underperform.The mutually reversed traversal sequences add no structural information because string edit distance is invariant under reversal.Source: §6.4.1 · p. 12, Figure 8 · p. 12
  • For SED-struct, rpre/pre performs best, and it is used in subsequent experiments.The authors assume subtree-size axes affect precision more than ancestor axes; traversal combinations capture different structural axes.Source: §6.4.2 · p. 12

6.5 Comparison of Filtering Methods on Real Datasets

Across the evaluated real-world datasets, SED-struct achieves the highest filter precision and significantly outperforms other methods on Sentiment and PTB query runtimes. PostgreSQL experiments generally mirror the in-memory results.

6.5 Comparison of Filtering Methods on Real Datasets

  • The comparison includes binary branch, intersection, structural, SED, and SED-struct filtering methods, with Ukkonen used for both SED-based methods.The evaluation measures filter precision and overall query execution time.Source: §6.5 · p. 12

6.5.1 Overall Query Runtime.

  • SED-struct achieves the highest precision across all datasets and significantly outperforms other methods on Sentiment and PTB query runtimes.The reported runtime advantage is mainly attributed to superior precision.Source: Figure 10 · p. 12, §6.5.2 · p. 12, §6.5.1 · p. 12

6.5.2 Filter Precision.

  • On Swissprot and DBLP, minimal precision gains can allow structural L1 overhead to cause a minor latency increase.The authors report that the added overhead is very small and does not compromise overall efficiency.Source: §6.5.2 · pp. 12–13

6.5.3 PostgreSQL extension.

  • In PostgreSQL, SED-struct likewise achieves the highest precision and lowest overall query runtime.The DBMS results generally mirror the in-memory implementation.Source: §6.5.3 · p. 13, Figure 12 · p. 13

6.6 Analysis of SED-struct versus SED

The section compares SED-struct with SED on synthetic trees with restricted label diversity and near-constant tree size. SED-struct retains higher precision as fanout decreases and when the label pool is reduced.

6.6 Analysis of SED-struct versus SED

  • The experiment tests when structural information lets SED-struct outperform the standard SED lower-bound.Source: §6.6 · p. 13
  • The collections have near-constant tree size and at most 10 distinct labels, a restriction chosen to expose structural effects on precision.The authors report that larger label pools make SED more efficient on synthetic collections.Source: §6.6 · p. 13
  • SED-struct maintains higher precision than SED across synthetic structure datasets as average fanout decreases.Both methods' precision declines, but SED-struct preserves more slack.Source: Figure 13 · p. 13, §6.6 · p. 13
  • With only two distinct labels, SED-struct maintains approximately 95% precision while SED falls from 98% to 40% as label diversity decreases.The label-pool range is 10 (L10) to 2 (L2).Source: §6.6 · p. 13

6.7 Combining Filters

The experiments compare cascaded lower-bounds with optimized SED-based filters. On real datasets, optimized SED and SED-struct take at most one order of magnitude longer to filter than the simplest bounds, while higher precision reduces verification costs.

6.7 Combining Filters

  • Cascading simple bounds is motivated by combining fast, loose filters with tighter, costlier ones to balance speed and precision.The rationale is to apply quick filters first and refine the remaining candidates with tighter bounds.Source: §6.7 · p. 13
  • Optimized SED and SED-struct filtering takes at most one order of magnitude longer than the simplest bounds on real datasets, with dramatically superior precision.The reported comparison links the precision result to Figure 11 and filtering times to Figure 15.Source: §6.7 · p. 14, Figure 15 · p. 14
  • When optimized SED filtering is a small share of search time, the overhead of multiple filters can outweigh their gains.Source: §6.7 · p. 14

7 CONCLUSION

The conclusion reports a comparison of TED lower-bounds, an optimized SED implementation, and the SED-struct filter. The experiments find SED-struct more precise, especially with low label diversity, while Ukkonen-based SED speeds computation without reducing pruning power.

7 CONCLUSION

  • The comparison evaluates size, label-intersection, binary-branch, structural, and SED lower-bounds for precision and computational cost on real and synthetic datasets.Source: §7 · p. 14
  • Ukkonen's bounded SED algorithm yields runtime improvements of several orders of magnitude for larger trees while preserving pruning power.The conclusion says this makes SED practical for large tree collections.Source: §7 · p. 14
  • SED-struct achieves higher precision than the evaluated filters, with about 95% precision at two distinct labels where SED falls to about 40%.The filter uses axes-aware structural information and is formally sound: rejection at threshold τ guarantees TED greater than τ.Source: §7 · p. 14
  • With optimized Ukkonen-based implementations, cascading multiple simple lower-bounds offers little benefit.Source: §7 · p. 14
  • The implementation and experimental scripts are publicly available, and a PostgreSQL extension exposes the evaluated filters in a database system.Source: §7 · p. 14
Loading 2609.03078v1…