An approach to XML path matching

ABSTRACT

In applications that accomplish XML data integration and XML instance querying, the problem of XML path matching plays a central role. This paper presents an approach for matching XML paths that consists of (1) PathSim, a similarity function specifically designed for matching XML paths and (2) a set of pre-processing functions to be applied to XML paths that are to be compared by a similarity function. The reported experiments demonstrate that PathSim achieves matches of higher quality than a similarity function for XML paths found in literature. The experiments further show that matches of higher quality are achieved when the proposed pre-processing functions are employed.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Chaitan Baru , Amarnath Gupta , Bertram Ludäscher , Richard Marciano , Yannis Papakonstantinou , Pavel Velikhov , Vincent Chu, XML-based information mediation with MIX, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.597-599, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: M. Boyd, S. Kittivoravitkul, C. Lazanitis, P. McBrien, and N. Rizopoulos. Automed: A bav data integration system for heterogeneous data sources. In CAiSE, pages 82--97, 2004.
• 4: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 5: Hong-Hai Do , Erhard Rahm, COMA: a system for flexible combination of schema matching approaches, Proceedings of the 28th international conference on Very Large Data Bases, p.610-621, August 20-23, 2002, Hong Kong, China
• 6: Carina F. Dorneles , Carlos A. Heuser , Andrei E. N. Lima , Altigran Soares da Silva , Edleno Silva de Moura, Measuring similarity between collection of values, Proceedings of the 6th annual ACM international workshop on Web information and data management, November 12-13, 2004, Washington DC, USA [doi>10.1145/1031453.1031465]
• 7: Hao Fan , Alexandra Poulovassilis, Using AutoMed metadata in data warehousing environments, Proceedings of the 6th ACM international workshop on Data warehousing and OLAP, November 07-07, 2003, New Orleans, Louisiana, USA [doi>10.1145/956060.956076]
• 8: The Piazza Peer Data Management System, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.787-798, July 2004 [doi>10.1109/TKDE.2004.1318562]
• 9: Sachindra Joshi , Neeraj Agrawal , Raghu Krishnapuram , Sumit Negi, A bag of paths model for measuring structural similarity in Web documents, 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.956822]
• 10: D. Kukulenz, K.-P. Herget, and J. Pauli. Improving retrieval by a similarity thesaurus based on hyperlink structure. In Databases and Applications, pages 29--34, 2005.
• 11: V. I. Levenshtein. Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady, 10(8):707--710, 1966.
• 12: B. Liang, J. Tang, J.-Z. Li, and K. Wang. Semantic similarity based ontology cache. In APWeb, pages 250--262, 2006.
• 13: Yinghua Ma , Richard Chbeir, Content and Structure Based Approach For XML Similarity, Proceedings of the The Fifth International Conference on Computer and Information Technology, p.136-140, September 21-23, 2005 [doi>10.1109/CIT.2005.91]
• 14: A. Nierman and H. V. Jagadish. Evaluating structural similarity in xml documents. In WebDB, pages 61--66, 2002.
• 15: T. Ogawa and N. Inuzuka. Similarity of documents using reconfiguration of thesaurus. In KES, pages 95--102, 2004.
• 16: Erhard Rahm , Philip A. Bernstein, A survey of approaches to automatic schema matching, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.334-350, December 2001 [doi>10.1007/s007780100057]
• 17: Igor Tatarinov , Zachary Ives , Jayant Madhavan , Alon Halevy , Dan Suciu , Nilesh Dalvi , Xin (Luna) Dong , Yana Kadiyska , Gerome Miklau , Peter Mork, The Piazza peer data management project, ACM SIGMOD Record, v.32 n.3, September 2003 [doi>10.1145/945721.945732]
• 18: Lonneke van der Plas , Jörg Tiedemann, Finding synonyms using automatic word alignment and measures of distributional similarity, Proceedings of the COLING/ACL on Main conference poster sessions, p.866-873, July 17-18, 2006, Sydney, Australia
• 19: Y. Wang, D. J. DeWitt, and Jyi Cai. X-diff: An effective change detection algorithm for xml documents. In ICDE, pages 519--530, 2003.
• 20: Y. Richard Wang , Stuart E. Madnick, The Inter-Database Instance Identification Problem in Integrating Autonomous Systems, Proceedings of the Fifth International Conference on Data Engineering, p.46-55, February 06-10, 1989
• 21: G. Wen, L. Jiang, and N. R. Shadbolt. Ontology-based similarity between text documents on manifold. In ASWC, pages 113--125, 2006.
• 22: Huimin Zhao , Sudha Ram, Entity identification for heterogeneous database integration: a multiple classifier system approach and empirical evaluation, Information Systems, v.30 n.2, p.119-132, April 2005 [doi>10.1016/j.is.2003.11.001]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.m Miscellaneous

General Terms:
Algorithms, Experimentation

Keywords:
approximate matching, data integration, xpath