XQStream++: Fast tuple extraction algorithm for streaming XML data

Byung Gul Ryu, Jongwoo Ha, Sang-Geun Lee

Research output: Contribution to journalArticlepeer-review


Tuple extraction from streaming XML should be cost effective for real-time query evaluation. Recently, StreamTX exhibits a good performance in terms of both running time and memory usage to support the tuple extraction queries for streaming XML. However, we empirically observe that StreamTX incurs computational overhead unnecessarily, since it builds on TwigStack, an XML query processing algorithm originally developed for stored XML. In this paper, we first design a non-recursive XQStream algorithm to handle inefficient recursive calls of StreamTX. Subsequently, we extend the basic XQStream by incorporating two novel schemes: (1) the relational pointer to efficiently and effectively evaluate the structural relationship of elements, and (2) the pattern reuse to reduce redundant path evaluations for pattern matching. The performance evaluation on various datasets provides new empirical findings. First, XQStream++, which incorporates the relational pointer and the pattern reuse scheme into XQStream, significantly outperforms the state-of-the-art algorithms in running time with a small, nearly constant memory usage. Second, the most recently released XQuery engines outperform StreamTX in running time.

Original languageEnglish
Pages (from-to)311-326
Number of pages16
JournalInformation Sciences
Publication statusPublished - 2015 Sept 1

Bibliographical note

Funding Information:
This work was in part supported by the Basic Science Research Program and the Next-Generation Information Computing Development Program through National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (Nos. NRF-2013R1A1A2061163 and 2012M3C4A7033344 ).

Publisher Copyright:
© 2014 Elsevier Inc. All rights reserved.


  • Pattern reuse
  • Relational pointer
  • Streaming XML
  • Tuple extraction

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


Dive into the research topics of 'XQStream++: Fast tuple extraction algorithm for streaming XML data'. Together they form a unique fingerprint.

Cite this