article

Free access

Meaningful change detection in structured data

Authors:

Sudarshan S. Chawathe,

Hector Garcia-MolinaAuthors Info & Claims

ACM SIGMOD Record, Volume 26, Issue 2

Pages 26 - 37

https://doi.org/10.1145/253262.253266

Published: 01 June 1997 Publication History

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.

References

[1]

S. Chawathe and H. Garcia-Molina. Meaningful change detection in structured data. Available at URL http://w~ra-db, stanford, edu, 1997. Extended version.

[2]

S. Chawathe, H. Garcia-Molina, J. Hammer, K. Ireland, Y. Papakonstantinou, J. Ullman, and J. Widom. The Tsimmis project: Integration of heterogeneous information sources. In Proceedings of lOOth Anniversary Meeting of the information Processing Society of Japan, pages 7-18, Tokyo, Japan, October 1994.

[3]

S. Chawathe, A. Rajaraman, H. Garcia- Mofina, and J. Widom. Change detection in hierarchically structured information. In Proceedings o} the A CM SIGMOD International Conference on Management o} Data, pages 493-504, Montreal, Quebec, June 1996.

Digital Library

[4]

M. Haertel, D. Hayes, R. Stallman, L. Tower, P. Eggert., and W. Davison. The GNU diff program. Texinfo system documentation. Available by anonymous FTP from prep. ai .mit. edu.

[5]

E. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.

[6]

W. Labio and H. Garcia-Molina. Efficient snapshot differential algorithms for data warehousing. In Proceedings of the International Conference on Very Large Data Bases, Bombay, India, September 1996.

Digital Library

[7]

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

[8]

C. Papadimitriou and K. Steiglitz. Combinatorial Optimization. Prentice-Hall, 1982.

Digital Library

[9]

E. Rothberg. The wmatch program for finding a maximum-weight matching for undirected graphs. Live OR collection. Available at URL http ://w~. orsoc, org. uk.

[10]

D. Shasha, J. Wang, K. Zhang, and F. Shih. Exact and approximate algorithms for unordered tree matching. IEEE Transactions on Systems, Man, and Cybernetics, 24(4):668-678, April 1994.

[11]

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

Digital Library

[12]

R. Wagner. On the complexity of the extended string-to-string correction problem. In Seventh A CM Symposium on the Theory o} Computation, 1975.

Digital Library

[13]

R. Wagner and M. Fischer. The string-to-string correction problem. Journal o} the Association of Computing Machinery, 21(1):168-173, January 1974.

Digital Library

[14]

S. Wu, U. Manber, and G.Myers. An O(NP) sequence comparison algorithm, ln}ormation Processing Letters, 35:317-323, September 1990.

Digital Library

[15]

J. Widom and J. Ullman. The C3 project: Changes, consistency, and configurations in heterogeneous distributed information systems. Unpublished manuscript; available at URL http://www-db, stan~ord, edu, 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

[17]

K. Zhang, J. Wang, and D. Shasha. On the editing distance between undirected acyclic graphs. International Journal of Foundations of Computer Science, 1995.

Cited By

Zhu JCai SDeng FOoi BZhang W(2023)METER: A Dynamic Concept Adaptation Framework for Online Anomaly DetectionProceedings of the VLDB Endowment10.14778/3636218.363623317:4(794-807)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636233
Shraga RMiller R(2023)Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-VProceedings of the VLDB Endowment10.14778/3583140.358316916:6(1587-1600)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583169
Cuculovic MFondement FDevanne MWeber JHassenforder M(2022)Semantics to the rescue of document‐based XML diff: A JATS case studySoftware: Practice and Experience10.1002/spe.307452:6(1496-1516)Online publication date: 12-Feb-2022
https://doi.org/10.1002/spe.3074
Show More Cited By

Index Terms

Meaningful change detection in structured data

Recommendations

Meaningful change detection in structured data
SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data

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 ...
Efficient change detection in tree-structured data
HSI'03: Proceedings of the 2nd international conference on Human.society@internet

We present X-tree Diff, a change detection algorithm for tree-structured data such as XML/HTML documents. X-tree Diff uses a specially designed data structure, called X-tree. Nodes of X-tree have a special hash-valued field representing the structure ...
A change detection system for unordered XML data using a relational model

The dramatic increase in the evolution of XML data available on the Internet requires a change detection system to keep track of important changes occurring during their life time. In this paper, we introduce a novel approach of detecting changes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMOD Record

ACM SIGMOD Record Volume 26, Issue 2

June 1997

583 pages

ISSN:0163-5808

DOI:10.1145/253262

Chairman:
Sudha Ram
Univ. of Arizona, Tucson
,
Editor:
Joan M. Peckham
Univ. of Rhode Island, Kingston

Issue’s Table of Contents

SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data
June 1997
594 pages
ISBN:0897919114
DOI:10.1145/253260
Editors:
Joan M. Peckman
Univ. of Rhode Island, Kingston
,
Sudha Ram
Univ. of Arizona, Tucson
,
Michael Franklin

Copyright © 1997 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1997

Published in SIGMOD Volume 26, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

197
Total Citations
View Citations
1,496
Total Downloads

Downloads (Last 12 months)156
Downloads (Last 6 weeks)20

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhu JCai SDeng FOoi BZhang W(2023)METER: A Dynamic Concept Adaptation Framework for Online Anomaly DetectionProceedings of the VLDB Endowment10.14778/3636218.363623317:4(794-807)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.14778/3636218.3636233
Shraga RMiller R(2023)Explaining Dataset Changes for Semantic Data Versioning with Explain-Da-VProceedings of the VLDB Endowment10.14778/3583140.358316916:6(1587-1600)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583169
Cuculovic MFondement FDevanne MWeber JHassenforder M(2022)Semantics to the rescue of document‐based XML diff: A JATS case studySoftware: Practice and Experience10.1002/spe.307452:6(1496-1516)Online publication date: 12-Feb-2022
https://doi.org/10.1002/spe.3074
Valiente GValiente G(2021)Tree IsomorphismAlgorithms on Trees and Graphs10.1007/978-3-030-81885-2_4(113-180)Online publication date: 12-Oct-2021
https://doi.org/10.1007/978-3-030-81885-2_4
Cuculovic MFondement FDevanne MWeber JHassenforder M(2020)Change Detection on JATS Academic ArticlesProceedings of the ACM Symposium on Document Engineering 202010.1145/3395027.3419581(1-10)Online publication date: 29-Sep-2020
https://dl.acm.org/doi/10.1145/3395027.3419581
Kifer D(2018)Change Detection on StreamsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_49(411-415)Online publication date: 7-Dec-2018
https://doi.org/10.1007/978-1-4614-8265-9_49
Vassena MChapman JSwierstra W(2016)Generic Diff3 for algebraic datatypesProceedings of the 1st International Workshop on Type-Driven Development10.1145/2976022.2976026(62-71)Online publication date: 18-Sep-2016
https://dl.acm.org/doi/10.1145/2976022.2976026
Kifer D(2016)Change Detection on StreamsEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_49-2(1-5)Online publication date: 20-Dec-2016
https://doi.org/10.1007/978-1-4899-7993-3_49-2
Missier PWoodman SHiden HWatson P(2016)Provenance and data differencing for workflow reproducibility analysisConcurrency and Computation: Practice & Experience10.1002/cpe.303528:4(995-1015)Online publication date: 25-Mar-2016
https://dl.acm.org/doi/10.1002/cpe.3035
Finis JBrunel RKemper ANeumann TMay NFaerber F(2015)Indexing highly dynamic hierarchical dataProceedings of the VLDB Endowment10.14778/2794367.27943698:10(986-997)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.14778/2794367.2794369
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 Issue’s Table of Contents