Efficient eager XPath filtering over XML streams

Kazuhito Hagio, Takashi Ohgami, Hideo Bannai, Masayuki Takeda

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


We address the embedding existence problem (often referred to as the filtering problem) over streaming XML data for Conjunctive XPath (CXP). Ramanan (2009) considered Downward CXP, a fragment of CXP that involves downward navigational axes only, and presented a streaming algorithm which solves the problem in O(|P||D|) time using only O(|P|height(D)) bits of space, where |P| and |D| are the sizes of a query P and an XML data D, respectively, and height(D) denotes the tree height of D. Unfortunately, the algorithm is lazy in the sense that it does not necessarily report the answer even after enough information has been gathered from the input XML stream. In this paper, we present an eager streaming algorithm that solves the problem with same time and space complexity. We also show the algorithm can be easily extended to Backward CXP a larger fragment of CXP.

Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference 2011
Number of pages15
Publication statusPublished - 2011
EventPrague Stringology Conference 2011, PSC 2011 - Prague, Czech Republic
Duration: Aug 29 2011Aug 31 2011

Publication series

NameProceedings of the Prague Stringology Conference 2011


OtherPrague Stringology Conference 2011, PSC 2011
Country/TerritoryCzech Republic

All Science Journal Classification (ASJC) codes

  • Mathematics(all)


Dive into the research topics of 'Efficient eager XPath filtering over XML streams'. Together they form a unique fingerprint.

Cite this