With the emergence of XML standardization, XML documents have been widely used and accepted in almost all the major industries. As a result of the widespread usage, it has been considered essential to not only store these XML documents but also to mine them to discover useful information from them. One of the very popular techniques to mine XML documents is frequent pattern mining, which has huge potential in varied domains such as bio-informatics, network analysis. This chapter presents some of the existing techniques to discover frequent patterns from XML documents. It also covers the applications and addresses the major issues in mining XML documents. Frequent Patterns: Patterns which occurs more than a user-specified threshold limit (minimum support or min_supp) in a given database.
With the emergence of XML (eXtensible Markup Language) standardization, XML documents have been widely used and accepted in almost all the major industries. This has resulted in a large amount of XML documents. In order to discover useful knowledge from the huge collections, various data mining techniques have been used (Nayak, 2005). One of the popular data mining techniques is frequent pattern mining on XML documents (Tan, Dillon, Hadzic, Chang, & Feng, 2005), which has created a great deal of interest among researchers due to its potential of application in diversified fields. Some of them include data warehouse integration (Termier, Rousset, & Sebag, 2002), bio-informatics (Hadzic, Dillon, Sidhu, Chang, & Tan, 2006b; Zaki, 2005), network analysis and information retrieval . Furthermore, XML frequent pattern mining serves as an important function for other data mining tasks such as classification (Zaki, 2005), clustering (Kutty, Tran, Nayak, & Li, 2007; Nayak & Iryadi, 2007) and association rules mining(Rusu, Rahayu, & Taniar, 2007).
In spite of its potential, there are major challenges that are yet to be fully addressed while mining XML documents in comparison to the established field of frequent pattern mining from relational databases. Firstly, unlike the relational databases which has structured or the unstructured data such as text, sound or image files, XML documents model the hierarchical relationships between data items. XML data represent semi-structured format consisting of values and their relationships. An XML document contains tags and the data enclosed within those tags. The tag, that describes the element name, includes the semantics in the form of text data. The tags define the structure of an XML document showing the relationships between elements of the document. Hence, while mining the XML documents, the structure of the data items has to be preserved and taken into consideration. This contributes to the second challenge that is, dealing with huge volume of data compared to structured data1 due to the storage of the structural information (Nayak, 2005).
This chapter presents a discussion of the current trends in frequent pattern mining on XML documents, addresses the related issues and challenges and finally presents the applications and opportunities for this type of mining. The background of frequent mining is provided in Frequent Pattern Mining section. The XML Frequent Pattern Mining section covers the analysis of various types of frequent pattern mining. Also, we will present some of the potential opportunities of XML frequent pattern mining from a technological as well as an application-based perspective in Applications and Issues of XML Frequent Mining and highlight some of the issues and challenges.
Key Terms in this Chapter
Frequent Patterns: Patterns which occurs more than a user-specified threshold limit (minimum support or min_supp) in a given database.
Subtree: The tree which is a child of a node in another tree.
XML Frequent Patterns Mining: Mining of XML documents for frequent patterns which are either structural or content-oriented or a combination of both.
Contents in XML Document: The text between the start and end tag in an XML document. For instance, Data Mining
, content refers to the text “Data Mining” between the tags
Frequent Patterns Mining: A data mining area focussing on the extraction of frequent patterns from a given data.
XML Frequent Structures Mining: Identifying frequently occurring structures in the schema (e.g DTD (Document Type Definition), XML Schema), which describes the structure of an XML document.
Structures in XML Document: The element tags and their nesting dictate the structure of an XML document.
Subgraph: A graph whose vertices and edges are subsets of another graph.
XML Frequent Content Mining: Mining for frequently occurring values which are instances of a relation in the XML document.