Stanford InfoLab Publication Server

Change Detection in Hierarchically Structured Information

Chawathe, S. and Rajaraman, A. and Garcia-Molina, H. and Widom, J. (1995) Change Detection in Hierarchically Structured Information. In: ACM International Conference on Management of Data, Montreal (SIGMOD 1996), June 4-6, 1996, Quebec, Canada.




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 effcient 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.

Item Type:Conference or Workshop Item (Paper)
Uncontrolled Keywords:change detection, semi-structured data, edit script, difference
Subjects:Computer Science > Semistructured Data
Related URLs:Project Homepage
ID Code:114
Deposited By:Import Account
Deposited On:25 Feb 2000 16:00
Last Modified:14 Jan 2009 14:25

Download statistics

Repository Staff Only: item control page