Lineage encoding: An efficient wireless xml streaming supporting twig pattern queries

Jun Pyo Park, Chang Sup Park, Yon Dohn Chung

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


In this paper, we propose an energy and latency efficient XML dissemination scheme for the mobile computing. We define a novel unit structure called G-node for streaming XML data in the wireless environment. It exploits the benefits of the structure indexing and attribute summarization that can integrate relevant XML elements into a group. It provides a way for selective access of their attribute values and text content. We also propose a lightweight and effective encoding scheme, called Lineage Encoding, to support evaluation of predicates and twig pattern queries over the stream. The Lineage Encoding scheme represents the parent-child relationships among XML elements as a sequence of bit-strings, called Lineage Code(V, H), and provides basic operators and functions for effective twig pattern query processing at mobile clients. Extensive experiments using real and synthetic data sets demonstrate our scheme outperforms conventional wireless XML broadcasting methods for simple path queries as well as complex twig pattern queries with predicate conditions.

Original languageEnglish
Article number6030874
Pages (from-to)1559-1573
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number7
Publication statusPublished - 2013


  • Twig pattern matching
  • XML streaming
  • wireless broadcast

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Lineage encoding: An efficient wireless xml streaming supporting twig pattern queries'. Together they form a unique fingerprint.

Cite this