Reconciliation of Changes on XML List.
Eunjung Lee · Parallel and Distributed Processing Techniques and Applications · 2005
In this research, we developed an efficient reconciliation method for mobile environments by using edit scripts of XML data sent from each mobile device. To obtain a simple model for mobile devices, we use the XML list data-sharing model, which allows the insertion/deletion of subtrees only for repetitive parts of the tree based on the document type. Furthermore, for subtrees of repetitive parts, we use keys that are unique between nodes with the same parent. This model not only guarantees that the edit action always results in a valid tree but also allows for a key-based linear time-reconciliation algorithm. Assuming that there are no insertion key conflicts, the proposed algorithm proposed requires a time of O(m) where m is the size of the edit script.