Change Detection in Hierarchically Structured Information.

Sudarshan S. Chawathe, Anand Rajaraman, Hector Garcia-Molina, Jennifer Widom: Change Detection in Hierarchically Structured Information. SIGMOD Conference 1996: 493-504

@inproceedings{DBLP:conf/sigmod/ChawatheRGW96,
  author    = {Sudarshan S. Chawathe and
               Anand Rajaraman and
               Hector Garcia-Molina and
               Jennifer Widom},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Change Detection in Hierarchically Structured Information},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {493-504},
  ee        = {http://doi.acm.org/10.1145/233269.233366, db/conf/sigmod/ChawatheRGW96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

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.

Copyright © 1996 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

BibTeX

Printed Edition

H. V. Jagadish, Inderpal Singh Mumick (Eds.): Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada, June 4-6, 1996. ACM Press 1996 BibTeX , SIGMOD Record 25(2), June 1996
Contents

Online Edition: ACM Digital Library

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

References

[ACM95]: Serge Abiteboul, Sophie Cluet, Tova Milo: A Database Interface for File Updates. SIGMOD Conference 1995: 386-397 BibTeX
[CRGMW95]: ...
[GHJ+93]: Shahram Ghandeharizadeh, Richard Hull, Dean Jacobs, Jaime Castillo, Martha Escobar-Molano, Shih-Hui Lu, Junhui Luo, Chiu Tsang, Gang Zhou: On Implementing a Language for Specifying Active Database Execution Models. VLDB 1993: 441-454 BibTeX
[GM95]: Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) BibTeX
[HGMW+95]: Joachim Hammer, Hector Garcia-Molina, Jennifer Widom, Wilburt Labio, Yue Zhuge: The Stanford Data Warehousing Project. IEEE Data Eng. Bull. 18(2): 41-48(1995) BibTeX
[HKG+94]: ...
[IK93]: W. H. Inmon, Ch. Kelley: Rdb/VMS: Developing the Data Warehouse. QED Publishing Group/John Wiley 1993, ISBN 0-471-56920-8
BibTeX
[Kif95]: ...
[LGM95]: ...
[Mye86]: Eugene W. Myers: An O(ND) Difference Algorithm and Its Variations. Algorithmica 1(2): 251-266(1986) BibTeX
[PGMW95]: Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260 BibTeX
[SZ90]: Dennis Shasha, Kaizhong Zhang: Fast Algorithms for the Unit Cost Editing Distance Between Trees. J. Algorithms 11(4): 581-621(1990) BibTeX
[WC96]: Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
Contents BibTeX
[ZGMHW95]: Yue Zhuge, Hector Garcia-Molina, Joachim Hammer, Jennifer Widom: View Maintenance in a Warehousing Environment. SIGMOD Conference 1995: 316-327 BibTeX
[Zha95]: ...
[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) BibTeX

Referenced by

Daniel Barbará, Rajni Goel, Sushil Jajodia: Using Checksums to Detect Data Corruption. EDBT 2000: 136-149
Sudarshan S. Chawathe: Comparing Hierarchical Data in External Memory. VLDB 1999: 90-101
Sudarshan S. Chawathe, Serge Abiteboul, Jennifer Widom: Representing and Querying Changes in Semistructured Data. ICDE 1998: 4-13
Jason Tsong-Li Wang, Dennis Shasha, George Jyh-Shian Chang, Liam Relihan, Kaizhong Zhang, Girish Patel: Structural Matching and Discovery in Document Databases. SIGMOD Conference 1997: 560-563
Sudarshan S. Chawathe, Hector Garcia-Molina: Meaningful Change Detection in Structured Data. SIGMOD Conference 1997: 26-37
Wilburt Labio, Hector Garcia-Molina: Efficient Snapshot Differential Algorithms for Data Warehousing. VLDB 1996: 63-74
Jennifer Widom: Research Problems in Data Warehousing. CIKM 1995: 25-30

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]