XML schema clustering with semantic and hierarchical similarity measures

Abstract

With the growing popularity of XML as the data representation language, collections of the XML data are exploded in numbers. The methods are required to manage and discover the useful information from them for the improved document handling. We present a schema clustering process by organising the heterogeneous XML schemas into various groups. The methodology considers not only the linguistic and the context of the elements but also the hierarchical structural similarity. We support our findings with experiments and analysis.

Introduction

XML has become a standard for information exchange and retrieval [34]. With the continuous growth in the XML data, the ability to manage massive collections of XML data and to discover knowledge from them becomes essential for the Web-based information systems [15], [25]. A possible solution is to group the similar XML data based on their context and structure. The clustering of XML data facilitates a number of advanced applications such as improved information retrieval, data and schema integration, document classification analysis, structure summary and indexing, and query processing and optimization [6], [23].

The clustering data mining process categorizes the XML data based on their similarity without having a prior knowledge on the taxonomy. There exist a number of clustering methods dealing with the (unstructured) database objects and text data [3], [36]. The XML data is different – semistructured and hierarchical [34]. There are two types of XML data: XML documents and XML schemas. A XML schema describes the structure of the XML document. Usually, XML’s schema can be obtained separately without scanning the whole document. Therefore, a method to cluster the XML documents should take advantage of their schema.

The similarity of correspondence elements between the XML documents can be conducted efficiently using the relevant XML schemas. The document schema provides a definitive description of the XML document, while document instances only give a snapshot what the XML document may contain. The document definition outlined in a schema holds true for all document instances of that schema. So the result produced from the clustering of schemas will hold true for all document instances of those schemas, and can be reused for any other instances. On the contrary, the result of the clustering of document instances will hold true for included document instances only. The clustering process is to be repeated for any other document instances.

This paper presents the XMine methodology that quantitatively determines the similarity between the heterogeneous XML schemas by considering the semantic, as well as the hierarchical structural similarity of elements. The similar schemas are clustered into the separate meaningful classes. Whilst there are several XML documents and schema clustering techniques available [4], [6], [9], [11], [24], [26], this paper enhances this task by adding the hierarchical similarity in clustering by addressing the element level hierarchical positions. The XMine methodology can deal with the varying structures of schemas and with the varying aspects of semantic differences in the schema elements.

The contributions of this paper are (1) combining the semantic and syntactic relationships to calculate the linguistic similarity between two element names; (2) calculating the structural similarity between two elements by considering the ancestor–child relationship along with the parent–child relationship in maximal similar paths; and then (3) generalizing a suitable schema class hierarchy to determine the relationships between the discovered schemas in the XMine methodology.

The performance of XMine is demonstrated using a number of heterogeneous schemas derived from the several application domains. The empirical results demonstrate that the semantic, syntactic and hierarchal relationships of schema elements play important roles for producing the good quality of clustering results. Most importantly, it discovers that the syntactic similarity measure is more useful than the semantic similarity measure.

The result of the schema class composition hierarchy can serve as a basis for a number of XML application processes. The clusters of schemas provide a hint for building an index structure. The indexing based on the structural similarity supports many applications. For example in the information retrieval field, the XML-based search engines can improve the speed and accuracy in retrieving the relevant portions of the XML data by using the efficient indexes. Moreover, several database tools that are developed to deliver, store, integrate and query the XML data [5], [12], [21], [33], require indexing based on the structural similarity to support an effective document storage and retrieval.

Moreover, the schema class composition hierarchy can be viewed as a generalization of the training sets of schemas to a super-class that is useful for further XML document classification analysis. A number of heterogeneous sources of schemas can be classified into this set of predefined classifications of schemas. This process will improve the XML document handling and achieve more effective and efficient searches for the relevant XML documents.

The method of the association rule mining can also be applied to find the interesting correlation relationships of all the metadata available in schemas belonging to the same schema class. The element tags that frequently occur together within a schema class can be used to maximally distinguish one class of schema from others. This would derive a set of association rules associated with each schema class. This schema element tag-based association analysis is also useful for discovering common XML structures for a specific domain.

In addition, the schema class hierarchies can also facilitate a difficult task of schema integration process on the heterogeneous schemas. The integration on the similar schemas within each schema class would provide an easier task than reconciling the schemas that are different in structure and semantics, which would involve a complex restructuring process.

The similarity between two structures is also a notion tied to a challenging task of reusing the XML or semi-structured documents. In the XML document content reuse, a document (or a part of the document) structured under one schema must be restructured into an instance of a different schema. The identification of the common paths between two instances of schema helps to avail this restructuring.