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

Abstract

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. © 2012 Elsevier Inc. All rights reserved.