Sublinear DTD Validity

Antoine Mbaye Ndione 1 Aurélien Lemay 1 Joachim Niehren 2
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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.

Type de document :
Communication dans un congrès
9th International Conference on. Language and Automata Theory and Applications, Mar 2015, Nice, France. 2015
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00803696
Contributeur : Inria Mostrare <>
Soumis le : jeudi 9 juillet 2015 - 13:27:28
Dernière modification le : mercredi 25 avril 2018 - 15:42:57
Document(s) archivé(s) le : mercredi 26 avril 2017 - 03:42:13

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-00803696, version 1

Collections

Citation

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. 2015. 〈hal-00803696〉

Partager

Métriques

Consultations de la notice

484

Téléchargements de fichiers

78