Early Nested Word Automata for XPath Query Answering on XML Streams

Abstract : Algorithms for answering XPath queries on XML streams have been studied intensively in the last decade. Nevertheless, there still exists no solution with high efficiency and large coverage. In this paper, we introduce early nested word automata in order to approximate earliest query answering algorithms for nested word automata in a highly efficient manner. We show that this approximation can be made tight in practice for automata obtained from XPath expressions. We have implemented an XPath streaming algorithm based on early nested word automata in the FXP tool. FXP outperforms most previous tools in efficiency, while covering more queries of the XPathMark benchmark. An extended version of the papers is available at http://www.grappa.univ-lille3.fr/~niehren/Papers/fxp/1.pdf
Type de document :
Communication dans un congrès
18th International Conference on Implementation and Application of Automata, Jul 2013, Halifax, Canada. pp.292-305, 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00676178
Contributeur : Joachim Niehren <>
Soumis le : dimanche 25 août 2013 - 12:53:47
Dernière modification le : samedi 16 janvier 2016 - 01:09:46
Document(s) archivé(s) le : mardi 26 novembre 2013 - 02:40:09

Fichier

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

Identifiants

  • HAL Id : hal-00676178, version 2

Citation

Denis Debarbieux, Olivier Gauwin, Joachim Niehren, Tom Sebastian, Mohamed Zergaoui. Early Nested Word Automata for XPath Query Answering on XML Streams. 18th International Conference on Implementation and Application of Automata, Jul 2013, Halifax, Canada. pp.292-305, 2013. 〈hal-00676178v2〉

Partager

Métriques

Consultations de la notice

438

Téléchargements de fichiers

172