ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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

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

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, 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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HHS+]
...
[Law76]
...
[LGM96]
Wilburt Labio, Hector Garcia-Molina: Efficient Snapshot Differential Algorithms for Data Warehousing. VLDB 1996: 63-74 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Mye86]
Eugene W. Myers: An O(ND) Difference Algorithm and Its Variations. Algorithmica 1(2): 251-266(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PS82]
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall 1982, ISBN 0-13-152462-3
CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rot]
...
[SWZS94]
...
[SZ90]
Dennis Shasha, Kaizhong Zhang: Fast Algorithms for the Unit Cost Editing Distance Between Trees. J. Algorithms 11(4): 581-621(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Wag75]
Robert A. Wagner: On the Complexity of the Extended String-to-String Correction Problem. STOC 1975: 218-223 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WF74]
Robert A. Wagner, Michael J. Fischer: The String-to-String Correction Problem. J. ACM 21(1): 168-173(1974) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WMG90]
Sun Wu, Udi Manber, Gene Myers, Webb Miller: An O(NP) Sequence Comparison Algorithm. Inf. Process. Lett. 35(6): 317-323(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[ZWS95]
...

Copyright © Mon Mar 15 03:54:34 2010 by Michael Ley (ley@uni-trier.de)