Selectivity-sensitive shared evaluation of multiple continuous XPath queries over XML streams

Hyun Ho Lee, Won Suk Lee

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


One of the primary issues confronting XML message brokers is the difficulty associated with processing a large set of continuous XPath queries over incoming XML streams. This paper proposes a novel system designed to present an effective solution to this problem. The proposed system transforms multiple XPath queries before their run-time into a new data structure, called an XP-table, by sharing their common constraints. An XP-table is matched with a stream relation (SR) transformed from a target XML stream by a SAX parser. This arrangement is intended to minimize the run-time workload of continuous query processing. In addition, an early-query-termination strategy is proposed as an improved alternative to the basic approach. It optimizes query processing by arranging the evaluation sequence of the member-lists (m-lists) of an XP-table adaptively and offers increased efficiency, especially in cases of low selectivity. System performance is estimated and verified through a variety of experiments, including comparisons with previous approaches such as YFilter and LazyDFA. The proposed system is practically linear-scalable and stable for evaluating a set of XPath queries in a continuous and timely fashion. Crown

Original languageEnglish
Pages (from-to)1984-2001
Number of pages18
JournalInformation sciences
Issue number12
Publication statusPublished - 2009 May 30

Bibliographical note

Funding Information:
This work was supported by the Korea Science and Engineering Foundation (KOSEF) NRL Program grant funded by the Korea government (MEST) (No. R0A-2006-000-10225-0).

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Selectivity-sensitive shared evaluation of multiple continuous XPath queries over XML streams'. Together they form a unique fingerprint.

Cite this