Titre :

Sublinear DTD Validity

Auteur(s) :

Ndione, Antoine Mbaye [Auteur]
Linking Dynamic Data [LINKS]
Lemay, Aurélien [Auteur]
Linking Dynamic Data [LINKS]
Niehren, Joachim [Auteur]
Linking Dynamic Data [LINKS]

Titre de la manifestation scientifique :

9th International Conference on. Language and Automata Theory and Applications

Ville :

Nice

Pays :

France

Date de début de la manifestation scientifique :

2015-03-02

Date de publication :

2015-03-02

Discipline(s) HAL :

Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Base de données [cs.DB]

Résumé en anglais : [en]

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 ...
Lire la suite >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. <p><a href="https://hal.inria.fr/hal-01187016">A long version is available here.</a></p>Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL