Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

A bounded distance metric for comparing tree structure

Connor, R. and Simeoni, F. and Iakovos, M. and Moss, R. (2011) A bounded distance metric for comparing tree structure. Information Systems, 36 (4). pp. 748-764. ISSN 0306-4379

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

Comparing tree-structured data for structural similarity is a recurring theme and one on which much effort has been spent. Most approaches so far are grounded, implicitly or explicitly, in algorithmic information theory, being approximations to an information distance derived from Kolmogorov complexity. In this paper we propose a novel complexity metric, also grounded in information theory, but calculated via Shannon's entropy equations. This is used to formulate a directly and efficiently computable metric for the structural difference between unordered trees. The paper explains the derivation of the metric in terms of information theory, and proves the essential property that it is a distance metric. The property of boundedness means that the metric can be used in contexts such as clustering, where second-order comparisons are required. The distance metric property means that the metric can be used in the context of similarity search and metric spaces in general, allowing trees to be indexed and stored within this domain. We are not aware of any other tree similarity metric with these properties.

Item type: Article
ID code: 32916
Keywords: unordered tree, tree comparison, distance metric, algorithmic information theory, information content, information distance, entropy, Electronic computers. Computer science, Hardware and Architecture, Software, Information Systems
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
Depositing user: Pure Administrator
Date Deposited: 29 Aug 2011 09:58
Last modified: 05 Sep 2014 10:26
URI: http://strathprints.strath.ac.uk/id/eprint/32916

Actions (login required)

View Item