A schema matching-based approach to XML schema clustering

ABSTRACT

The relationship between XML data clustering and schema matching is bidirectional. On one side, clustering techniques have been adopted to improve matching performance, and on the other side schema matching is the backbone of the clustering technique. This paper presents a new approach for clustering XML schema based on schema matching. In particular, we develop and implement an XML schema matching system, which determines semantic similarities between XML schemas based on the Prüfer sequence representation of schema trees. The proposed computation similarity algorithm makes use of the semantic meaning of XML elements as well as the hierarchical features of XML schemas. The computed similarities are then exploited by an agglomerative clustering algorithm to group similar schemas. Our experimental results show that the proposed approach is fast and accurate in clustering heterogeneous XML schemas.

REFERENCES

• 1: Charu C. Aggarwal , Na Ta , Jianyong Wang , Jianhua Feng , Mohammed Zaki, Xproj: a framework for projected structural clustering of xml documents, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281201]
• 2: A. Algergawy, E. Schallehn, and G. Saake. A prufer sequence-based approach for schema matching. In BalticDB&IS2008. Estonia, 2008.
• 3: P. Berkhin. Survey of clustering data mining techniques. In Accrue Software, Inc., pages 1--56, 2002.
• 4: Elisa Bertino , Elena Ferrari, XML and Data Integration, IEEE Internet Computing, v.5 n.6, p.75-76, November 2001 [doi>10.1109/4236.968835]
• 5: Elisa Bertino , Giovanna Guerrini , Marco Mesiti, Measuring the structural similarity among XML documents and DTDs, Journal of Intelligent Information Systems, v.30 n.1, p.55-92, February 2008 [doi>10.1007/s10844-006-0023-y]
• 6: D. Carmel, N. Efraty, G. M. Landau, Y. S. Maarek, and Y. Mass. An extension of the vector space model for querying xml documents via XML fragments. SIGIR Forum, 36(2), 2002.
• 7: Ilhwan Choi , Bongki Moon , Hyoung-Joo Kim, A clustering method based on path similarities of XML data, Data & Knowledge Engineering, v.60 n.2, p.361-376, February, 2007 [doi>10.1016/j.datak.2006.02.004]
• 8: Theodore Dalamagas , Tao Cheng , Klaas-Jan Winkel , Timos Sellis, A methodology for clustering XML documents by structure, Information Systems, v.31 n.3, p.187-228, May 2006 [doi>10.1016/j.is.2004.11.009]
• 9: G. Guerrini, M. Mesiti, and I. Sanz. An Overview of Similarity Measures for Clustering XML Documents. Web Data Management Practices: Emerging Techniques and Technologies. IDEA GROUP, 2007.
• 10: M. Hassler and A. Bouchachia. Searching XML documents: Preliminary work. In INEX2005, pages 119--133, 2005.
• 11: Ying Zhao , George Karypis, Evaluation of hierarchical clustering algorithms for document datasets, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584877]
• 12: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 13: Dongwon Lee , Wesley W. Chu, Comparative analysis of six XML schema languages, ACM SIGMOD Record, v.29 n.3, p.76-87, Sept. 2000 [doi>10.1145/362084.362140]
• 14: Mong Li Lee , Liang Huai Yang , Wynne Hsu , Xia Yang, XClust: clustering XML schemas for effective integration, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584841]
• 15: Jayant Madhavan , Philip A. Bernstein , Erhard Rahm, Generic Schema Matching with Cupid, Proceedings of the 27th International Conference on Very Large Data Bases, p.49-58, September 11-14, 2001
• 16: Richi Nayak, Fast and effective clustering of XML data using structural information, Knowledge and Information Systems, v.14 n.2, p.197-215, January 2008 [doi>10.1007/s10115-007-0080-8]
• 17: Richi Nayak , Wina Iryadi, XML schema clustering with semantic and hierarchical similarity measures, Knowledge-Based Systems, v.20 n.4, p.336-349, May, 2007 [doi>10.1016/j.knosys.2006.08.006]
• 18: J. Pei, J. Hong, and D. A. Bell. A novel clustering-based approach to schema matching. In 4th ADVIS, pages 60--69, 2006.
• 19: Charnyote Pluempitiwiriyawej , Joachim Hammer, Element matching across data-oriented XML sources using a multi-strategy clustering model, Data & Knowledge Engineering, v.48 n.3, p.297-333, March 2004 [doi>10.1016/j.datak.2003.06.001]
• 20: H. Prufer. Neuer beweis eines satzes uber permutationen. Archiv fur Mathematik und Physik, 27:142--144, 1918.
• 21: Marko Smiljanic , Maurice van Keulen , Willem Jonker, Using Element Clustering to Increase the Efficiency of XML Schema Matching, Proceedings of the 22nd International Conference on Data Engineering Workshops, p.45, April 03-07, 2006 [doi>10.1109/ICDEW.2006.159]
• 22: Shirish Tatikonda , Srinivasan Parthasarathy , Matthew Goyder, LCS-TRIM: dynamic programming meets XML indexing and querying, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 23: H. Zhao and S. Ram. Clustering schema elements for semantic integration of heterogeneous data sources. Journal of Database Management, 15(4):88--106, 2004.

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

General Terms:
Algorithms

Keywords:
Prüfer sequences, XML, clustering, schema matching