An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs
Paaßen B (2021)
In: Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021). Reyes N, Connor R, Kriege N, Kazempour D, Bartolini I, Schubert E, Chen J-J (Eds); Springer: 364–371.
Konferenzbeitrag | Englisch
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Herausgeber*in
Reyes, Nora;
Connor, Richard;
Kriege, Nils;
Kazempour, Daniyal;
Bartolini, Ilaria;
Schubert, Erich;
Chen, Jian-Jia
Einrichtung
Abstract / Bemerkung
The unordered tree edit distance is a natural metric to compute distances between trees without intrinsic child order, such as representations of chemical molecules. While the unordered tree edit distance is MAX SNP-hard in principle, it is feasible for small cases, e.g. via an A* algorithm. Unfortunately, current heuristics for the A* algorithm assume unit costs for deletions, insertions, and replacements, which limits our ability to inject domain knowledge. In this paper, we present three novel heuristics for the A* algorithm that work with custom cost functions. In experiments on two chemical data sets, we show that custom costs make the A* computation faster and improve the error of a 5-nearest neighbor regressor, predicting chemical properties. We also show that, on these data, polynomial edit distances can achieve similar results as the unordered tree edit distance.
Erscheinungsjahr
2021
Titel des Konferenzbandes
Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021)
Seite(n)
364–371
Konferenz
14th International Conference on Similarity Search and Applications (SISAP 2021)
Konferenzort
Dortmund
Konferenzdatum
2021-09-29 – 2021-10-01
Page URI
https://pub.uni-bielefeld.de/record/2978967
Zitieren
Paaßen B. An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs. In: Reyes N, Connor R, Kriege N, et al., eds. Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021). Springer; 2021: 364–371.
Paaßen, B. (2021). An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs. In N. Reyes, R. Connor, N. Kriege, D. Kazempour, I. Bartolini, E. Schubert, & J. - J. Chen (Eds.), Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021) (p. 364–371). Springer. https://doi.org/10.1007/978-3-030-89657-7_27
Paaßen, Benjamin. 2021. “An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs”. In Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021), ed. Nora Reyes, Richard Connor, Nils Kriege, Daniyal Kazempour, Ilaria Bartolini, Erich Schubert, and Jian-Jia Chen, 364–371. Springer.
Paaßen, B. (2021). “An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs” in Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021), Reyes, N., Connor, R., Kriege, N., Kazempour, D., Bartolini, I., Schubert, E., and Chen, J. - J. eds. (Springer), 364–371.
Paaßen, B., 2021. An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs. In N. Reyes, et al., eds. Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021). Springer, pp. 364–371.
B. Paaßen, “An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs”, Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021), N. Reyes, et al., eds., Springer, 2021, pp.364–371.
Paaßen, B.: An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs. In: Reyes, N., Connor, R., Kriege, N., Kazempour, D., Bartolini, I., Schubert, E., and Chen, J.-J. (eds.) Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021). p. 364–371. Springer (2021).
Paaßen, Benjamin. “An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs”. Proceedings of the 14th International Conference on Similarity Search and Applications (SISAP 2021). Ed. Nora Reyes, Richard Connor, Nils Kriege, Daniyal Kazempour, Ilaria Bartolini, Erich Schubert, and Jian-Jia Chen. Springer, 2021. 364–371.
Open Access
arXiv: 
Google Scholar