Meaningful Change Detection in Structured Data.

Sudarshan S. Chawathe, Hector Garcia-Molina: Meaningful Change Detection in Structured Data. SIGMOD Conference 1997: 26-37

@inproceedings{DBLP:conf/sigmod/ChawatheG97,
  author    = {Sudarshan S. Chawathe and
               Hector Garcia-Molina},
  editor    = {Joan Peckham},
  title     = {Meaningful Change Detection in Structured Data},
  booktitle = {SIGMOD 1997, Proceedings ACM SIGMOD International Conference
               on Management of Data, May 13-15, 1997, Tucson, Arizona, USA},
  publisher = {ACM Press},
  year      = {1997},
  pages     = {26-37},
  ee        = {http://doi.acm.org/10.1145/253260.253266, db/conf/sigmod/ChawatheG97.html},
  crossref  = {DBLP:conf/sigmod/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Detecting changes by comparing data snapshots is an important requirement for difference queries, active databases, and version and configuration management. In this paper we focus on detecting meaningful changes in hierarchically structured data, such as nested-object data. This problem is much more challenging than the corresponding one for relational or flat-file data. In order to describe changes better, we base our work not just on the traditional "atomic" insert, delete, update operations, but also on operations that move an entire sub-tree of nodes, and that copy an entire sub-tree. These operations allows us to describe changes in a semantically more meaningful way. Since this change detection problem is NP-hard, in this paper we present a heuristic change detection algorithm that yields close to "minimal" descriptions of the changes, and that has fewer restrictions than previous algorithms. Our algorithm is based on transforming the change detection problem to a problem of computing a minimum-cost edge cover of a bipartite graph. We study the quality of the solution produced by our algorithm, as well as the running time, both analytically and experimentally.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Joan Peckham (Ed.): SIGMOD 1997, Proceedings ACM SIGMOD International Conference on Management of Data, May 13-15, 1997, Tucson, Arizona, USA. ACM Press 1997

, SIGMOD Record 26(2), June 1997
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1635 KB]

References

[CGM97]: ...
[CHMH+94]: ...
[CRGMW96]: Sudarshan S. Chawathe, Anand Rajaraman, Hector Garcia-Molina, Jennifer Widom: Change Detection in Hierarchically Structured Information. SIGMOD Conference 1996: 493-504
[HHS+]: ...
[Law76]: ...
[LGM96]: Wilburt Labio, Hector Garcia-Molina: Efficient Snapshot Differential Algorithms for Data Warehousing. VLDB 1996: 63-74
[Mye86]: Eugene W. Myers: An O(ND) Difference Algorithm and Its Variations. Algorithmica 1(2): 251-266(1986)
[PS82]: Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
[Rot]: ...
[SWZS94]: ...
[SZ90]: Dennis Shasha, Kaizhong Zhang: Fast Algorithms for the Unit Cost Editing Distance Between Trees. J. Algorithms 11(4): 581-621(1990)
[Wag75]: Robert A. Wagner: On the Complexity of the Extended String-to-String Correction Problem. STOC 1975: 218-223
[WF74]: Robert A. Wagner, Michael J. Fischer: The String-to-String Correction Problem. J. ACM 21(1): 168-173(1974)
[WMG90]: Sun Wu, Udi Manber, Gene Myers, Webb Miller: An O(NP) Sequence Comparison Algorithm. Inf. Process. Lett. 35(6): 317-323(1990)
[WU95]: ...
[ZS89]: Kaizhong Zhang, Dennis Shasha: Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. SIAM J. Comput. 18(6): 1245-1262(1989)
[ZWS95]: ...