On Boosting Holism in XML Twig Pattern Matching Using Structural Indexing Techniques

Searching for all occurrences of a twig pattern in an XML document is an important operation in XML query process-ing. Recently a holistic method TwigStack [2] has been proposed. The method avoids generating large interme-diate results which do not contribute to the final answer and is CPU and I/O optimal when twig patterns only have ancestor-descendant relationships. Another important di-rection of XML query processing is to build structural in-dexes [3][8][13][15] over XML documents to avoid unneces-sary scanning of source documents. We regard XML struc-tural indexing as a technique to partition XML documents and call it streaming scheme in our paper. In this paper we develop a method to perform holistic twig pattern match-ing on XML documents partitioned using various streaming schemes. Our method avoids unnecessary scanning of irrel-evant portion of XML documents. More importantly, de-pending on different streaming schemes used, it can process a large class of twig patterns consisting of both ancestor-descendant and parent-child relationships and avoid gen-erating redundant intermediate results. Our experiments demonstrate the applicability and the performance advan-tages of our approach. 1