HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Thursday, July 9, 2015 - 1:27:28 PM
Last modification on : Wednesday, March 23, 2022 - 3:51:21 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