X-Diff: An Effective Change Detection Algorithm for XML Documents
Yuan Wang
David J. DeWitt
Jin-Yi Cai
University of Wisconsin – Madison, WI, U.S.A.
{yuanwang, dewitt, cjy}@cs.wisc.edu
ones are new. In the example below, although the order
of the two books has changed, both of them are still
available. Next, for each book that is still available, the
change-detection tool will determine what information has
been modified. Based on the data in Figure 1.1 and 1.2, it
should notify the consumer that there are two fewer hours
to submit a bid for both books. The current bid price of
the Harry Porter book is $10 by Mark whose rating is 125,
and the current bid price of the Tom Sawyer book is $4.50
and the bidder has not changed.
Such a change-detection tool can also be very useful to
a query system in at least two ways,
• Incremental Query Evaluation. When a user has a
standing query against a time-varying data source, a
change-detection tool can provide the query engine the
delta data on which the query will be re-evaluated.
Thus, the user doesn’t receive old results and the query
engine avoids repeated work. Since the delta data is
usually much smaller than the original data, query
evaluation will also be much faster.
• Trigger Condition Evaluation. In a continuous query
or trigger system [CDTW00], the condition of firing a
trigger is often defined on a specific change to one or
more data sources. The change detection tool can
quickly report such changes, filtering out other
changes.
Abstract
XML has become the de facto standard format for web
publishing and data transportation. Since online
information changes frequently, being able to quickly
detect changes in XML documents is important to Internet
query systems, search engines, and continuous query
systems. Previous work in change detection on XML, or
other hierarchically structured documents, used an
ordered tree model, in which left-to-right order among
siblings is important and it can affect the change result.
This paper argues that an unordered model (only
ancestor relationships are significant) is more suitable for
most database applications. Using an unordered model,
change detection is substantially harder than using the
ordered model, but the change result that it generates is
more accurate. This paper proposes X-Diff, an effective
algorithm that integrates key XML structure
characteristics with standard tree-to-tree correction
techniques. The algorithm is analyzed and compared with
XyDiff [CAM02], a published XML diff algorithm. An
experimental evaluation on both algorithms is provided.
1. Introduction
The eXtensible Markup Language (XML) [W3C] has
been recognized as the de facto standard format for
publishing and transporting documents on the web. Since
online information changes frequently a tool is needed to
detect such changes. In order to handle large volumes of
changing documents this tool needs to work very
efficiently. The following example illustrates the problem.
Suppose a parent is interested in buying books for her
children at an online auction site through a search engine
that is equipped with such a tool. On the first visit she
obtains a list of currently offered books and related
information. Two hours later, the search engine retrieves
updated data and uses the tool to figure out what has been
changed during the past two hours.
Part of the
information received on the two visits is shown in Figures
1.1 and 1.2.
As a first step, the change-detection tool will determine
whether or not the two versions are identical. If not, it
next tries to match each book segment in the old version
with every one in the new version to determine which
books are still available, which have been sold, and which
This paper describes X-Diff, an algorithm for
computing the differences between two versions of an
XML document. The key features of this algorithm
include:
• XML Structure Information. An XML document is
generally a hierarchically structured document, and
can be represented in a tree structure. However, an
XML document has other features that distinguish it
from a general labeled tree. X-Diff introduces the
notion of node signature and a new matching between
the trees corresponding to the two versions of a
document. Together, these two features are used to
find the minimum-cost matching and generate a
minimum-cost edit script that is capable of
transforming the original version of the document to
the new version.
• Unordered Trees. Since XML documents can be
represented as trees, the change detection problem is
related to the problem of change detection on trees.
Algorithms to compute the difference between trees
1
Harry Potter and the Sorcerer's Stone
The Adventures of Tom Sawyer
J.K. Rowling
Mark Twain
Mike
Sean
30
100
$5.00
$2.00
$8.50
$4.50
Tim
Steve
5
25
Harry Potter and the Sorcerer's Stone
The Adventures of Tom Sawyer
J.K. Rowling
Mark Twain
Mike
Sean
30
100
$5.00
$2.00
$10.00
$3.50
Mark
Tim
5
125
Figure 1.1 A piece of auction data of old version
Figure 1.2 A piece of auction data of new version
formulates the problem and gives an overview of our
approach. It defines the basic operations, edit scripts, cost
model, node signature and matching. Section 4 presents
the details of the X-Diff algorithm with complexity
analysis. Section 5 gives some preliminary performance
results. Section 6 summarizes our conclusions.
can be divided into two categories depending on
whether they deal with ordered or unordered trees. An
ordered tree is one in which both the ancestor (parentchild) relationship and the left-to-right ordering among
siblings are significant. An unordered tree is one in
which only ancestor relationships are significant, while
the left-to-right order among siblings is not significant.
For database applications of XML the authors believe
that the unordered tree model is more important. Thus,
X-Diff is designed to handle unordered tree
representations of XML documents. This is one major
difference between our work and some earlier efforts
in this area [CRGMW96, CE99, CAM02].
• High Performance. Change detection on unordered
trees is substantially harder than that on ordered trees;
Zhang et al. have shown it to be NP-Complete in
general case [ZSS92]. By exploiting certain features of
XML documents, a polynomial algorithm is presented
to compute the “optimal” difference between two
XML documents. An improvement is also proposed on
the algorithm that achieves high efficiency while
generating near-optimal result.
2. Related Work
Most previous work in change detection has focused on
computing differences between flat files. The GNU diff
utility is probably the most famous one. This algorithm
uses the LCS (Longest Common Subsequence) algorithm
[Myers86] to compare two plain text files. CVS, another
GNU utility, uses diff to detect differences between two
versions of programs [CVS]. Chawathe et al.
[CRGMW96] pointed out that the techniques employed
by these two programs cannot be generalized to handle
structured data because they do not understand the
hierarchical structure information contained in such data
sets. Typical hierarchically structured data, e.g. SGML
and XML, place tags on each data segment to indicate
context. Standard plain-text change-detection tools have
problems matching data segments between two versions of
data.
The remainder of the paper is organized as follows.
Related work is contained in Section 2. Section 3
2
The AT&T Internet Difference Engine [DB96,
DBCK98] uses HtmlDiff [Berk] to determine the
differences between two HTML pages. HtmlDiff treats
two HTML pages as two sequences of tokens (a token is
either a sentence-breaking markup or a sentence) and uses
a weighted LCS algorithm [Hirs77] to find the best
matching between the two sequences. This method cannot
be applied to XML documents because markups in XML
data provide context, and contents within different
markups cannot be matched.
Since XML documents can be represented as trees, it is
a natural idea to utilize tree-to-tree correction techniques
[Selk77, Tai79, HD82], to detect changes in XML
documents. Zhang and Shasha proposed a fast algorithm
to find the minimum cost editing distance between two
ordered labeled trees [ZS89]. Given two ordered trees T1
and T2, in which each node has an associated label, their
algorithm finds an optimal edit script in time O(|T1| × |T2|
× min{depth(T1), leaves(T1)} × min{depth(T2),
leaves(T2)}), which is the best known result for the
general tree-to-tree correction problem.
Chawathe et. al. [CRGMW96] formulated the change
detection problem on hierarchically structured documents,
and proposed an efficient algorithm based on the
following key assumption:
[MTU98] and reduces the size of the two trees by
removing identical subtrees (i.e., ones with identical hash
values). Second, it uses Zhang and Shasha's algorithm
[ZS89] to generate the difference between the two
simplified trees. While using DOMHash to filter out
identical subtrees can reduce the size of the two trees, its
use conflicts with the cost model employed by Zhang and
Shasha’s algorithm. Thus, XMLTreeDiff may not generate
an optimal result.
Recently, Cobéna et al. [CAM02] proposed XyDiff, an
algorithm for detecting changes in XML documents. The
algorithm first computes a signature (i.e., hash value) and
a weight (i.e., subtree size) for every node in both
documents in a bottom-up fashion (the root nodes of the
two documents end up with the largest weights). Next,
starting with the root nodes of the two documents XyDiff
compares the signatures of the two nodes. If they are
equal, the two nodes are matched; otherwise, their child
nodes will be inserted into a priority queue in which the
subtrees with the largest weights are always compared
first. Whenever XyDiff finds an exact match between two
subtrees, it attempts to propagate the match to the
respective parents of the two nodes with the weight of
each subtree determining how many levels the matching is
propagated. Whenever there is more than one potential
candidate for matching, XyDiff uses a few simple
heuristic rules to pick one in order to avoid having to
perform a full evaluation of the alternatives. This
algorithm achieves O(nlogn) complexity in execution time
and generates fairly good results in many cases. However,
XyDiff cannot guarantee any form of optimal or nearoptimal result because of the greedy rules used in the
algorithm. In fact, Section 5 demonstrates that in many
cases it will mismatch subtrees resulting in the generation
of incorrect results.
Both XMLTreeDiff and XyDiff focus on change
detection for ordered trees. On the other hand, there are
very few algorithms besides [CGM97] capable of
handling unordered trees. Zhang et al. [ZSS92] proved
that general unordered tree-to-tree correction problem is
NP-complete. Zhang also proposed a polynomial-time
algorithm based on a restriction that matching is only
performed between nodes at the same level [Zha93]. As
mentioned in the previous section, XML documents have
more features than general labeled trees that can be
exploited to pursue an efficient algorithm. Our X-Diff
algorithm uses the notions of matching and editing
distance, which are introduced in [ZS89]2, adding special
criteria that apply to XML documents.
Tararinov et. al. [TIHW01] proposed a set of primitive
operations for modifying the structure and content of an
XML document. The output of our algorithm can be easily
adapted into such format.
Given two labeled trees, T1 and T2, there is a “good”
matching function compare, so that given any leaf s in
T1, there is at most one leaf in T2 that is “close”
enough to match s.
This algorithm runs in time O(ne + e2), where n is the
number of tree leaves and e is “weighted edit distance”
(typically, e << n). This assumption holds well for many
SGML documents that do not contain duplicate or similar
objects, but it does not hold for many XML documents.
For example, in the documents contained in Figure 1.1
and 1.2, there may be many users with the same rating,
and many books that have the same bid price. In those
cases, the algorithm is not guaranteed to generate the
optimal result.
Chawathe et. al. [CGM97] also presented a heuristic
algorithm, MH-Diff, to detect change in unordered
structured documents. MH-Diff is based on representing
an edit script between two trees as an edge cover of a
bipartite graph. They introduced new edit operators such
as “subtree” copy and “subtree glue” in the algorithm.
However, the worst case of algorithm is in O(n3), and the
performance evaluation in the paper only tested very small
documents (less than 250 nodes in a tree).
XMLTreeDiff1 [CE99] computes the difference
between two XML documents. First, it computes hash
values for the nodes of both documents using DOMHash
1
2
Available at http://www.alphaworks.ibm.com.
3
The counterpart of “matching” in [ZS89, Zha93] is “mapping”.
node of node y.
• Delete(x) – delete a leaf node x.
• Update(x, new_value) – change the value of a leaf
node x to new_value. Note, x has to be either a text
node or an attribute node. Update can only modify a
node’s value, but not its name.
Notice that all basic operations are defined on leaf
nodes. For convenience, there are also two composite
operations:
• Insert(Tx, y) – insert a subtree Tx, which is rooted at
node x, to node y.
• Delete(Tx) – delete a subtree Tx, which is rooted at
node x. Delete(x) can be used if there is no confusion.
Both operations represent a list of basic operations
respectively.
The definition of these three operations is similar to
that in [CRGMG96, CAM02] except:
• For insertion, there is no need to specify which
position among y’s child nodes to insert node x
because X-Diff is dealing with unordered trees.
• There are no “move” operations, which transfer a node
or a subtree from one position to another. Many
“move” operations are not necessary in the unordered
tree model because the order among siblings is not
important. Other “move” operations can be replaced
by a combination of “delete” and “insert” operations.
3. Problem Overview and Preliminaries
The change detection problem is formulated in this
section. Section 3.1 describes the tree-structure
representation of XML documents. It also explains why
X-Diff focuses on change detection on unordered trees.
The basic edit operations are defined in Section 3.2, and
edit scripts are described in Section 3.3. These scripts
consist of a list of basic editing operations, transforming
one tree to another. Section 3.4 defines a cost model for
edit scripts and the minimum-cost edit script. Section 3.5
introduces the notion of node signature that distinguishes
nodes in an XML context. Node signature is used to
define a new tree-to-tree matching.
3.1. Tree Representation of XML Documents
In order to design an efficient algorithm to detect
changes to XML documents, it is necessary to understand
the hierarchical structure in XML. Based on the
Document Object Model (DOM) specification [W+00], an
XML document can be represented as a tree.
This paper discusses three kinds of nodes in DOM
tree3.
• Element nodes – non-leaf nodes with one label, name.
• Text nodes – leaf nodes with one label, value.
• Attribute nodes – leaf nodes with two labels, name
and value.
According to the DOM specification, element nodes
and text nodes are ordered, while attribute nodes are
unordered. In many applications XML documents can be
treated as unordered trees – only ancestor relationships
are significant, while the left-to-right order among siblings
is not significant. In the document showed by Figure 1.1
and 1.2, the order of two books is reversed, but this is not
significant.
In X-Diff, change detection is focused on unordered
trees. Most ordered tree-to-tree correction approaches
cannot be applied to unordered trees because their
correctness generally depends on preserving the left-toright order when matching nodes.
Two trees are termed isomorphic if they are identical
except for the ordering of siblings. X-Diff considers two
trees are equivalent if they are isomorphic.
3.3. Edit Scripts
An edit script is a sequence of basic edit operations
that convert one tree into another [CRGMG96].
Example 3.1 Consider the following trees T1 and T2
in Figure 3.1 (capital letters denote node name; Greek
letters denote node value), the following edit script
transforms T1 into T2:
E(T1→T2) = Delete(5), Insert(5(B,λ), 3), Update(6,ω).
3.4. A General Cost Model for Edit Scripts
Intuitively, given two trees, there can be many valid
edit scripts capable of transforming one tree to the other.
For instance, consider the following edit script E′ for the
example in Figure 3.1:
E′(T1→T2) = Update(5,λ), Delete(5), Insert(5(B,λ), 3),
Update(6, ω).
Apparently, E′ is not as good as E, so a standard cost
model should be defined to evaluate alternative edit
scripts to determine which one(s) is(are) best. The cost
model will also affect the algorithm design. X-Diff uses a
simple cost model.
3.2. Edit Operations
This section defines three basic edit operations on
DOM Trees.
Definition 3.1
• Insert(x(name, value), y) – insert a node x, with node
name “name” and node value “value”, as a leaf child
3
We ignore other types of nodes for simplicity purpose.
4
1
T1
1’
U
2
3
V
4
A (α)
2’
W
B (β)
3’
W
V
6
5
T2
U
4’
C (γ)
6’
5’
A (α)
B (λ)
C (ω)
Figure 3.1 An example for edit scripts
node within a “Seller” node should not be matched to the
“Name” node of a “Bidder” node.
Here the node signature is defined as the first criterion
for matching two nodes. Given a DOM tree T, let Root(T)
denote the root of T. Given a node x in T, let Type(x)
denote the node type of x, Name(x) denote the node name
of x, and Value(x) denote the node value of x4.
Definition 3.6 Suppose x is a node in a DOM tree T,
Signature(x) = /Name(x1)/…/Name(xn)/Name(x)/Type(x),
where x1 is the root of T, (x1, …, xn, x) is the path from
root to x. If x is a text node, Signature(x) = /Name(x1)/…
/Name(xn)/Type(x).
The signature of a node is obtained by concatenating
the names of all its ancestors with its own name and type5.
X-Diff only matches nodes that have the same signature.
Since all ancestor nodes are non-leaf nodes and non-leaf
nodes must be element nodes, the types of ancestor nodes
in the signature are not included.
Next the notion of a matching is ready to be defined.
Definition 3.7 A set of node pairs (x, y), M, is called a
matching from T1 to T2, iff
1) (x, y) ∈ M, x ∈ T1, y ∈ T2, Signature(x) = Signature(y).
2) ∀ (x1, y1) ∈ M, and (x2, y2) ∈ M, x1 = x2 iff y1 = y2;
(one-to-one)
3) M is prefix closed, i.e., given (x, y) ∈ M, suppose x’ is
the parent of x, y’ is the parent of y, then (x’, y’) ∈ M.
Clearly, M preserves ancestor relationships.
Lemma 3.1
Suppose (x1, y1) ∈ M, (x2, y2) ∈ M, x1 is
an ancestor of x2 iff y1 is an ancestor of y2.
Criterion 3 prevents children being matched if their
ancestors are not matched. This criterion reflects the
integrity of XML segments.
Lemma 3.2
M is a matching from T1 to T2, M = {}
iff (Root(T1), Root(T2)) ∉ M.
Criteria 1 and 3 represent the major differences between
our definition of matching and that in [Zha93]. They
Definition 3.2 Given an edit script E, Cost(E) = n,
where E = O1 O2 … On and Oi is a basic edit operation
defined in Definition 3.1.
This definition can be easily extended by assigning
different costs to different operations, which can also be
applied to X-Diff. The authors believe the cost model
above always accurately reflects real situations.
Based on the definition of the cost of edit scripts, the
minimum-cost edit script, or optimal edit script can be
defined.
Definition 3.3 E is an edit script that transforms tree T1
to T2. E is called a minimum-cost edit script, or an optimal
edit script for (T1→T2) iff ∀ edit script E′ of (T1→T2),
Cost(E′) ≥ Cost(E).
Then the editing distance can also be defined. Let
Dist(T1, T2) denote the editing distance from T1 to T2.
Definition 3.4 Dist(T1, T2) = Cost(E), where E is a
minimum-cost edit script for (T1→T2).
Both minimum-cost edit script and editing distance can
be defined on subtree pairs.
Definition 3.5 E is an edit script that transforms
subtree Tx to Ty. E is called a minimum-cost edit script for
(Tx→Ty) iff ∀ edit script E′ for (Tx→Ty), Cost(E′) ≥
Cost(E); Dist(Tx, Ty) = Cost(E).
3.5.Node Signature and Minimum-Cost Matching
In order to find the difference (generating an edit
script) between two trees, a matching of corresponding
nodes in the two trees should be found. Intuitively, it is
not a good idea to try to match every node in the first tree
to every node in the second tree because each node in
XML has its own context. “Bad” matching will violate the
context and cause unnecessary computation.
For example, a “Title” node won’t match an “Author”
node. Similarly, nodes with different node types are not
matched – Text nodes should not be matched with
Element nodes, or Attribute nodes. Notice it is not enough
to compare node type and node name of two nodes to
decide if they can be matched. For instance, the “Name”
4
A text node does not have a name. An element node does not
have a value.
5
We use “/” as delimiter in the string of signature, similar as in
Xpath [CD+99].
5
reduce the matching space dramatically and make the
algorithm efficient.
Based on a matching M from T1 to T2, an edit script for
(T1→T2) can be generated. Basically, X-Diff delete nodes
in T1 that do not exist in M, insert nodes in T2 that do not
exist in M, and update nodes that are in M but have
different values. The complete algorithm is described in
Section 4.5.
The following theorem shows that a minimum-cost edit
script can be generated from the best matching.
Theorem 3.1 There is a matching M from T1 to T2,
which generates a minimum-cost edit script for (T1→T2).
M is called a minimum-cost matching from T1 to T2,
denoted by Mmin(T1, T2).
Before proving Theorem 3.1, two lemmas about editing
distance should be given.
Lemma 3.3
Suppose both x and y are leaf nodes, x ∈
T1, y ∈ T2; φ denotes null.
1) Dist(x, y) = 0 iff Signature(x) = Signature(y), Value(x)
= Value(y) (identical);
2) Dist(x, y) = 1 iff Signature(x) = Signature(y), Value(x)
≠ Value(y) (update);
3) Dist(x, φ) = Dist(φ, y) = 1 (delete & insert).
Lemma 3.4
Dist(Tx, φ) = Cost(Delete(Tx)); Dist(φ,
Ty) = Cost(Insert(Ty)); Dist(Tx, Ty) = Dist(Tx, φ) + Dist(φ,
Ty) iff Signature(x) ≠ Signature(y).
A brief proof of Theorem 3.1 is given here.
Proof: Mathematical induction is performed on the
height of both trees.
1) height(T1) = height(T2) = 1, i.e., both T1 and T2 are a
single node. Suppose T1 is node x, T2 is node y.
According to Lemma 3.2, the minimum-cost matching
is, Mmin(T1, T2) = {(x, y)} iff Signature(x) =
Signature(y); otherwise Mmin(T1, T2) = {}.
2) Suppose the theorem is true when height(T1) = h1,
height(T2) = h2, h1 ≥ 1, h2 ≥ 1. Consider height(T1) =
h1+1, height(T2) = h2+1.
≠
Signature(Root(T2)).
a) Signature(Root(T1))
According to Lemma 3.2, obviously Mmin(T1, T2) =
{}; Dist(T1, T2) = Cost(Delete(T1), Insert(T2)).
b) Signature(Root(T1)) = Signature(Root(T2)). Suppose
x1, x2, …, xm are second-level nodes in T1, y1, y2, …,
yn are second-level nodes in T2. ∀ xi and yj, there is a
minimum-cost matching Mmin(Txi, Tyj) between Txi
and Tyj, which editing distance is Dist(Txi, Tyj).
Suppose W is a 1-1 (partial) bipartite mapping
between (x1, x2, …, xm) and (y1, y2, …, yn), then
Dist (T1 , T2 ) = min{
Dist (Txi , Ty j )
W
+
∑
xi is unmapped
M min (T1 , T2 ) =
Dist (Txi , φ ) +
∑
M min (Txi , Ty j )
□
The Matching algorithm is described in Section 4.4.
U {( Root (T1 ), Root (T2 ))}
4. Change Detection with X-Diff
The X-Diff algorithm is introduced in this section.
Section 4.1 describes the overall algorithm which consists
of several phases, which are discussed in detail in the
Sections 4.2 through 4.4. Section 4.5 analyzes the
algorithm and estimates its time complexity. Section 4.6
presents a variant of the algorithm with improved
performance but which does not guarantee an optimal
result.
4.1. Outline of the X-Diff Algorithm
Given two XML documents, DOC1 and DOC2, T1 and
T2 are their Tree representations. X-Diff determines if
DOC2 is different from DOC1 based on the unordered
model. If so, X-Diff finds a minimum-cost matching from
T1 to T2, and generates a minimum-cost edit script for
(T1→T2).
There are several steps in X-Diff as shown in Figure
4.1:
1. Parsing and Hashing X-Diff parses DOC1 and DOC2
into XTrees T1 and T2. During the parsing process, XDiff will compute an XHash value for every node,
which is used to represent the entire subtree rooted at
the node.
2. Matching First, X-Diff compares XHash values of
Root(T1) and Root(T2). T1 and T2 are considered
equivalent if two XHash values are equal; otherwise,
X-Diff finds Mmin(T1,T2), a minimum-cost matching
between two trees.
3. Generating Minimum-Cost Edit Script X-Diff
generates a minimum-cost edit script E for (T1→T2),
based on the Mmin(T1, T2) found in Step 2.
Input: (DOC1, DOC2)
/* Parsing and Hashing. */
Parse DOC1 to T1 and hash T1;
Parse DOC2 to T2 and hash T2;
/* Checking and Filtering. */
If ( XHash (Root(T1)) = XHash (Root(T2)) )
DOC1 and DOC2 are equivalent, stop.
else
Do Matchng – Find a minimum-cost matching Mmin(T1, T2)
from T1 to T2.
/* Generating minimum-cost edit script */
Do EditScript – Generate the minimum-cost edit script E from
Mmin(T1, T2).
∑
( xi , y j )∈W
U
( xi , y j )∈Wmin
Dist (φ , Ty j )}
y j is unmapped
i.e., if Wmin is a minimum-cost bipartite mapping
between (x1, x2, …, xm) and (y1, y2, …, yn),
Figure 4.1 Outline of X-Diff Algorithm
6
with extremely high probability6. Since many XML
documents are only slightly modified between versions,
this step will reduce the tree size effectively, avoiding
unnecessary computations in subsequent phases of the
algorithm.
Second, the algorithm computes the editing distance
for each of the remaining subtree pairs and obtains
minimum-cost matchings between subtrees. Finally, it
computes the editing distance between T1 and T2, and
obtains the minimum-cost matching Mmin(T1, T2). On each
level the XHash values of the child nodes are used to filter
out equivalent subtrees in order to reduce the matching
space.
In the Matching algorithm, dynamic programming is
used to compute Dist(T1, T2). It starts computing the
editing distance from leaf node pairs and move upward.
The editing distance between two leaf nodes or two
subtrees, associated with their minimum-cost matching, is
stored in a Distance Table, which is available after
computing the editing distance between subtrees that are
rooted at their parent nodes. When computing the editing
distance between subtrees, the Matching algorithm uses
the minimum-cost maximum flow algorithm [Tar83,
Zha93] to find the minimum-cost bipartite mapping (recall
the proof for Theorem 3.1).
Notice that Theorem 3.1 shows that X-Diff only needs
to compute the editing distance between nodes that have
the same signature. This is critical to this algorithm
because it reduces the mapping space significantly and
helps our algorithm achieve polynomial time in
complexity. Otherwise, X-Diff would have to compute
editing distance between all possible node pairs, which
has been proven to be NP-Complete [ZSS92].
4.2. Parsing and Hashing
This step is the preprocessing step in X-Diff. Two
input XML documents, DOC1 and DOC2, are parsed into
two Xtrees first. An Xtree provides a subset of the
interface provided by a DOM tree, and they are more
efficient than a DOM tree.
During the parsing process, X-Diff uses a special hash
function, XHash, to compute a hash value for every node
on both trees. Similar to DOMHash [MTU98], the XHash
value of a node represents the entire subtree rooted at this
node. The difference is that DOMHash is used fro the
ordered tree model, while XHash is for the unordered tree
model so that two isomorphic trees should have the same
XHash value.
4.3. Matching
The algorithm Matching is used in this step, shown in
Figure 4.2, to find a minimum-cost matching between T1
and T2. Section 3.5 has proved that the minimum-cost
matching can be found by computing the editing distance
between T1 and T2, which is the core of Matching.
To find a minimum-cost matching between T1 and T2,
first the algorithm filters out equivalent subtrees between
two root nodes by comparing the XHash values of secondlevel child nodes. Subtrees with identical XHash values
can be considered to be equivalent because this is true
Input: Tree T1 and T2.
Output: a minimum-cost matching Mmin(T1, T2).
Initialize: set initial working sets
N1 = {all leaf nodes in T1}, N2 = {all leaf nodes in T2}.
Set the Distance Table DT = {}.
/* Step 1: Reduce matching space */
Filter out next-level subtrees that have equal XHash values.
/* Step 2: compute editing distance for (T1 → T2) */
DO {
For every node x in N1
For every node y in N2
If Signature(x) = Signature(y)
Compute Dist(x, y);
Save matching (x, y) with Dist(x, y) in DT.
Set N1 = {parent nodes of previous nodes in N1};
N2 = {parent nodes of previous nodes in N2}.
} While (both N1 and N2 are not empty).
/* Step 3: mark matchings on T1 and T2. */
Set Mmin(T1, T2) = {}
If Signature(Root(T1)) ≠ Signature(Root(T2))
Return;
/* Mmin(T1, T2) = {}*/
Else
Add (Root(T1), Root(T2)) to Mmin(T1, T2).
For every non-leaf node mapping (x, y) ∈ Mmin(T1, T2)
Retrieve matchings between their child nodes that
are stored in DT.
Add child node matchings into Mmin(T1, T2).
Figure 4.2
4.4. Generating Minimum Cost Edit Script
In this phase, X-Diff generates a minimum-cost edit
script based on the minimum-cost matching found in the
previous phase. This generation procedure is performed
recursively from roots to leaves, shown in Figure 4.3.
4.5. Algorithm Analysis
This section briefly analyzes the complexity of our
algorithm. First the complexity of each step in the
algorithm is estimated. |T1| and |T2| denote the number of
nodes in T1 and T2.
1. Parsing and Hashing The time to parse two
documents and construct trees is O(| T1 | + | T2 |) . Hashing
is performed during parsing. Since the child node XHash
values must be sorted before computing parent node
6
A full tree-to-tree comparison may be performed here to
double-check the equivalence between two subtrees. The cost of
this test is linear to the number of nodes in the subtrees.
Matching Algorithm
7
Suppose there are M common non-leaf signatures
between T1 and T2, denoted by S1 to SM. N1k and N2k are
the number of nodes in T1 and T2 whose signature is Sk. xki
and ykj denote nodes whose signature is Sk. The cost of
computing the editing distance for all non-leaf node pairs
is bounded by
Input: Tree T1 and T2, a minimum-cost matching Mmin(T1,
T2), the distance table DT.
Output: an edit script E.
Initialize: set E = Null;
x = Root(T1), y = Root(T2).
If (x, y) ∉ Mmin(T1, T2) /* Subtree deletion and insertion */
Return “Delete(T1), Insert(T2)”.
Else if Dist(T1, T2) = 0
Return “”;
Else {
For every node pair (xi , yj) ∈ Mmin(T1, T2), xi is a child
node of x, yj is a child node of y.
If xi and yj are leaf nodes
If Dist(xi, yj) = 0
Return “”;
Else
/* Update leaf node */
Add Update(xi , Value(yj)) to E;
Else
/* Call subtree matching */
Add EditScript(Txi, Tyj) to E;
Return E;
For every node xi not in Mmin(T1, T2)
Add “Delete(Txi)” to E;
For every node yj not in Mmin(T1, T2)
Add “Insert(Tyj )” to E;
Return E. }
M N1k N 2 k
∑∑∑{O(deg( x
ki ) × deg( ykj ) × max{deg( xki ), deg( ykj )}
k =1 i =1 j =1
(3)
Let deg(T1) and deg(T2) denote the maximum outdegree in T1 and T2, then
M
(3) ≤
N1 k N 2 k
∑∑∑ {O(deg( x
ki ) × deg( y kj ) × max{deg(T1 ), deg(T2 )}
k =1 i =1 j =1
M
Since
× log 2 (max{deg(T1 ), deg(T2 )}))
N1 k
∑∑ deg( x
ki )
k =1 i =1
M
< | T1 | and
(4)
N2k
∑∑ deg( y
kj )
< | T2 | ,
k =1 j =1
(4) ≤ O(| T1 | × | T2 | × max{deg(T1 ), deg(T2 )} ×
log 2 (max{deg(T1 ), deg(T2 )}))
(5)
Combining (1) and (5), the complexity of this step is
bounded by:
O(| T1 | × | T2 | × max{deg(T1 ), deg(T2 )} ×
Figure 4.3 EditScript Algorithm
XHash values, the upper bound for the complexity of this
step is O(| T1 | × log(| T1 |) + | T2 | × log(| T2 |)) .
2. Mapping
As described in Section 4.3, in this step,
the editing distance between every node pair (x, y) (where
x ∈ T1, y ∈ T2, Signature(x) = Signature(y)) is computed,
from leaf nodes to roots. Here the complexity of this step
in the worst case is analyzed, in which X-Diff cannot filter
out any equivalent subtrees by comparing their XHash
values although this is very unlikely to happen. The
minimum-cost matching from T1 to T2 is obtained when
the editing distance between the two root nodes is found.
The complexity of this step can be estimated by dividing it
into two parts, leaf nodes matching and non-leaf nodes
matching.
First consider leaf nodes matching. According to
Lemma 4.3, the cost of computing the editing distance
between two leaf nodes is O(1). So the cost of computing
the editing distance for all leaf node pairs is bounded by
O(| T1 | × | T2 |)
(1)
Second, consider non-leaf nodes matching. According
to Lemma 4.2, the editing distance of each non-leaf node
pair (x, y) (where x ∈ T1, y ∈ T2, Signature(x) =
Signature(y)) is obtained by finding a minimum-cost
matching between their child nodes. Let deg(x) denote the
out-degree of node x, i.e., the number of its child nodes.
The cost of computing editing distance between x and y is
bounded by
Ο( deg( x) × deg( y ) × max{deg( x), deg( y )}
× log 2 (max{deg( x ), deg( y )}))
× log 2 (max{deg( xki ), deg( ykj )}))}
log 2 (max{deg(T1 ), deg(T2 )}))
(6)
3. Generating Minimum-Cost Edit Scrip The minimumcost edit script is generated recursively by traversing all
nodes once in T1 and T2. The time complexity
is O(| T1 | + | T2 |) .
The running time in step 3 is the most significant of all
steps, so the complexity of our algorithm is the complexity
of step3, shown by (6).
4.6. Performance Improvement
The primary focus of the X-Diff algorithm is to
compute and generate the best possible difference
between two XML documents. The previous section has
demonstrated that X-Diff has a polynomial running time.
In some cases, however, this may not satisfy users’ needs.
Assume, for example, that the document shown in Figure
1.1 contains 10,000 books and that each hour 1,000
elements are changed. In order to compute the
optimal difference between the two versions of the
document, X-Diff must compute the minimum editing
distance between every updated element in the
old and new versions, which means that it needs to
compute the editing distance for 1 million pairs of nodes.
While X-Diff guarantees to generate the best difference
result, some users may be willing to sacrifice some degree
of accuracy in exchange for improved response time. This
section discusses an approach for improving X-Diff’s
response time.
[Zha93] (2)
8
X-Diff is implemented in C++8, using Xerces C++
XML parser v1.4.0, the same parser used by the XyDiff9
algorithms. Both programs read in two versions of an
XML document and generate the difference. All following
experiments were performed on a Pentium® III 550 MHz
PC with 256 MB memory. The operating System is
RedHat® Linux 6.2.
The Actors data set10 is used, whose DTD is shown in
Figure 5.1. The size of the documents used in our
experiments ranges from 10 KB to 1MB. A program
generates all three types of changes, “insert”, “delete”,
and “update”, randomly at each level. The program takes
a parameter, the percentage of nodes being changed. All
changes are equally distributed in half of the
elements.
The motivation is to speed up X-Diff without reducing
the result quality significantly. The authors believe that
generally when people attempt to compute the difference
between two versions of a document, the two documents
will not be significantly different. In the example above,
except for recently inserted or deleted books, most
elements are likely to have been only slightly
changed, such as the bidder’s name, or the bidding price.
That suggests that for every updated element in
one document, it is very likely to find one and only one
“good” match for the element in the other document.
Thus, the editing distance between this element (subtree)
and its “good” match is very likely to be significantly less
than the editing distance between it and all the other
elements. As a result, when computing the editing distance
for an element, as soon as one such match is found, both
nodes can be immediately matched and there is no need to
consider any other matchings for these two nodes.
A natural idea is to use a threshold value to decide
whether or not two nodes are a “good” match. Obviously,
a good threshold should not be a static value across
documents or even different levels within a document. If
the threshold is too high, it tends to mismatch elements.
On the other hand, if the threshold is too low, it cannot
locate good matches and avoid a full evaluation. Our
solution is to use sampling to calculate this threshold
whenever there are more than a couple of updated nodes
in the two documents. At each level when computing the
editing distance for node pairs, first a small number7 of
nodes are randomly selected from the first document.
Second, for each node in this sample the algorithm
computes the editing distance between this node and every
candidate in the other document and finds the smallest
value, which represents the best match for this node. Then
the threshold value is calculated as the average of the
editing distances obtained by sampling.
Section 5 demonstrates that the improved X-Diff
algorithm runs much faster than the optimal X-Diff
algorithm while still generating the optimal results in most
cases.
Figure 5.1 DTD of Actors data set
Notice that XyDiff uses the ordered tree model. In
order to provide a fair comparison, our change generator
does not permute the order of any nodes; otherwise, it
would bias the results in favor of the X-Diff algorithm.
5.2. Execution Time
First, we evaluate the execution time of the three
algorithms, X-Diff, the improved X-Diff (represented by
X-Diff+) and XyDiff on documents of different sizes. In
Figure 5.1, 1% of the nodes are modified. In Figure 5.2,
5% of then nodes are changed.
Both figures show that X-Diff performs well on smalland medium-size documents. However, due to the
complexity of the algorithm, its execution time is fairly
long when the two input files are large. On the other hand,
XyDiff is very efficient in that its running time is almost
linear in the size of the document. Notice, however, while
the improved X-Diff algorithm is still slower than XyDiff,
it is much faster than the original X-Diff algorithm as
using a threshold value obtained by sampling avoids
unnecessary comparisons. Notice also that the absolute
execution time of the two X-Diff algorithms does not
increase significantly when the percentage of changed
5. Performance Evaluation
This section examines the performance of both the
optimal X-Diff algorithm and the improved X-Diff
algorithm. Both algorithms are compared to XyDiff by
showing some preliminary results on their running time
and result quality.
5.1. Experimental Settings and Testing Dataset
8
7
According to the large number / central limit theory,
“safe” number if there are n nodes [Fel71].
Both C++ and Java version of X-Diff are available at
http://www.cs.wisc.edu/~yuanwang/xdiff.html.
9
http://www-rocq.inria.fr/~cobena/XyDiffWeb/.
10
http://www.cs.wisc.edu/niagara/data.html.
n is a
9
3
1000.000
Execution Time (s)
100.000
10.000
1.000
0.100
0.010
10
XyDiff
Ratios of the diff result vs. the
optimal resul
X-Dif f
X-Dif f +
XyDiff
100
X-Diff+
2
1
0
0
1000
10
Size of input documents (KB)
Figure 5.2 Execution time on 1% change
Figure 5.4 Quality of diff result (1)
6
1,000.0
XyDiff
Ratios of the diff result
vs. the optimal resul
X-Diff
X-Diff+
XyDiff
100.0
Execution Time (s)
20
Change ratio (%)
10.0
1.0
0.1
0.0
10
100
5
X-Diff+
4
3
2
1
0
0
1,000
10
Size of input documents (KB)
Figure 5.5 Quality of diff result (2)
Figure 5.3 Execution time on 5% change
nodes increases from 1% to 5% (Figure 5.3 vs. Figure
5.2).
This is consistent with our complexity analysis which
demonstrated that the execution time of the algorithm
depends primarily on the total number of nodes and not
the number of changed nodes.
Mike
Johnson
movie1
movie2
movie3
Mike
Goodman
movie1
movie2
movie3
Document #1
20
Change ratio (%)
5.2. Result Quality
In the next set of tests the result quality of each
algorithm is compared. Since the original X-Diff
algorithm was shown to always find the optimal difference
in Section 3 (and it does!), Only the improved X-Diff
algorithm and XyDiff algorithm are compared.
Mike
Johnson
movie4
movie2
movie3
Bill
Goodman
movie1
movie2
movie3
Document #2
Figure 5.6 Two sample documents
10
1
Tree T1
Actors
2
15
Actor
Actor
3
8
Name
4
FirstName
LastName
5
Title
7
Mike
Johnson
13
Title
21
Name
11
9
6
16
Movies
17
FirstName
Title
10
12
14
movie1
movie2
movie3
LastName
18
Title
20
Goodman
Mike
26
24
22
19
Movies
Title
Title
23
25
27
movie1
movie2
movie3
1
Tree T2
Actors
2
15
Actor
Actor
3
8
Name
4
9
6
FirstName
5
LastName
7
Mike
Johnson
Title
16
13
11
Title
21
Name
Movies
Title
10
12
14
movie4
movie2
movie3
17
22
19
FirstName
18
LastName
20
Bill
Goodman
Title
Movies
26
24
Title
Title
23
25
27
movie1
movie2
movie3
Figure 5.7 Tree representation for both documents in Figure5.6
First one hundred 50KB documents are constructed in
E′(T1→T2) = Move(16, 2, 1)11, Move(3, 15, 1),
which elements are randomly selected from the base data
Update(18, Bill), Update(10, movie4), Move(2, 1, 2).
set used in the previous experiments. Then a series of new
This is because XyDiff matches the element
versions for each document was generated by varying the
of Mike Johnson to the Bill Goodman’s when it finds both
change ratio. X-Diff+ and XyDiff were run to compare the
subtrees are identical, although it is not a good match
original version of the document with each of the new
from the higher-level’s point of view. In this type of
versions to obtain a series of differences for each
situation, no matter if the match is propagated to the upper
algorithm. The results of each diff operation were then
level or not, it will generate a much longer difference than
compared to the results obtained using the original X-Diff
the optimal result.
algorithm and the ratio plotted in Figure 5.4. The
In fact, the above example illustrates that when there
improved X-Diff algorithm almost always finds out the
are many small identical elements in both documents,
optimal difference until the change ratio reaches 18%
XyDiff is likely to generate a significantly larger diff
where its result is very close to the optimal difference. On
result than the optimal result. On the other hand, although
the other hand, the result generated by XyDiff is generally
X-Diff+ also uses a heuristic matching method, threshold
about 50% worse than the optimal result.
matching, its top-down fashion avoids aggressive
One of the reasons that XyDiff generates non-optimal
matching on small elements. Notice that the example is
results is that it has a tendency to mismatch nodes when
not that unusual. Considering the motivating example
guided by its greedy matching rules. For example, two
shown in Figures 1.1 and 1.2, different books may have
simple documents are illustrated in Figure 5.6, and the
the same author, or the same publisher, or even the same
tree representation of both documents is shown in Figure
price, etc.
5.7. The difference between the two documents is
The next experiment is to demonstrate this difference
displayed in bold font. The editing list computed by both
between X-Diff/X-Diff+ and XyDiff. Similar to the
X-Diff and X-Diff+ is,
11
E(T1→T2) = Update(10, movie4), Update(18, Bill).
This operation means “move the subtree rooted at node 16 to
However, the diff result generated by XyDiff is,
be a child of node 2 at position 1”.
11
[CD+99] J. Clark, S. DeRose, et al., “XML Path Language
(Xpath)
Version
1.0”,
November
1999,
http://www.w3.org/TR/1999/REC-xpath-19991116.
[CE99] Curbera, D. A. Epstein, “Fast Difference and Update of
XML Documents”, XTech’99, San Jose, March 1999.
[CGM97] S. Chawathe, H. Garcia-Molina, “Meaningful
Change Detection in Structured Data”, Proceedings of the ACM
SIGMOD International Conference on Management of Data,
June 1996.
[CRGMW96] S. Chawathe, A. Rajaraman, H. Garcia-Molina
and J. Widom, “Change Detection in Hierarchically Structured
Information”, Proceedings of the ACM SIGMOD International
Conference on Management of Data, Montreal, June 1996.
[CVS] “Concurrent Versions System (CVS)”, Free Software
Foundation, http://www.gnu.org/manual/cvs-1.9.
[DB96] F. Douglis, T. Ball, “Tracking and Viewing Changes on
the Web”, 1996 USENIX Annual Technical Conference, 1996.
[DBCK98] F. Douglis, T. Ball, Y. F. Chen, E. Koutsofios, “The
AT&T Internet Difference Engine: Tracking and Viewing
Changes on the Web”, World Wide Web, 1(1): 27-44, January
1998.
[Fel71] W. Feller, “An Introduction to Probability Theory and
Its Applications”, 2nd ed., John Wiley & Sons, 1971.
[Hirs77] D. S. Hirschberg, “Algorithm for the Longest Common
Subsequence Problem”, Journal of the ACM, 24(4): 664-675,
October 1977.
[HD82] C. M. Hoffmann, M. J. O’Donnell, “Pattern Matching
in Trees”, Journal of the ACM, 29: 68-95, 1982.
[MTU98] H. Maruyama, K. Tamura and R. Uramoto, “Digest
values for DOM (DOMHash) proposal”, IBM Tokyo Research
Laboratory,
http://www.trl.ibm.co.jp/projects/xml/domhash.htm, 1998.
[Myers86] E. W. Myers, “An O(ND) Difference Algorithm and
Its Variations”, Algorithmica, 1(2): 251-266, 1986.
[Selk77] S. M. Selkow, “The Tree-to-Tree Editing Problem”,
Information Processing Letters, 6(6): 184-186, 1977.
[Tai79] K. C. Tai, “The Tree-to-Tree Correction Problem”,
Journal of the ACM, 26: 485-495, 1979.
[Tar83] R.E. Tarjan, “Data Structures and Network
Algorithms”, CBMS-NSF Regional Conference Series in
Applied Mathematics, 1983.
[TIHW01] I. Tatarinov, Z. Ives, A. Halevy, D. Weld, “Updating
XML”, SIGMOD Conference, 2001.
[W+00] L. Wood, et. al., “Document Object Model (DOM)
Level 1 Specification (Second Edition)”, World Wide Web
Consortium, http://www.w3.org/TR/2000/WD-DOM-Level-120000929/, 2000.
[W3C] “Extensible Markup Language (XML)”, World Wide
Web Consortium, http://www.w3.org/XML/.
[Zha93] K. Zhang, “A New Editing based Distance between
Unordered Labeled Trees”, Combinatorial Pattern Matching, 1:
254 – 265, 1993.
[ZS89] K. Zhang and D. Shasha, “Simple Fast Algorithms for
the Editing Distance between Trees and Related Problems”,
SIAM Journal of Computing, 18(6): 1245-1262, 1989.
[ZSS92] K. Zhang, R. Statman, D. Shasha, “On the Editing
Distance between Unordered Labeled Trees”, Information
Processing Letters, 42: 133-139, 1992.
previous test, one hundred 50KB documents are randomly
constructed, but this time there are at average of five
duplicate elements for every different element
across each document. A series of new versions for each
document are also randomly generated and fed to both XDiff+ and XyDiff. Figure 5.5 shows the ratios of the diff
results of both algorithms compared to the optimal result.
X-Diff+ generates significantly shorter diff results than
XyDiff.
6. Conclusions
X-Diff is motivated by the problem of efficiently
detecting changes to XML documents on the web.
Previous work in change detection on XML or other
hierarchically structured data [CRGMW96, CE99] used
the ordered-tree model. In this paper, we argue that using
the unordered-tree model is more suitable for most
database and web applications, although it is substantially
harder than using the ordered-tree model. The paper
studies the XML domain characteristics and introduces
several key notions, such as node signature, and XHash.
Using these techniques in combination with standard treeto-tree correction techniques [Zha93], this paper proposes
X-Diff, an efficient algorithm for computing the optimal
difference between two versions of an XML document.
We present and analyze the algorithm, and also propose
an improved X-Diff algorithm that runs much faster than
the original algorithm while still generating at least nearoptimal results. A preliminary performance evaluation of
our algorithms is presented, compared with XyDiff
[CAM02]. The experiments show that the improved XDiff algorithm generally generates more accurate results
than XyDiff does, although it runs slower than XyDiff. It
is suitable for the situations that users want to get more
accurate results.
7. Acknowledgement
We would thank the anonymous reviewers for their
valuable comments. We also appreciate all X-Diff users
for comments and bug reports.
Yuan Wang and David J. DeWitt are supported by the
NSF under grant number ITR 0086002. Jin-Yi Cai is
supported by NSF CCR-9820806 and Guggenheim
Fellowship.
8. References
[Berk] E. Berk, “HtmlDiff: A Differencing Tool for HTML
Student
Project,
Princeton
University,
Documents”,
http://www.htmldiff.com.
[CAM02] G. Cobéna, S. Abiteboul, A. Marian, “Detecting
Changes in XML Documents”, The 18th International
Conference on Data Engineering, San Jose, February, 2002.
12