Abstract | ||
---|---|---|
We introduce a tree distance function based on multi-sets. We show that this function is a metric on tree spaces, and we design an algorithm to compute the distance between trees of size at most n in O (n 2) time and O (n ) space. Contrary to other tree distance functions that require expensive memory allocations to maintain dynamic programming tables of forests, our function can be implemented over simple and static structures. Additionally, we present a case study in which we compare our function with other two distance functions. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-642-00399-8_8 | PAKDD Workshops |
Keywords | DocType | Volume |
static structure,tree space,tree distance function,dynamic programming table,tree distance,expensive memory allocation,case study,distance function,memory allocation,triangle inequality | Conference | 5433 |
ISSN | Citations | PageRank |
0302-9743 | 8 | 0.58 |
References | Authors | |
21 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Arnoldo José Muller-Molina | 1 | 14 | 2.13 |
Kouichi Hirata | 2 | 130 | 32.04 |
Takeshi Shinohara | 3 | 660 | 75.22 |