Semantics-Guided Clustering of Heterogeneous XML Schemas | SpringerLink
Skip to main content
Springer Nature Link
Log in

Semantics-Guided Clustering of Heterogeneous XML Schemas

  • Conference paper
Journal on Data Semantics IX

Part of the book series: Lecture Notes in Computer Science ((JODS,volume 4601))

  • 486 Accesses

Abstract

In this paper we illustrate an approach for clustering semantically heterogeneous XML Schemas. The proposed approach is driven by the semantics of the involved Schemas that is defined by means of the interschema properties existing among concepts represented therein; interschema properties taken into account by our approach are synonymies (indicating that two concepts have the same meaning), hyponymies (denoting that a concept has a more specific meaning than another one), and overlappings (indicating that two concepts are neither synonyms nor one hyponym of the other, but represent, to some extent, the same reality). An important feature of our approach consists of its capability of being integrated with almost all the clustering algorithms already proposed in the literature. Both a theoretical and an experimental analysis on the complexity of our approach are presented in the paper. They show that our approach is scalable and particularly suited in application contexts characterized by a great number and a large variety of XML Schemas.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Beil, F., Ester, M., Xu, X.: Frequent term-based text clustering. In: KDD 2002. Proc. of the International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, pp. 436–442. ACM Press, New York (2002)

    Chapter  Google Scholar 

  2. Bergamaschi, S., Castano, S., Vincini, M.: Semantic integration of semistructured and structured data sources. SIGMOD Record 28(1), 54–59 (1999)

    Article  Google Scholar 

  3. Castano, S., De Antonellis, V., De Capitani di Vimercati, S.: Global viewing of heterogeneous data sources. IEEE Transactions on Data and Knowledge Engineering 13(2), 277–297 (2001)

    Article  Google Scholar 

  4. Catania, B., Maddalena, A., Vakali, A.: XML document indexes: A classification. IEEE Internet Computing 9(5), 64–71 (2005)

    Article  Google Scholar 

  5. Chung, C., Min, J., Shim, K.: APEX: an adaptive path index for XML data. In: SIGMOD 2002. Proc. of the ACM International Conference on Management of Data, Madison, Wisconsin, USA, pp. 121–132. ACM Press, New York (2002)

    Chapter  Google Scholar 

  6. Cobena, G., Abiteboul, S., Marian, A.: Detecting changes in XML documents. In: ICDE 2002. Proc. of the IEEE International Conference on Data Engineering, San Jose, California, USA, pp. 41–52. IEEE Computer Society Press, Los Alamitos (2002)

    Google Scholar 

  7. Costa, G., Manco, G., Ortale, R., Tagarelli, A.: A tree-based approach to clustering XML documents by structure. In: Boulicaut, J.-F., Esposito, F., Giannotti, F., Pedreschi, D. (eds.) PKDD 2004. LNCS (LNAI), vol. 3202, pp. 137–148. Springer, Heidelberg (2004)

    Google Scholar 

  8. Crescenzi, V., Mecca, G., Merialdo, P.: RoadRunner: Towards automatic data extraction from large Web sites. In: VLDB 2001. Proc. of the International Conference on Very Large Data Bases, pp. 109–118. Morgan Kaufmann, San Francisco (2001)

    Google Scholar 

  9. Dalamagas, T., Cheng, T., Winkel, K., Sellis, T.K.: A methodology for clustering XML documents by structure. Information Systems 31(3), 187–228 (2006)

    Article  Google Scholar 

  10. De Francesca, F., Gordano, G., Ortale, R., Tagarelli, A.: Distance-based clustering of XML documents. In: Proc. of the International Workshop on Mining Graphs, Trees and Sequences (MGTS 2003), pp. 75–78, Cavtat-Dubrovnik, Croatia (2003)

    Google Scholar 

  11. De Meo, P., Quattrone, G., Terracina, G., Ursino, D.: Extraction of synonymies, hyponymies, overlappings and homonymies from XML Schemas at various “severity” levels. In: IDEAS 2004. Proc. of the International Database Engineering and Applications Symposium, Coimbra, Portugal, pp. 389–394. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  12. Dempster, A., Laird, N., Rubin, D.: Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society Series B 30(1), 1–38 (1977)

    MathSciNet  Google Scholar 

  13. Deschler, K.W., Rundensteiner, E.A.: MASS: a multi-axis storage structure for large XML documents. In: CIKM 2003. Proc. of ACM International Conference on Information and Knowledge Management, New Orleans, Louisiana, USA, pp. 520–523. ACM Press, New York (2003)

    Chapter  Google Scholar 

  14. Dhamankar, R., Lee, Y., Doan, A., Halevy, A., Domingos, P.: iMAP: Discovering complex semantic matches between database schemas. In: SIGMOD 2004. Proc. of the ACM International Conference on Management of Data, Paris, France, pp. 383–394. ACM Press, New York (2004)

    Chapter  Google Scholar 

  15. Fankhauser, P., Kracker, M., Neuhold, E.J.: Semantic vs. structural resemblance of classes. ACM SIGMOD RECORD 20(4), 59–63 (1991)

    Article  Google Scholar 

  16. Flesca, S., Manco, G., Masciari, E., Pontieri, L., Pugliese, A.: Fast detection of XML structural similarity. IEEE Transactions on Knowledge Data Engineering 17(2), 160–175 (2005)

    Article  Google Scholar 

  17. Gal, A., Anaby-Tavor, A., Trombetta, A., Montesi, D.: A framework for modeling and evaluating automatic semantic reconciliation. The International Journal on Very Large Databases 14(1), 50–67 (2005)

    Article  Google Scholar 

  18. Galil, Z.: Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys 18, 23–38 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  19. Garruzzo, S., Modafferi, S., Rosaci, D., Ursino, D.: X-Compass: an XML agent for supporting user navigation on the Web. In: Andreasen, T., Motro, A., Christiansen, H., Larsen, H.L. (eds.) FQAS 2002. LNCS (LNAI), vol. 2522, pp. 197–211. Springer, Heidelberg (2002)

    Google Scholar 

  20. Guha, S., Rastogi, R., Shim, K.: ROCK: A robust clustering algorithm for categorical attributes. Information Systems 25(5), 345–366 (2000)

    Article  Google Scholar 

  21. Han, J., Kamber, M.: Data Mining: Concepts and Techniques. Morgan Kaufmann, San Francisco (2001)

    Google Scholar 

  22. He, B., Tao, T., Chang, K.C.-C.: Organizing structured Web sources by query schemas: a clustering approach. In: CIKM 2004. Proc. of the ACM International Conference on Information and Knowledge Management, Washington, Columbia, USA, pp. 22–31. ACM Press, New York (2004)

    Chapter  Google Scholar 

  23. Hochbaum, D.S., Shmoys, D.B.: A best possible heuristic for the k-center problem. International Journal on Digital Libraries 10(2), 180–184 (1985)

    MATH  MathSciNet  Google Scholar 

  24. Jiang, H., Lu, H., Wang, W., Chin, B.: XR-Tree: Indexing XML Data for Efficient Structural Joins. In: ICDE 2003. Proc. of the International Conference on Data Engineering, Bangalore, India, pp. 253–263. IEEE Computer Society, Los Alamitos (2003)

    Google Scholar 

  25. Jolliffe, I.T.: Principal Component Analysis, 2nd edn. Springer, Heidelberg (2002)

    MATH  Google Scholar 

  26. Koutsonikola, V.A., Vakali, A.: LDAP: Framework, practices, and trends. IEEE Internet Computing 8(5), 66–72 (2004)

    Article  Google Scholar 

  27. Lee, M.L., Yang, L.H., Hsu, W., Yang, X.: XClust: clustering XML schemas for effective integration. In: CIKM 2002. Proc. of the ACM International Conference on Information and Knowledge Management, McLean, Virginia, USA, pp. 292–299. ACM Press, New York (2002)

    Chapter  Google Scholar 

  28. Lian, W., Cheung, D.W., Mamoulis, N., Yiu, S.: An efficient and scalable algorithm for clustering XML documents by structure. IEEE Transactions on Knowledge and Data Engineering 16(1), 82–96 (2004)

    Article  Google Scholar 

  29. Liu, J., Wang, J.T.L., Hsu, W., Herbert, K.G.: XML clustering by principal component analysis. In: ICTAI 2004. Proc. of the IEEE International Conference on Tools with Artificial Intelligence, Boca Raton, Florida, USA, pp. 658–662. IEEE Computer Society, Los Alamitos (2004)

    Google Scholar 

  30. MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proc. of the International Symposium on Mathematics, Statistics and Probability, Berkeley, California, USA, pp. 281–297. University of California Press (1967)

    Google Scholar 

  31. Madhavan, J., Bernstein, P.A., Rahm, E.: Generic schema matching with Cupid. In: VLDB 2001. Proc. of the International Conference on Very Large Data Bases, Roma, Italy, pp. 49–58. Morgan Kaufmann, San Francisco (2001)

    Google Scholar 

  32. Miller, A.G.: WordNet: A lexical database for English. Communications of the ACM 38(11), 39–41 (1995)

    Article  Google Scholar 

  33. Nierman, A., Jagadish, H.V.: Evaluating structural similarity in XML documents. In: Proc. of the International Workshop on the Web and Databases (WebDB 2002), pp. 61–66, Madison, Wisconsin, USA (2002)

    Google Scholar 

  34. Palopoli, L., Saccà, D., Terracina, G., Ursino, D.: Uniform techniques for deriving similarities of objects and subschemes in heterogeneous databases. IEEE Transactions on Knowledge and Data Engineering 15(2), 271–294 (2003)

    Article  Google Scholar 

  35. Passi, K., Lane, L., Madria, S.K., Sakamuri, B.C., Mohania, M.K., Bhowmick, S.S.: A model for XML Schema integration. In: Bauknecht, K., Tjoa, A.M., Quirchmayr, G. (eds.) EC-Web 2002. LNCS, vol. 2455, pp. 193–202. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  36. Qian, W., Zhang, L., Liang, Y., Qian, H., Jin, W.: A two-level method for clustering DTDs. In: Lu, H., Zhou, A. (eds.) WAIM 2000. LNCS, vol. 1846, pp. 41–52. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  37. Qian, Y., Zhang, K.: A customizable hybrid approach to data clustering. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 485–489. Springer, Heidelberg (2004)

    Google Scholar 

  38. Rahm, E., Bernstein, P.A.: A survey of approaches to automatic schema matching. VLDB Journal 10(4), 334–350 (2001)

    Article  MATH  Google Scholar 

  39. Shanmugasundaram, J., Tufte, K., He, G., Zhang, C., DeWitt, D., Naughton, J.: Relational databases for querying XML documents: limitations and opportunities. In: VLDB 1999. Proc. of Very Large DataBase Conference, Edinburgh, Scotland, UK, pp. 302–314. Morgan Kaufmann, San Francisco (1999)

    Google Scholar 

  40. Tatarinov, I., Viglas, S.D., Beyer, K., Shanmugasundaram, J., Shekita, E., Zhang, C.: Storing and querying ordered xml using a relational database system. In: SIGMOD 2002. Proc. of the ACM International Conference on Management of Data, Madison, Wisconsin, USA, pp. 204–215. ACM Press, New York (2002)

    Chapter  Google Scholar 

  41. Terziyan, V., Vitko, O.: Intelligent information management in mobile electronic commerce. Artificial Intelligence News. Journal of Russian Association of Artificial Intelligence 5 (2002)

    Google Scholar 

  42. Witten, I.H., Frank, E.: Data Mining: Practical machine learning tools with Java implementations. Morgan Kaufmann, San Francisco, California, USA (2000)

    Google Scholar 

  43. Xu, L., Jordan, M.I.: On convergence properties of the EM algorithm for gaussian mixtures. Neural Computation 8(1), 129–151 (1996)

    Article  Google Scholar 

  44. Yang, J., Cheung, W.K., Chen, X.: Integrating element and term semantics for similarity-based XML document clustering. In: WI 2005. Proc. of the IEEE/WIC/ACM International Conference on Web Intelligence, Compiegne-Cedex, France, pp. 222–228. IEEE Computer Society Press, Los Alamitos (2005)

    Google Scholar 

  45. Yoon, J.P., Raghavan, V., Chakilam, V.: BitCube: A three-dimensional bitmap indexing for XML documents. In: SSDBM 2001. Proc. of the International Conference on Scientific and Statistical Database Management, Fairfax, Virginia, USA, pp. 158–167. IEEE Computer Society, Los Alamitos (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. DIMET, Università Mediterranea di Reggio Calabria, Via Graziella, Località Feo di Vito, 89060 Reggio Calabria, Italy

    Pasquale De Meo, Giovanni Quattrone & Domenico Ursino

  2. Dipartimento di Matematica, Università della Calabria, Via Pietro Bucci, 87036 Rende (CS), Italy

    Giorgio Terracina

Authors
  1. Pasquale De Meo
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Giovanni Quattrone
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Giorgio Terracina
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Domenico Ursino
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Stefano Spaccapietra Paolo Atzeni François Fages Mohand-Saïd Hacid Michael Kifer John Mylopoulos Barbara Pernici Pavel Shvaiko Juan Trujillo Ilya Zaihrayeu

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

De Meo, P., Quattrone, G., Terracina, G., Ursino, D. (2007). Semantics-Guided Clustering of Heterogeneous XML Schemas. In: Spaccapietra, S., et al. Journal on Data Semantics IX. Lecture Notes in Computer Science, vol 4601. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74987-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74987-5_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74982-0

  • Online ISBN: 978-3-540-74987-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics