research-article

Introduction to the universal delta model

Author:

Gioele BarabucciAuthors Info & Claims

DocEng '13: Proceedings of the 2013 ACM symposium on Document engineering

Pages 47 - 56

https://doi.org/10.1145/2494266.2494284

Published: 10 September 2013 Publication History

Abstract

There are currently no shared formalization of the output of diff algorithms, the so called deltas. From a theoretical point of view, without such a formalization it is difficult to compare the output of different algorithms. In more practical terms, the lack of a shared formalization makes it hard to create tools that support more than one diff algorithm.

This paper introduces the universal delta model: a formal definition of changes (the pieces of information that records that something has changed), operations (the definitions of the kind of change that happened) and deltas (coherent summaries of what has changed between two documents). The fundamental mechanism that makes the changes as defined in the universal delta model a very expressive tool, is the use of encapsulation relations between changes: changes are not only simple records of what has changed, they can also be combined into more complex changes to express the fact that the algorithm has detected more nuanced kinds of changes. The universal delta model has been applied successfully in various projects that served as an evaluation for the model. In addition to the model itself, this paper briefly describes one of these projects: the measurement of objective qualities of deltas as produced by various diff algorithms.

References

[1]

Barabucci, G. OntoEv: See how an ontology has evolved through its development. http://barabucc.web.cs.unibo.it/ontoev.

[2]

Barabucci, G. A universal delta model. PhD thesis, Universita di Bologna, Apr. 2013.

[3]

Barabucci, G., Cervone, L., Palmirani, M., Peroni, S., and Vitali, F. Multi-layer markup and ontological structures in Akoma Ntoso. In AI Approaches to the Complexity of Legal Systems. Complex Systems, the Semantic Web, Ontologies, Argumentation, and Dialogue - International Workshops AICOL-I/IVR-XXIV Beijing, China, September 19, 2009 and AICOL-II/JURIX 2009, Rotterdam,The Netherlands, December 16, 2009 Revised Selected Papers (2010), P. Casanovas, U. Pagallo, G. Sartor, and G. Ajani, Eds., vol. 6237 of Lecture Notes in Computer Science, Springer, pp. 133--149.

Digital Library

[4]

Barabucci, G., and Vitali, F. XDTD as a simple validation language for XML-based legal documents. In Legal Knowledge and Information Systems - JURIX 2009: The Twenty-Second Annual Conference on Legal Knowledge and Information Systems, Rotterdam, The Netherlands, 16-18 December 2009 (2009), G. Governatori, Ed., vol. 205 of Frontiers in Artificial Intelligence and Applications, IOS Press, pp. 1--10.

Digital Library

[5]

Berners-Lee, T., and Connolly, D. Delta: an ontology for the distribution of differences between RDF graphs. http://www.w3.org/DesignIssues/Diff, 2009. accessed Nov 26, 2012.

[6]

Burns, R., Burns, A. C., and Long, D. D. E. A linear time, constant space differencing algorithm. In Performance, Computing, and Communications Conference, 1997 (feb 1997), IEEE International, pp. 429--436.

[7]

Cóbena, G., Abiteboul, S., and Marian, A. Detecting changes in XML documents. In Proceedings of the 18th International Conference on Data Engineering, San Jose, CA, USA, February 26 - March 1, 2002 (2002), R. Agrawal and K. R. Dittrich, Eds., IEEE Computer Society, pp. 41--52.

Digital Library

[8]

Di Iorio, A., Schirinzi, M., Vitali, F., and Marchetti, C. A natural and multi-layered approach to detect changes in tree-based textual documents. In Enterprise Information Systems, 11th International Conference, ICEIS 2009, Milan, Italy, May 6-10, 2009. Proceedings (2009), J. Filipe and J. Cordeiro, Eds., vol. 24 of Lecture Notes in Business Information Processing, Springer, pp. 90--101.

[9]

Hartung, M., Kirsten, T., Gross, A., and Rahm, E. Onex: Exploring changes in life science ontologies. BMC Bioinformatics 10 (2009).

[10]

Hunt, J. W., and McIllroy, M. An algorithm for differential file comparison. Tech. Rep. 41, AT&T Bell Laboratories Inc., 1976.

[11]

Klein, M. Change Management for Distributed Ontologies. PhD thesis, Vrije Universiteit Amsterdam, Aug. 2004.

[12]

Lindholm, T., Kangasharju, J., and Tarkoma, S. Fast and simple XML tree differencing by sequence alignment. In Proceedings of the 2006 ACM Symposium on Document Engineering, Amsterdam, The Netherlands, October 10-13, 2006 (2006), D. C. A. Bulterman and D. F. Brailsford, Eds., ACM, pp. 75--84.

Digital Library

[13]

Noy, N. F., and Musen, M. A. PROMPTDIFF: a fixed-point algorithm for comparing ontology versions. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28 - August 1, 2002, Edmonton, Alberta, Canada (2002), R. Dechter and R. S. Sutton, Eds., AAAI Press / The MIT Press, pp. 744--750.

Digital Library

[14]

Papavassiliou, V., Flouris, G., Fundulaki, I., Kotzinos, D., and Christophides, V. On detecting high-level changes in RDF/S KBs. In The Semantic Web - ISWC 2009, 8th International Semantic Web Conference, ISWC 2009, Chantilly, VA, USA, October 25-29, 2009. Proceedings (2009), A. Bernstein, D. R. Karger, T. Heath, L. Feigenbaum, D. Maynard, E. Motta, and K. Thirunarayan, Eds., vol. 5823 of Lecture Notes in Computer Science, Springer, pp. 473--488.

Digital Library

[15]

Percival, C. Naive differences of executable code. http://www.daemonology.net/bsdiff/, accessed Nov 26, 2012, 2003.

[16]

Ronnau, S., and Borghoff, U. M. Versioning XML-based office documents. Multimedia Tools and Applications 43, 3 (2009), 253--274.

Digital Library

[17]

Ronnau, S., Pauli, C., and Borghoff, U. M. Merging changes in XML documents using reliable context fingerprints. In Proceedings of the 2008 ACM Symposium on Document Engineering, Sao Paulo, Brazil, September 16-19, 2008 (2008), M. da Graca Campos Pimentel, D. C. A. Bulterman, and L. F. G. Soares, Eds., pp. 52--61.

Digital Library

[18]

Ronnau, S., Philipp, G., and Borghoff, U. M. Efficient change control of XML documents. In Proceedings of the 2009 ACM Symposium on Document Engineering, Munich, Germany, September 16-18, 2009 (2009), U. M. Borghoff and B. Chidlovskii, Eds., ACM, pp. 3--12.

Digital Library

[19]

Ronnau, S., Scheffczyk, J., and Borghoff, U. M. Towards XML version control of office documents. In Proceedings of the 2005 ACM Symposium on Document Engineering, Bristol, UK, November 2-4, 2005 (2005), A. Wiley and P. R. King, Eds., pp. 10--19.

Digital Library

[20]

Thao, C., and Munson, E. V. Using versioned tree data structure, change detection and node identity for three-way XML merging. In Proceedings of the 2010 ACM Symposium on Document Engineering, Manchester, United Kingdom, September 21-24, 2010 (2010), A. Antonacopoulos, M. J. Gormish, and R. Ingold, Eds., pp. 77--86.

Digital Library

Cited By

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
Di Iorio ASpinaci GVitali FBorghoff USchimmler S(2019)Multi-layered edits for meaningful interpretation of textual differencesProceedings of the ACM Symposium on Document Engineering 201910.1145/3342558.3345406(1-4)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1145/3342558.3345406
Barabucci GBorghoff UDi Iorio ASchimmler SMunson E(2018)Document ChangesProceedings of the ACM Symposium on Document Engineering 201810.1145/3209280.3232792(1-2)Online publication date: 28-Aug-2018
https://dl.acm.org/doi/10.1145/3209280.3232792
Show More Cited By

Index Terms

Introduction to the universal delta model
1. Applied computing
  1. Document management and text processing
    1. Document management
      1. Version control

Recommendations

Strongly Universal Interval Hypergraphs
Measuring the quality of diff algorithms

The automatic detection of differences between documents is a very common task in several domains. This paper introduces a formal way to compare diff algorithms and to analyze the deltas they produce. There is no one-fits-all definition for the quality ...
Multi-layered edits for meaningful interpretation of textual differences
DocEng '19: Proceedings of the ACM Symposium on Document Engineering 2019

The way humans and algorithms look at and understand differences between versions and variants of the same text may be very different. While correctness and overall byte length are fundamental aspects of good outputs of diff algorithms, they do not ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DocEng '13: Proceedings of the 2013 ACM symposium on Document engineering

September 2013

582 pages

ISBN:9781450317894

DOI:10.1145/2494266

Conference Chair:
Simone Marinai
University of Florence, Italy
,
Program Chair:
Kim Marriott
Monash University, Australia

Copyright © 2013 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 the author(s) 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

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 September 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DocEng '13

Sponsor:

SIGWEB

DocEng '13: ACM Symposium on Document Engineering 2013

September 10 - 13, 2013

Florence, Italy

Acceptance Rates

DocEng '13 Paper Acceptance Rate 16 of 50 submissions, 32%;

Overall Acceptance Rate 194 of 564 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
195
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Di Iorio ASpinaci GVitali FBorghoff USchimmler S(2019)Multi-layered edits for meaningful interpretation of textual differencesProceedings of the ACM Symposium on Document Engineering 201910.1145/3342558.3345406(1-4)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1145/3342558.3345406
Barabucci GBorghoff UDi Iorio ASchimmler SMunson E(2018)Document ChangesProceedings of the ACM Symposium on Document Engineering 201810.1145/3209280.3232792(1-2)Online publication date: 28-Aug-2018
https://dl.acm.org/doi/10.1145/3209280.3232792
Barabucci G(2018)diffiProceedings of the ACM Symposium on Document Engineering 201810.1145/3209280.3229084(1-4)Online publication date: 28-Aug-2018
https://dl.acm.org/doi/10.1145/3209280.3229084
de la Torre GRobbes RBergel AZaidman AKamei YHill E(2018)Imprecisions diagnostic in source code deltasProceedings of the 15th International Conference on Mining Software Repositories10.1145/3196398.3196404(492-502)Online publication date: 28-May-2018
https://dl.acm.org/doi/10.1145/3196398.3196404
Barabucci GBarabucci GBorghoff UIorio ASchimmler SMunson E(2016)Manuscript annotations as deltasProceedings of the 4th International Workshop on Document Changes: Modeling, Detection, Storage and Visualization10.1145/2993585.2993591(1-2)Online publication date: 13-Sep-2016
https://dl.acm.org/doi/10.1145/2993585.2993591
Barabucci GCiancarini PDi Iorio AVitali F(2016)Measuring the quality of diff algorithmsComputer Standards & Interfaces10.1016/j.csi.2015.12.00546:C(52-65)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1016/j.csi.2015.12.005
Barabucci GBarabucci GBorghoff UIorio AMaier SMunson E(2015)Minimal and functionally complete operation sets for deltasProceedings of the 3rd International Workshop on (Document) Changes: modeling, detection, storage and visualization10.1145/2881631.2881634(7-10)Online publication date: 8-Sep-2015
https://dl.acm.org/doi/10.1145/2881631.2881634

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents