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

ABSTRACT

We consider merging structured documents, which is to transform given two distinct documents into isomorphic ones. Such merging is essential to synchronizing several copies of a document concurrently edited by several clients. Two documents, treated as ordered trees, are merged by applying a merge script consisting of add, del, upd, and move operations to the documents. We prove that the corresponding decision problem to finding an optimum merge script is NP-complete. Then, we show a sufficient condition under which an optimum merge script can be found in polynomial time.

REFERENCES

• 1: D. T. Barnard, G. Clarke, and N. Duncan, "Tree-to-tree correction for document trees," Technical Report 95--372, Queen's University, 1995.
• 2: Sudarshan S. Chawathe, Comparing Hierarchical Data in External Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.90-101, September 07-10, 1999
• 3: 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
• 4: Sudarshan S. Chawathe , Hector Garcia-Molina, Meaningful change detection in structured data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.26-37, May 11-15, 1997, Tucson, Arizona, United States
• 5: Amelie Marian, Detecting Changes in XML Documents, Proceedings of the 18th International Conference on Data Engineering, p.41, February 26-March 01, 2002
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: A. Nierman and H. V. Jagadish, "Evaluating structual similarity in XML documetns," Proc. WebDB, pp. 61--66, 2002.
• 8: N. Suzuki, "A Sturctural merging algorithm for XML docuemnts," Proc. IADIS International Conference WWW/Internet 2002, pp. 699--703, 2002.
• 9: 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]