Change discovery of hierarchically structured, order-sensitive data in HTML/XML documents

As hierarchically structured, order-sensitive HTML/XML data become more prevailing in online data exchange and processing, discovering changes in these data is essential in Web data processing, especially when they evolve frequently over time. We propose a change-discovery algorithm (CDA) for any two HTML/XML documents, each of which is hierarchically structured and represented as an ordered tree. The novelties of CDA include (i) the usage of weighted sequence difference to determine the edit script with the anticipated minimal operational cost and (ii) the generation of the minimal contextual differences of branches in the two given trees. Differed from existing change-detection approaches that adopt node-to-node comparisons, CDA adopts branch-to-branch comparisons. Using CDA, generated edit scripts can be processed in any order to yield the same results, which enhances parallelism. CDA also guarantees lossless reversal transformation. The time complexity of CDA is polynomial, which is proportional to the numbers of branches in any two given trees.