Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-00676178
Contributor : Joachim Niehren <>
Submitted on : Sunday, August 25, 2013 - 12:53:47 PM
Last modification on : Thursday, February 21, 2019 - 10:52:55 AM
Long-term archiving on: : Tuesday, November 26, 2013 - 2:40:09 AM

File

1.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00676178v2⟩

Share

Metrics

Record views

706

Files downloads

521