Early Nested Word Automata for XPath Query Answering on XML Streams

Denis Debarbieux 1 Olivier Gauwin 2 Joachim Niehren 1 Tom Sebastian 3, 1 Mohamed Zergaoui 3
1 LINKS - Linking Dynamic Data
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
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. Our early query answering algorithm is based on stack-and-state sharing for running early nested word automata on all answer candidates with on-the-fly determinization. We prove tight upper complexity bounds on time and space consumption. We have implemented our algorithm in the QuiXPath system and show that it outperforms all previous tools in coverage on the XPathMark benchmark, while obtaining very high time and space efficiency and scaling to huge Xml streams. Furthermore, it turns out that our early query answering algorithm is earliest in practice on most queries from the XPathMark benchmark.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2015, pp.100-127
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00966625
Contributeur : Inria Links <>
Soumis le : vendredi 20 février 2015 - 17:52:39
Dernière modification le : mercredi 25 avril 2018 - 15:44:55
Document(s) archivé(s) le : jeudi 28 mai 2015 - 16:20:26

Fichier

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

Identifiants

  • HAL Id : hal-00966625, version 1

Citation

Denis Debarbieux, Olivier Gauwin, Joachim Niehren, Tom Sebastian, Mohamed Zergaoui. Early Nested Word Automata for XPath Query Answering on XML Streams. Theoretical Computer Science, Elsevier, 2015, pp.100-127. 〈hal-00966625〉

Partager

Métriques

Consultations de la notice

482

Téléchargements de fichiers

375