Metraipolis › archive › dc_5291d293b82e

Practical Threshold-based Tree Edit Distance Lower-Bounds — arXiv:2609.03078

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.03078
License (as archived)
CC0-1.0
Archived
2026-10-17T03:00:42.971Z
SHA-256 of the archived text
877d2aa49b173dc42b3bc3b6376284fe6ff664b77876911229ad3d2e84750aa2
Stable URL of this page
https://metraipolis.com/documento/dc_5291d293b82e

How to cite

Practical Threshold-based Tree Edit Distance Lower-Bounds — arXiv:2609.03078 — arXiv (en), https://arxiv.org/abs/2609.03078 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5291d293b82e (Metraipolis archive dc_5291d293b82e, sha256 877d2aa49b173dc42b3bc3b6376284fe6ff664b77876911229ad3d2e84750aa2)
BibTeX
@misc{dc5291d293b82e,
  title = {Practical Threshold-based Tree Edit Distance Lower-Bounds — arXiv:2609.03078},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.03078},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5291d293b82e; sha256 877d2aa49b173dc42b3bc3b6376284fe6ff664b77876911229ad3d2e84750aa2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.03078. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-04 in cs.DB).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.03078 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T02:33:39.135Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-04?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).