Skip to Main content Skip to Navigation
Conference papers

Sublinear DTD Validity

Antoine Mbaye Ndione 1 Aurélien Lemay 1 Joachim Niehren 1
1 LINKS - Linking Dynamic Data
CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189, Inria Lille - Nord Europe
Abstract : We present an efficient algorithm for testing approximate DTD validity modulo the strong tree edit distance. Our algorithm inspects XML documents in a probabilistic manner. It detects with high probability the nonvalidity of XML documents with a large fraction of errors, measured in terms of the strong tree edit distance from the DTD. The run time depends polynomially on the depth of the XML document tree but not on its size, so that it is sublinear in most cases. Therefore, our algorithm can be used to speed up exact DTD validators that run in linear time. We also prove a negative result showing that the run time of any approximate DTD validity tester must depend on the depth of the input tree.

A long version is available here.

Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Inria Mostrare <>
Submitted on : Thursday, July 9, 2015 - 1:27:28 PM
Last modification on : Friday, December 11, 2020 - 6:44:06 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 3:42:13 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : hal-00803696, version 1



Antoine Mbaye Ndione, Aurélien Lemay, Joachim Niehren. Sublinear DTD Validity. 9th International Conference on. Language and Automata Theory and Applications, Mar 2015, Nice, France. ⟨hal-00803696⟩



Record views


Files downloads