Efficient Change Detection in Tree-Structured Data

We present X-tree Diff, a change detection algorithm for treestructured data such as XML/HTML documents. X-tree Diff uses a specially designed data structure, called X-tree. Nodes of X-tree have a special hash-valued field representing the structure and data of the subtree rooted at each node, which enables us to compare between subtrees efficiently. X-tree Diff allows exact matchings at early stage, so as to reduce the possibility of wrong matchings. We show that X-tree Diff runs in O(n), where n is the number of nodes in X-trees, in worst case as well as in average case.