.png){kind=icon}
返回
Tree edit distance: Robust and memory-efficient
.png){kind=icon}
PRE
AI
DOI：10.1016/j.is.2015.08.004.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Hierarchical data are often modelled as trees. An interesting query identifies pairs of similar trees. The standard approach to tree similarity is the tree edit distance, which has successfully been applied in a wide range of applications. In terms of runtime, the state-of-the-art algorithm for the tree edit distance is RTED, which is guaranteed to be fast independent of the tree shape. Unfortunately, this algorithm requires up to twice the memory of its competitors. The memory is quadratic in the tree size and is a bottleneck for the tree edit distance computation. In this paper we present a new, memory efficient algorithm for the tree edit distance, AP-TED (All Path Tree Edit Distance). Our algorithm runs at least as fast as RTED without trading in memory efficiency. This is achieved by releasing memory early during the first step of the algorithm, which computes a decomposition strategy for the actual distance computation. We show the correctness of our approach and prove an upper bound for the memory usage. The strategy computed by AP-TED is optimal in the class of all-path strategies, which subsumes the class of LRH strategies used in RTED. We further present the AP-TED+ algorithm, which requires less computational effort for very small subtrees and improves the runtime of the distance computation. Our experimental evaluation confirms the low memory requirements and the runtime efficiency of our approach. (C) 2015 Elsevier Ltd. All rights reserved.
Keyword:
Tree edit distance
Similarity search
Approximate matching
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
3.9
论文数:
2.8K
被引数:
1.8K
机构
引用论文
.png){kind=icon}
Mission Impossible? What States With Large Percentages of Rural Schools Tell Us About Federal School Improvement Grants不可能的任务？高比例农村学校的州所揭示的关于联邦学校改进补助金的信息
PREAI
分享收藏Assessing the psychological and mechanical impact of electoral rules: A quasi-experiment评估选举规则的心理学和机械学影响：一项准实验
PREAI
分享收藏分享收藏
查看更多内容