Not checkedNot checked for notices yet.
Path histogram distance and complete subtree histogram distance for rooted labelled caterpillars
Taiga Kawaguchi, Takuya Yoshino, Kouichi Hirata
Journal of Information and Telecommunication · 2020
doi:10.1080/24751839.2020.1718443 (opens in a new tab)
We email you when a new notice or a question about this paper appears.
Abstract
A rooted labelled caterpillar (a caterpillar, for short) is a rooted labelled unordered tree transformed to a path after removing all the leaves in it. In this paper, we discuss two histogram distance between caterpillars. One is a path histogram distance as an $L_1$-distance between the histograms of paths from the root to every leaf and another is a complete subtree histogram distance as an $L_1$-distance between the histograms of complete subtrees for every node. While the latter is always a metric for general trees, the former is not a metric. In this paper, we show that, for caterpillars, the path histogram distance is always a metric, simply linear-time computable and incomparable with the edit distance. Furthermore, we give experimental results for caterpillars in real data of comparing the path histogram distance and the complete subtree histogram distance with the isolated-subtree distance as the most general tractable variation of the edit distance.
Abstract licence: CC BY-NC
Reads
Read by people on this page
None yet.
Checked or read by AI through naulon
None yet.
A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.
Are you an author?
Is this your paper?
Claim it to add your note and be paid when agents cite it. Free.