A stream-based method to detect differences between XML documents

Abstract

Detecting differences between XML documents is one of most important research topics for XML. Since XML documents are generally considered to be organized in a tree structure, most previous research has attempted to detect differences using tree-matching algorithms. However, most tree-matching algorithms have inadequate performance owing to limitations in terms of the execution time, optimality and scalability. This study proposes a stream-based difference detection method in which an XML binary encoding algorithm is used to provide improved performance relative to that of previous tree-matching algorithms. A tree-structured analysis of XML is not essential in order to detect differences. We use a D-Path algorithm that has an optimal result quality for difference detection between two streams and has a lower time complexity than tree-based methods. We then modify the existing XML binary encoding method to tokenize the stream and the algorithm in order to support more operations than D-Path algorithm does. The experimental results reveal greater efficiency for the proposed method relative to tree-based methods. The execution time is at least 4 times faster than state-of-the-art tree-based methods. In addition, the scalability is much more efficient.