Title | ||
---|---|---|
Earth Mover's Distance Between Rooted Labeled Unordered Trees Formulated from Complete Subtrees. |
Abstract | ||
---|---|---|
In this paper, we introduce earth mover’s distances (EMDs, for short) for rooted labeled trees formulated from complete subtrees. First, we formulate the EMDs whose signatures are all of the pairs of a complete subtree and the ratio of its frequency and whose ground distances are either the tractable variations of the tree edit distance, provided from the restricted mappings in the Tai mapping hierarchy, or the complete subtree histogram distance. Then, we show that all of the EMDs are metrics and we can compute them in (O(n^3log n)) time, where n is the maximum number of nodes in given two trees. Finally, we give experimental results of computing EMDs for several data, by comparing the EMDs with their ground distances. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/978-3-030-05499-1_4 | ICPRAM |
Field | DocType | Citations |
Histogram,Binary logarithm,Combinatorics,Earth mover's distance,Pattern recognition,Computer science,Tree (data structure),Artificial intelligence,Tree edit distance,Hierarchy | Conference | 0 |
PageRank | References | Authors |
0.34 | 10 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Taiga Kawaguchi | 1 | 0 | 0.68 |
Takuya Yoshino | 2 | 4 | 4.54 |
Kouichi Hirata | 3 | 130 | 32.04 |