Article

Free access

Change detection in hierarchically structured information

Authors:

Sudarshan S. Chawathe,

Anand Rajaraman,

Hector Garcia-Molina,

Jennifer WidomAuthors Info & Claims

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

Pages 493 - 504

https://doi.org/10.1145/233269.233366

Published: 01 June 1996 Publication History

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.

References

[1]

S. Abiteboul, S. Cluet, and T. Milo. A database interface for file updates. In Proceedings of the A CM SIGMOD International Conference on Management of Data, 1995.

Digital Library

[2]

S. Chawathe, A. Rajaraman, H. Garcia- Molina, and J. Widom. Change detection in hierarchlcally structured information. Available by anonymous ftp from db.stanford.edu in directory pub/chawathe/199S/, 1995.

[3]

S. Ghandeharizadeh, R. Hull, D. Jacobs, et al. On implementing a language for specifying active database execution models. In Proceedings of the Nineteenth International Conference on Very Large Data Bases, Dublin, Ireland, August 1993.

Digital Library

[4]

A. Gupta and I.S. Mumick. Maintenance of materialized views: Problems, techniques, and appfications. IEEE Data Engineering Bulletin, Special Issue on Materialized Views and Data Warehousing, 18(2):3-18, June 1995.

[5]

J. Hammer, H. Garcia-Molina, J. Widom, W. Labio, and Y. Zhuge. The Stanford Data Warehousing Project. IEEE Data Engineering Bulletin, Special Issue on Materialized Views and Data Warehousing, 18(2):41-48, June 1995.

[6]

H.C. Howard, A.M. Keller, A. Gupta, K. Krishnamurthy, K.H. Law, P.M. Teicholz, S. Tiwari, and J. Ullman. Versions, configurations, and constraints in CEDB. CIFE Working Paper 31, Center for Integrated Facilities Engineering, Stanford University, April 1994.

[7]

W.H. Inmon and C. Kelley. Rdb/VMS: Developing the Data Warehouse. QED Publishing Group, Boston, Massachussetts, 1993.

Digital Library

[8]

M. Kifer. EDIFF-a comprehensive interface to diff for Emacs 19. Available through anonymous ftp at ftp. ca. sunysb, edu, 1995.

[9]

W. Labio and H. Garcia-Molina. Efficient algorithms to compare snapshots. Manuscript, available by anonymous ftp from db.stanford.edu in pub/labio/199S/, 1995.

[10]

E. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1(2):251-266, 1986.

[11]

Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. Object exchange across heterogeneous information sources. In Proceedings of the Eleventh International Conference on Data Engineering, pages 251-260, Taipei, Taiwan, March 1995.

Digital Library

[12]

D. Shasha and K. Zhang. Fast algorithms for the unit cost editing distance between trees. Journal of Algorithms, 11:581-621, 1990.

Digital Library

[13]

J. Widom and S. Ceri. Active Database Systems: Triggers and Rules for Advanced Database Processing. Morgan Kaufmann, San Francisco, California, 1996.

Digital Library

[14]

Y. Zhuge, H. Garcia-Molina, 3. Hammer, and J. Widom. View maintenance in a warehousing environment. In Proceedings of the A CM SIGMOD International Conference on Management of Data, pages 316- 327, San Jose, California, May 1995.

Digital Library

[15]

K. Zhang. Personal communication, May 1995.

[16]

K. Zhang and D. Shasha. Simple fast algorithms for the editing distance between trees and related problems. SIAM Journal of Computing, 18(6):1245-1262, 1989.

Digital Library

Cited By

Tekli JTekli GChbeir R(2023)Combining offline and on-the-fly disambiguation to perform semantic-aware XML queryingComputer Science and Information Systems10.2298/CSIS220228063T20:1(423-457)Online publication date: 2023
https://doi.org/10.2298/CSIS220228063T
Pečimúth ALeopoldseder DTůma PBruno RMoss E(2023)Diagnosing Compiler Performance by Comparing Optimization DecisionsProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622994(47-61)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622994
Martinez MFalleri JMonperrus M(2023)Hyperparameter Optimization for AST DifferencingIEEE Transactions on Software Engineering10.1109/TSE.2023.331593549:10(4814-4828)Online publication date: 1-Oct-2023
https://doi.org/10.1109/TSE.2023.3315935
Show More Cited By

Index Terms

Change detection in hierarchically structured information
1. Information systems
  1. Data management systems
    1. Database design and models

Recommendations

Change detection in hierarchically structured information

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 Distributed Data Warehouse
HPC '00: Proceedings of the The Fourth International Conference on High-Performance Computing in the Asia-Pacific Region-Volume 2 - Volume 2

Data Warehouse (DW) is a rapidly developing field of both application and research. Up to now, three types of data warehouse have been proposed, which include centralized DW, data mart, and distributed DW. In this paper, a new type of data warehouse, ...
Modeling subpopulations for hierarchically structured data
Abstract
The field of forensic statistics offers a unique hierarchical data structure in which a population is composed of several subpopulations of sources and a sample is collected from each source. This subpopulation structure creates an additional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '96: Proceedings of the 1996 ACM SIGMOD international conference on Management of data

June 1996

560 pages

ISBN:0897917944

DOI:10.1145/233269

Editor:
Jennifer Widom
Stanford Univ., Stanford, CT

ACM SIGMOD Record Volume 25, Issue 2
June 1996
557 pages
ISSN:0163-5808
DOI:10.1145/235968
Chairman:
T. H. Merrett
McGill Univ.
,
Editors:
H. V. Jagadish,
Inderpal Singh Mumick
Issue’s Table of Contents

Copyright © 1996 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS96

Sponsor:

SIGMOD/PODS96: Joint ACM SIGMOD International Conference on Management of Data and ACM Symposium on Principles of Database Systems

June 4 - 6, 1996

Quebec, Montreal, Canada

Acceptance Rates

SIGMOD '96 Paper Acceptance Rate 47 of 290 submissions, 16%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

338
Total Citations
View Citations
2,791
Total Downloads

Downloads (Last 12 months)419
Downloads (Last 6 weeks)53

Reflects downloads up to 30 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tekli JTekli GChbeir R(2023)Combining offline and on-the-fly disambiguation to perform semantic-aware XML queryingComputer Science and Information Systems10.2298/CSIS220228063T20:1(423-457)Online publication date: 2023
https://doi.org/10.2298/CSIS220228063T
Pečimúth ALeopoldseder DTůma PBruno RMoss E(2023)Diagnosing Compiler Performance by Comparing Optimization DecisionsProceedings of the 20th ACM SIGPLAN International Conference on Managed Programming Languages and Runtimes10.1145/3617651.3622994(47-61)Online publication date: 19-Oct-2023
https://dl.acm.org/doi/10.1145/3617651.3622994
Martinez MFalleri JMonperrus M(2023)Hyperparameter Optimization for AST DifferencingIEEE Transactions on Software Engineering10.1109/TSE.2023.331593549:10(4814-4828)Online publication date: 1-Oct-2023
https://doi.org/10.1109/TSE.2023.3315935
Larsen SFalleri JBaudry BMonperrus M(2023)Spork: Structured Merge for Java With Formatting PreservationIEEE Transactions on Software Engineering10.1109/TSE.2022.314376649:1(64-83)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TSE.2022.3143766
Mori AHashimoto M(2023)Phylogenetic Analysis of Reticulate Software Evolution2023 IEEE/ACM 20th International Conference on Mining Software Repositories (MSR)10.1109/MSR59073.2023.00074(498-510)Online publication date: May-2023
https://doi.org/10.1109/MSR59073.2023.00074
Zhang NChen QZheng ZZou YBissyandé TKlein JBird CSarro F(2023)iASTMapper: An Iterative Similarity-Based Abstract Syntax Tree Mapping AlgorithmProceedings of the 38th IEEE/ACM International Conference on Automated Software Engineering10.1109/ASE56229.2023.00178(863-874)Online publication date: 11-Nov-2023
https://dl.acm.org/doi/10.1109/ASE56229.2023.00178
Hütter TAugsten NKirsch CCarey MLi CIves ZBonifati AEl Abbadi A(2022)JEDI: These aren't the JSON documents you're looking for...Proceedings of the 2022 International Conference on Management of Data10.1145/3514221.3517850(1584-1597)Online publication date: 10-Jun-2022
https://dl.acm.org/doi/10.1145/3514221.3517850
Wu XZhu CLi YSpinellis DGousios GChechik MDi Penta M(2021)DIFFBASE: a differential factbase for effective software evolution managementProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468605(503-515)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468605
Bittner PSchultheiß AThüm TKehrer TYoung JLinsbauer LSpinellis DGousios GChechik MDi Penta M(2021)Feature trace recordingProceedings of the 29th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3468264.3468531(1007-1020)Online publication date: 20-Aug-2021
https://dl.acm.org/doi/10.1145/3468264.3468531
Erdweg SSzabó TPacak AFreund SYahav E(2021)Concise, type-safe, and efficient structural diffingProceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3453483.3454052(406-419)Online publication date: 19-Jun-2021
https://dl.acm.org/doi/10.1145/3453483.3454052
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents