Name
Title | ||
|---|---|---|
Vertical And Horizontal Distances To Approximate Edit Distance For Rooted Labeled Caterpillars |
Abstract | ||
|---|---|---|
A rooted labeled caterpillar (caterpillar, for short) is a rooted labeled tree transformed to a rooted path (called a backbone) after removing all the leaves in it and we can compute the edit distance between caterpillars in quartic time. In this paper, we introduce two vertical distances and two horizontal distances for caterpillars. The former are based on a string edit distance between the string representations of the backbones and the latter on a multiset edit distance between the multisets of labels occurring in all the leaves. Then, we show that these distances give both lower bound and upper bound of the edit distance and we can compute the vertical distances in quadratic time and the horizontal distances in linear time under the unit cost function. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.5220/0007387205900597 | ICPRAM: PROCEEDINGS OF THE 8TH INTERNATIONAL CONFERENCE ON PATTERN RECOGNITION APPLICATIONS AND METHODS |
Keywords | Field | DocType |
Edit Distance, Rooted Labeled Caterpillar, Vertical Distance, Horizontal Distance, String Edit Distance, Multiset Edit Distance | Edit distance,Horizontal and vertical,Combinatorics,Pattern recognition,Upper and lower bounds,Multiset,Computer science,Quartic function,Artificial intelligence,Time complexity | Conference |
Citations | PageRank | References |
1 | 0.38 | 0 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kohei Muraka | 1 | 1 | 0.38 |
| Takuya Yoshino | 2 | 4 | 4.54 |
| Kouichi Hirata | 3 | 130 | 32.04 |