Tree edit distance: Robust and memory-efficient

作者：

Highlights：

• We address the memory problem of the strategy computation in the RTED algorithm for the tree edit distance.

• We prove an upper bound which guarantees that the strategy computation never uses more memory than the distance computation.

• We compute the optimal strategy in the class of all-path strategies which subsumes the LRH strategies used before.

• We develop new single-path functions which are better in terms of runtime and memory than the previously used functions.

摘要

Highlights•We address the memory problem of the strategy computation in the RTED algorithm for the tree edit distance.•We prove an upper bound which guarantees that the strategy computation never uses more memory than the distance computation.•We compute the optimal strategy in the class of all-path strategies which subsumes the LRH strategies used before.•We develop new single-path functions which are better in terms of runtime and memory than the previously used functions.

论文关键词：Tree edit distance,Similarity search,Approximate matching

论文评审过程：Received 12 August 2014, Revised 25 May 2015, Accepted 2 August 2015, Available online 28 August 2015, Version of Record 29 October 2015.

论文官网地址：https://doi.org/10.1016/j.is.2015.08.004