On the Usage of Structural Distance Metrics for Mining Hierarchical Structures

Abstract

The recent proliferation of XML-based standards and technologies demonstrates the need for effective management of hierarchical structures. Such structures are used, for example, to organize data in product catalogs, taxonomies of thematic categories, concept hierarchies, etc. Since the XML language has become the standard data exchange format on the Web, organizing data in hierarchical structures has been vastly established. Even if data are not stored natively in such structures, export mechanisms make data publicly available in hierarchical structures to enable its automatic processing by programs, scripts and agents. Processing data encoded in hierarchical structures has been a popular research issue, resulting in the design of effective query languages. However, the inherent structural aspect of such encodings has not received strong attention till lately, when the requirement for mining tasks, like clustering/classification methods, similarity ranking, etc., on hierarchical structures has been raised. The key point to perform such tasks is the design of a structural distance metric to quantify the structural similarity between hierarchical structures. The chapter will study distance metrics that capture the structural similarity between hierarchical structures and approaches that exploit structural distance metrics to perform mining tasks on them.