C-tree indexing for holistic twig joins

With the growing importance of semi-structure data in information exchange, effort has been put in providing an effective mechanism to match a twig query in an XML database. Bruno et al. have proposed a novel algorithm TwigStack to deal with the twig query pattern by scanning the tag streams only once. In this paper, we propose a new index called C-Tree and two algorithms named NestTwigStack and ADTwigStack to speed up the processing of twig pattern queries by omitting some elements that can be processed without scanning. Using C-Tree, our algorithms can accelerate both the ancestor-descendant and parent-child edges by skipping the elements with their context in documents. We complement our research with experiments on a set of real and synthetic data, which are intended to show the significant superiority of our algorithms over the previous algorithms.