Schema Evolution publication categorizer

This paper generalizes the work on the edit distance between
strings [6, 11, 13, 16, 20, 21, 25] and trees [19, 28, 29]. Various
kinds of constrained and
generalized edit distance on strings and trees have been developed
[1, 9, 10, 17, 27]. Our degree-2
distance, when applied to unordered trees, is a restricted form of
the constrained distance previously
reported in [27]. When applied to ordered trees, the degree-2
distance is a generalized
measure of the constrained distance originated from Selkow [17],
though our algorithm has the
same asymptotic complexity as Selkow's algorithm. (Selkow's distance
measure requires that all
node deletions and insertions occur at leaves i.e., with degree 1.)
In this extended abstract, we
present algorithms for computing the degree-2 distance between two
CUAL graphs and unordered
trees. (The result for the latter is used as a subroutine to
calculate the former.) The entire set of
algorithms is in the full paper and is available from the authors. We
have chosen to present these
two results, because we believe they are the most useful of our
results to date for approximate
graph matching.