28559 articles – 22057 references  [version française]

hal-00676178, version 1

Early Nested Word Automata for XPath Query Answering on XML Streams

Denis Debarbieux (http://researchers.lille.inria.fr/~debarbie/) 1, 2, Olivier Gauwin (http://www.labri.fr/perso/ogauwin/) 3, Joachim Niehren (, http://researchers.lille.inria.fr/~niehren/) a, 1, 2, Tom Sebastian (http://chercheurs.lille.inria.fr/~sebastia/) b, 1, 2, 4, Mohamed Zergaoui b, 5

18th International Conference on Implementation and Application of Automata (2013) 12

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

  • a –  INRIA
  • b –  Innovimax
  • 1:  Laboratoire d'Informatique Fondamentale de Lille (LIFL)
  • CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – INRIA
  • 2:  LINKS (INRIA Lille - Nord Europe)
  • INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales
  • 3:  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
  • CNRS : UMR5800 – Université Sciences et Technologies - Bordeaux I – École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB) – Université Victor Segalen - Bordeaux II
  • 4:  innovimax
  • Innovimax
  • 5:  Innovimax
  • Innovimax
  • Domain : Computer Science/Learning
    Computer Science/Document and Text Processing
 
  • hal-00676178, version 1
  • http://hal.inria.fr/hal-00676178
  • oai:hal.inria.fr:hal-00676178
  • From: Joachim Niehren <>
  • Submitted on: Thursday, 9 May 2013 14:29:19
  • Updated on: Friday, 10 May 2013 09:06:36