• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Early = Earliest?
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Rapport de recherche
Title :
Early = Earliest?
Author(s) :
Lick, Anthony [Auteur]
École normale supérieure - Cachan [ENS Cachan]
Niehren, Joachim [Auteur] refId
Linking Dynamic Data [LINKS ]
Laboratoire d'Informatique Fondamentale de Lille [LIFL]
Institution :
inria lille
Publication date :
2013-10-16
HAL domain(s) :
Informatique [cs]/Informatique et langage [cs.CL]
English abstract : [en]
Early query answering is the core issue of memory efficient query evaluation on data streams. The idea is to select and reject answer candidates as early as possible on the stream, so that they do not have to be stored in ...
Show more >
Early query answering is the core issue of memory efficient query evaluation on data streams. The idea is to select and reject answer candidates as early as possible on the stream, so that they do not have to be stored in main memory. Since earliest query answering is unfeasible for XPath, as first no- ticed by Benedikt, Jeffrey and Ley-Wild in 2008, most exist- ing streaming algorithms for XPath approximate it in some early manner, while focussing on high time efficiency. Such approximations, however, spoil all theoretical guarantees on memory efficiency. In this paper, we prove that earliest query answering is indeed feasible for positive Forward XPath queries, which have neither unsatisfiable nor valid subqueries. The core in- sight is that a variant of Colmerauer's independence property can be proven for the corresponding fragment of the FXP tree logic. Based on this independence property, we can show that the early query answering algorithm from [13], which is based on a compiler from FXP to early nested word automata, is indeed earliest for all positive FXP0 queries with neither unsatisfiable nor valid subformulas. Further- more, this algorithm outperforms most previous algorithms for XPath evaluation on XML streams in time efficiency and coverage, as shown elsewhere. <a href="http://www.grappa.univ-lille3.fr/~niehren/Papers/early-equal-earliest/0.pdf">Available here</a>.</p>Show less >
Language :
Anglais
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Université de Lille

Mentions légales
Université de Lille © 2017