Discovering frequently changing structures from historical structural deltas of unordered XML

ABSTRACT

Recently, a large amount of work has been done in XML data mining. However, we observed that most of the existing works focus on the snapshot XML data, while XML data is dynamic in real applications. To the best of our knowledge, none of the existing works has addressed the issue of mining the history of changes to XML documents. Such mining results can be useful in many applications such as XML change detection, XML indexing, association rule mining, and classification etc. In this paper, we propose a novel approach to discover the <i>frequently changing structures</i> from the sequence of historical <i>structural deltas</i> of unordered XML. To make the structure discovering process efficient, an expressive and compact data model, <b>H</b>istorical-<b>D</b>ocument <b>O</b>bject <b>M</b>odel (<b>H-DOM</b>), is proposed. Using this model, two basic algorithms, which can discover all the <i>frequently changing structures</i> with only two scans of the XML sequence, are presented. Experimental results show that our algorithms, together with the optimization techniques, are efficient and scalable.

REFERENCES

• 1: Daniele Braga , Alessandro Campi , Stefano Ceri , Mika Klemettinen , Pier Luca Lanzi, A Tool for Extracting XML Association Rules, Proceedings of the 14th IEEE International Conference on Tools with Artificial Intelligence (ICTAI'02), p.57, November 04-06, 2002
• 2: L. Chen, S. S. Bhowmick and C. Chia. Mining Association Rules from Structural Deltas of Historical XML Documents. In In Proc. PAKDD, 452--457, 2004.
• 3: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 4: Curbera and D. A. Epstein. Fast difference and update of XML documents. In Proc. XTech'99, 1999.
• 5: Jiawei Han , Jian Pei , Yiwen Yin, Mining frequent patterns without candidate generation, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.1-12, May 15-18, 2000, Dallas, Texas, United States
• 6: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 7: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 8: Y. Wang, D. J. DeWitt, and J.-Y. Cai. X-diff: An effective change detection algorithm for XML documents. In Proc. ICDE, 519--530, 2003.
• 9: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 10: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775058]
• 11: Mohammed J. Zaki , Charu C. Aggarwal, XRules: an effective structural classifier for XML data, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956787]
• 12: Q. Zhao and S. S. Bhowmick. Mining changes to historical web access patterns. In Pro. PKDD, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design

Keywords:
XML, data mining