Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams

Tom Sebastian 1 Joachim Niehren 1
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 evaluator for navigational XPath on Xml streams with projection. The idea is to project away those parts of an Xml stream that are irrelevant for evaluating a given XPath query. This task is relevant for processing Xml streams in general since all Xml standard languages are based on XPath. The best existing streaming algorithm for navigational XPath queries runs nested word automata. Therefore, we develop a projection algorithm for nested word automata, for the first time to the best of our knowledge. It turns out that projection can speed up the evaluation of navigational XPath queries on Xml streams by a factor of 4 in average on the usual XPath benchmarks. The extended version of the document is available in pdf here.
Type de document :
Communication dans un congrès
International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Jan 2016, Harrachov, Czech Republic. 2015
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01182529
Contributeur : Tom Sebastian <>
Soumis le : jeudi 15 octobre 2015 - 17:44:11
Dernière modification le : vendredi 13 avril 2018 - 01:26:58
Document(s) archivé(s) le : lundi 18 janvier 2016 - 05:47:25

Fichier

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

Identifiants

  • HAL Id : hal-01182529, version 1

Collections

Citation

Tom Sebastian, Joachim Niehren. Projection for Nested Word Automata Speeds up XPath Evaluation on XML Streams . International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Jan 2016, Harrachov, Czech Republic. 2015. 〈hal-01182529〉

Partager

Métriques

Consultations de la notice

380

Téléchargements de fichiers

66