Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

XML-based documents play a major role in modern information architectures and their corresponding workflows. In this context, the ability to identify and represent differences between two versions of a document is essential. Several approaches to finding the differences between XML documents have already been proposed. Typically, they are based on tree-to-tree correction, or sequence alignment. Most of these algorithms, however, are too slow and do not support the subsequent merging of changes. In this paper, we present a differencing algorithm tailored to ordered XML documents, called DocTreeDiff. It relies on our context-oriented XML versioning model which allows for document merging, presented in earlier work. An empiric evaluation demonstrates the efficiency of our approach as well as the high quality of the generated deltas.

REFERENCES

• 1: L. Bergroth , H. Hakonen , T. Raita, A Survey of Longest Common Subsequence Algorithms, Proceedings of the Seventh International Symposium on String Processing Information Retrieval (SPIRE'00), p.39, September 27-29, 2000
• 2: Marc Bernard , Laurent Boyer , Amaury Habrard , Marc Sebban, Learning probabilistic models of tree edit distance, Pattern Recognition, v.41 n.8, p.2611-2629, August, 2008 [doi>10.1016/j.patcog.2008.01.011]
• 3: Philip Bille, A survey on tree edit distance and related problems, Theoretical Computer Science, v.337 n.1-3, p.217-239, 9 June 2005 [doi>10.1016/j.tcs.2004.12.030]
• 4: M. Brauer, R. Weir, and M. McRae. OpenDocument v1.1 specification, 2007.
• 5: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, ACM SIGMOD Record, v.26 n.2, p.26-37, June 1997
• 6: Sudarshan S. Chawathe , Anand Rajaraman , Hector Garcia-Molina , Jennifer Widom, Change detection in hierarchically structured information, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.493-504, June 04-06, 1996, Montreal, Quebec, Canada
• 7: Weimin Chen, New algorithm for ordered tree-to-tree correction problem, Journal of Algorithms, v.40 n.2, p.135-158, August 2001 [doi>10.1006/jagm.2001.1170]
• 8: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 9: S. DeRose and J. Clark. XML path language (XPath) version 1.0. W3C recommendation, W3C, Nov. 1999. http://www.w3.org/TR/1999/REC-xpath-19991116.
• 10: R. L. Fontaine. Merging xml files: a new approach providing intelligent merge of xml data sets. In Proceedings of XML Europe 2002, 2002.
• 11: Kuo-Si Huang , Chang-Biau Yang , Kuo-Tsung Tseng , Hsing-Yen Ann , Yung-Hsing Peng, Efficient algorithms for finding interleaving relationship between sequences, Information Processing Letters, v.105 n.5, p.188-193, February, 2008 [doi>10.1016/j.ipl.2007.08.028]
• 12: Jesper Jansson , Andrzej Lingas, A Fast Algorithm for Optimal Alignment between Similar Ordered Trees, Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, p.232-240, July 01-04, 2001
• 13: Tao Jiang , Lusheng Wang , Kaizhong Zhang, Alignment of trees: an alternative to tree edit, Theoretical Computer Science, v.143 n.1, p.137-148, May 29, 1995 [doi>10.1016/0304-3975(95)80015-8]
• 14: Tancred Lindholm, A three-way merge for XML documents, Proceedings of the 2004 ACM symposium on Document engineering, October 28-30, 2004, Milwaukee, Wisconsin, USA [doi>10.1145/1030397.1030399]
• 15: Tancred Lindholm , Jaakko Kangasharju , Sasu Tarkoma, Fast and simple XML tree differencing by sequence alignment, Proceedings of the 2006 ACM symposium on Document engineering, October 10-13, 2006, Amsterdam, The Netherlands [doi>10.1145/1166160.1166183]
• 16: E. W. Myers. An o(nd) difference algorithm and its variations. Algorithmica, 1:251--266, 1986.
• 17: J. Paoli, I. Valet-Harper, A. Farquhar, and I. Sebestyen. ECMA-376 Office Open XML File Formats, 2006.
• 18: S. Pemberton. XHTML™ 1.0 the extensible hypertext markup language (second edition). W3C recommendation, W3C, Aug. 2002. http://www.w3.org/TR/2002/REC-xhtml1-20020801.
• 19: M. O. Rabin. Fingerprinting by random polynomials. Technical Report TR-CSE-03-01, Center for Research in Computing Technology, Harvard University, 1981.
• 20: Sebastian Rönnau , Uwe M. Borghoff, Versioning XML-based office documents, Multimedia Tools and Applications, v.43 n.3, p.253-274, July 2009 [doi>10.1007/s11042-009-0271-2]
• 21: Sebastian Rönnau , Christian Pauli , Uwe M. Borghoff, Merging changes in XML documents using reliable context fingerprints, Proceeding of the eighth ACM symposium on Document engineering, September 16-19, 2008, Sao Paulo, Brazil [doi>10.1145/1410140.1410151]
• 22: Sebastian Rönnau , Jan Scheffczyk , Uwe M. Borghoff, Towards XML version control of office documents, Proceedings of the 2005 ACM symposium on Document engineering, November 02-04, 2005, Bristol, United Kingdom [doi>10.1145/1096601.1096606]
• 23: Luis J. Arévalo Rosado , Antonio Polo Márquez , Jorge Martínez Gil, Managing Branch Versioning in Versioned/Temporal XML Documents, Proceedings of the 5th international Symposium on XML Database: Database and XMLTechnologies, September 23-24, 2007, Vienna, Austria [doi>10.1007/978-3-540-75288-2_9]
• 24: S. M. Selkow. The tree-to-tree editing problem. Inf. Process. Lett., 6(6):184--186, 1977.
• 25: Kuo-Chung Tai, The Tree-to-Tree Correction Problem, Journal of the ACM (JACM), v.26 n.3, p.422-433, july 1979 [doi>10.1145/322139.322143]
• 26: G. Valiente. An efficient bottom-up distance between trees. In SPIRE, pages 212--219, 2001.
• 27: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 28: Kaizhong Zhang, Efficient Parallel Algorithms for Tree Editing Problems, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.361-372, June 10-12, 1996
• 29: K. Zhang , D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing, v.18 n.6, p.1245-1262, Dec. 1989 [doi>10.1137/0218082]
• 30: K. Zhang, J. T.-L. Wang, and D. Shasha. On the editing distance between undirected acyclic graphs and related problems. In CPM '95: Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, pages 395--407, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Document management

Additional Classification:
  I. Computing Methodologies
  I.7 DOCUMENT AND TEXT PROCESSING
      I.7.1 Document and Text Editing
          Subjects: Version control

General Terms:
Algorithms, Management, Performance, Reliability

Keywords:
XML diff, XML merge, office documents, tree-to-tree correction, version control