The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Detecting changes in XML documents
Abstract
We present a diff algorithm for XML data. This work is motivated by the support for change control in the context of the Xyleme project that is investigating dynamic warehouses capable of storing massive volumes of XML data. Because of the context, our algorithm has to be very efficient in terms of speed and memory space even at the cost of some loss of quality. Also, it considers, besides insertions, deletions and updates (standard in diffs), a move operation on subtrees that is essential in the context of XML. Intuitively, our diff algorithm uses signatures to match (large) subtrees that were left unchanged between the old and new versions. Such exact matchings are then possibly propagated to ancestors and descendants to obtain more matchings. It also uses XML specific information such as ID attributes. We provide a performance analysis of the algorithm. We show that it runs in average in linear time vs. quadratic time for previous algorithms. We present experiments on synthetic data that confirm the analysis. Since this problem is NP-hard, the linear time is obtained by trading some quality. We present experiments (again on synthetic data) that show that the output of our algorithm is reasonably close to the optimal in terms of quality. Finally we present experiments on a small sample of XML pages found on the Web.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Binary Codes capable of currecting deletions, insertions, and reversals
Levenshtein, V. I. (1965) · Soviet physics. Doklady · Cited by 14,807
The String-to-String Correction Problem
Wagner, R. A., & Fischer, M. J. (1974) · Journal of the ACM · doi:10.1145/321796.321811 · Cited by 3,032
Data on the Web from relations to semistructured data and XML
Abiteboul, S., Buneman, P., & Suciu, D. M. (2000) · Cited by 1,062
Self-citationThe Tree-to-Tree Correction Problem
Tai, K.-C. (1979) · Journal of the ACM · doi:10.1145/322139.322143 · Cited by 865
Efficient Filtering of XML Documents for Selective Dissemination of Information
Altınel, M., & Franklin, M. J. M. (2000) · Cited by 548
Change detection in hierarchically structured information
Chawathe, S. S., Rajaraman, A., Garcia-Molina, H., & Widom, J. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233366 · Cited by 484
The tree-to-tree editing problem
Selkow, S. M. (1977) · Information Processing Letters · doi:10.1016/0020-0190(77)90064-3 · Cited by 474
XML-QL: A Query Language for XML
Deutsch, A. (1998) · Cited by 422
On the editing distance between unordered labeled trees
Zhang, K., Statman, R., & Shasha, D. E. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90136-j · Cited by 359
Identifying syntactic differences between two programs
Yang, W. (1991) · Software: Practice and Experience · doi:10.1002/spe.4380210706 · Cited by 346
Meaningful change detection in structured data
Chawathe, S. S., & García-Molina, H. (1997) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/253260.253266 · Cited by 320
(1998) · Choice Reviews Online · doi:10.5860/choice.36-1021 · Cited by 280
Time Warps, String Edits, and Macromolecules
Sankhoff, D., & Kruskal, J. B. (1999) · University of Groningen research database (University of Groningen / Centre for Information Technology) · Cited by 213
Change-Centric Management of Versions in an XML Warehouse
Marian, A., Abiteboul, S., Cobéna, G., & Mignet, L. (2000) · Cited by 189
Self-citationChange detection in hierarchically structured information
Chawathe, S. S., Rajaraman, A., Garcia-Molina, H., & Widom, J. (1996) · ACM SIGMOD Record · doi:10.1145/235968.233366 · Cited by 165
A system for approximate tree matching
Wang, J. T.-L., Zhang, K., Jeong, K., & Shasha, D. E. (1994) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/69.298173 · Cited by 152
A Tree-to-Tree Distance and Its Application to Cluster Analysis
Lu, S.-Y. (1979) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1979.6786615 · Cited by 138
Fast algorithms for the unit cost editing distance between trees
Shasha, D. E., & Zhang, K. (1990) · Journal of Algorithms · doi:10.1016/0196-6774(90)90011-3 · Cited by 135
Efficient Snapshot Differential Algorithms for Data Warehousing
Labio, W. J., & García-Molina, H. (1996) · Cited by 111
Cited by
Fine-grained and accurate source code differencing
Falleri, J.-R., Morandat, F., Blanc, X., Martinez, M., & Monperrus, M. (2014) · Proceedings of the 29th ACM/IEEE International Conference on Automated Software Engineering · doi:10.1145/2642937.2642982 · Cited by 549
A content-driven reputation system for the wikipedia
Adler, B. T., & de Alfaro, L. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242608 · Cited by 440
X-Diff: an effective change detection algorithm for XML documents
Wang, Y., DeWitt, D. J., & Cai, J.-Y. (2004) · Proceedings 19th International Conference on Data Engineering (Cat. No.03CH37405) · doi:10.1109/icde.2003.1260818 · Cited by 348
Scharm, M., Wolkenhauer, O., & Waltemath, D. (2016) · Bioinformatics · doi:10.1093/bioinformatics/btv484 · Cited by 24
Metadata
- Authors
- Cobena, G., Abiteboul, S., & Marian, A.
- Venue
- Proceedings 18th International Conference on Data Engineering
- Publisher
- IEEE Comput. Soc
- Published
- 2003-06-25
- Pages
- 41-52
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2136393336
- Cited by
- 422
- References
- 19
- FWCI
- 22.94
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.