Examining the impact of data-access cost on XML twig pattern matching

Sang-Geun Lee, Byung Gul Ryu, Kun Lung Wu

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


To process a large size of XML document, data-access time dominates the whole system performance in most cases. However, few techniques exist today that optimize the data-access cost of performing twig pattern matching. TJFast [18] is one of the few that do. TJFast could reduce the number of elements scanned by deriving all the element names along the path from the root to the element with the extended Dewey label of an element alone. However, there is still much room for improvement. We empirically observe that (1) many irrelevant elements can still be accessed and processed by TJFast, unnecessarily incurring both data-access and computation overhead, and (2) there still exists substantial redundant label-to-element name decoding, needlessly increasing processing cost. In this paper, we present TJFast-BNS, an optimization of TJFast, to further reduce the data-access cost of twig pattern matching. TJFast-BNS efficiently identifies and filters out many irrelevant elements by introducing a new labeling scheme, termed E2Dewey, and a novel pointer structure. E2Dewey includes the total number of children of an element in the element's label. This is used to quickly identify unnecessary paths. The pointer structure to the descendants of a branching element supports random access to leaf and non-top branching elements. Extensive performance studies on various datasets clearly show that our approach accesses much fewer elements to process a twig query than others, leading to a superior performance gain in execution time.

Original languageEnglish
Pages (from-to)24-43
Number of pages20
JournalInformation Sciences
Publication statusPublished - 2012 Oct 25


  • Branching node stream
  • Labeling scheme
  • Leaf node stream
  • Pointer structure
  • XML twig pattern matching

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 'Examining the impact of data-access cost on XML twig pattern matching'. Together they form a unique fingerprint.

Cite this