Name
Abstract | ||
|---|---|---|
In this paper, we focus on a caterpillar as a rooted labeled unordered tree (a tree, for short) transformed to a path after removing all the leaves in it. Also we introduce a path histogram distance between trees as an L-1-distance between the histograms of paths from the root to every leaf. Whereas the path histogram distance is not a metric for trees, we show that, for caterpillars, it 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 with the isolated-subtree distance as the most general tractable variation of the edit distance. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/978-3-319-75417-8_26 | INTELLIGENT INFORMATION AND DATABASE SYSTEMS, ACIIDS 2018, PT I |
Field | DocType | Volume |
Edit distance,Data mining,Histogram,Combinatorics,Computer science | Conference | 10751 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
8 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Taiga Kawaguchi | 1 | 0 | 0.34 |
| Takuya Yoshino | 2 | 4 | 4.54 |
| Kouichi Hirata | 3 | 130 | 32.04 |