Path histogram distance and complete subtree histogram distance for rooted labelled caterpillars

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.

Keywords

• path histogram distance
• complete subtree histogram distance
• rooted labelled caterpillar
• edit distance
• isolated-subtree distance