Extended Subtree: A New Similarity Function for Tree Structured Data

doi:10.1109/TKDE.2013.53

Extended Subtree: A New Similarity Function for Tree Structured Data

2014-04-01

9

PRE

AI

DOI：10.1109/TKDE.2013.53

Original

Original request for help

Save

Abstract

En 中文

Although several distance or similarity functions for trees have been introduced, their performance is not always satisfactory in many applications, ranging from document clustering to natural language processing. This research proposes a new similarity function for trees, namely Extended Subtree (EST), where a new subtree mapping is proposed. EST generalizes the edit base distances by providing new rules for subtree mapping. Further, the new approach seeks to resolve the problems and limitations of previous approaches. Extensive evaluation frameworks are developed to evaluate the performance of the new approach against previous proposals. Clustering and classification case studies utilizing three real-world and one synthetic labeled data sets are performed to provide an unbiased evaluation where different distance functions are investigated. The experimental results demonstrate the superior performance of the proposed distance function. In addition, an empirical runtime analysis demonstrates that the new approach is one of the best tree distance functions in terms of runtime efficiency.

Keywords:

Tree classification

tree clustering

tree comparison

tree distance function

tree similarity

tree structured data

Extended Subtree: A New Similarity Function for Tree Structured Data

Abstract

AI Summary

Journal

Organization