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

Cited literature [23 references]  Display  Hide  Download
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


Files produced by the author(s)


  • HAL Id : hal-00676178, version 2


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⟩



Record views


Files downloads