Next: Introduction
Change Detection in Hierarchically Structured Information
Sudarshan S. Chawathe,
Anand Rajaraman,
Hector Garcia-Molina,
and Jennifer Widom
Department of Computer Science
Stanford University
Stanford, California 94305
{chaw,anand,hector,widom}@cs.stanford.edu
Abstract:
Detecting and representing changes to data is important for active
databases, data warehousing, view maintenance, and version and
configuration management. Most previous work in change management has
dealt with flat-file and relational data; we focus on hierarchically
structured data. Since in many cases changes must be computed from
old and new versions of the data, we define the hierarchical change
detection problem as the problem of finding a ``minimum-cost edit
script'' that transforms one data tree to another, and we present
efficient algorithms for computing such an edit script. Our
algorithms make use of some key domain characteristics to achieve
substantially better performance than previous, general-purpose
algorithms. We study the performance of our algorithms both
analytically and empirically, and we describe the application of our
techniques to hierarchically structured documents.
Sudarshan S. Chawathe
Wed Jun 19 08:22:34 PDT 1996