A Survey of XML Tree Patterns <s> Fig. 13. Sample DataGuide <s> A common problem of XML query algorithms is that execution time and input size grows rapidly as the size of XML document increases. In this paper, we propose a version-labeling scheme and TwigVersion algorithm to address this problem. The version-labeling scheme is utilized to identify all repetitive structures in XML documents, and the Version Tree is constructed to hold such version information. To process a query, TwigVersion generates a filter through the created Version Tree, and the final answer to the query can be retrieved from the database easily through the filtering process. Both theoretical proof and experimental results reported in this paper demonstrate that the concise structure of Version Tree and the reduced input size make TwigVersion outperform the existing approaches. <s> BIB001 </s> A Survey of XML Tree Patterns <s> Fig. 13. Sample DataGuide <s> With the rapid emergence of XML as an enabler for data exchange and data transfer over the Web, querying XML data has become a major concern. In this paper, we present a hybrid system, TwigX-Guide; an extension of the well-known DataGuide index and region encoding labeling to support twig query processing. With TwigX-Guide, a complex query can be decomposed into a set of path queries, which are evaluated individually by retrieving the path or node matches from the DataGuide index table and subsequently joining the results using the holistic twig join algorithm TwigStack. TwigX-Guide improves the performance of TwigStack for queries with parent-child relationships and mixed relationships by reducing the number of joins needed to evaluate a query. Experimental results indicate that TwigX-Guide can process twig queries on an average 38% better than the TwigStack algorithm, 30% better than TwigINLAB, 10% better than TwigStackList and about 5% better than TwigStackXB in terms of execution time. <s> BIB002
While a DataGuide can efficiently answer queries with PC edges (by matching the query path against the label path directly), it cannot process queries with AD edges nor twig queries, because it does not preserve hierarchical relationships BIB002 . Combining a DataGuide with a labeling scheme that captures AD relationships allows the reconstruction, for any node x in a data tree t, of the specific path instance x belongs to. Thus, in the computing phase, node labels can be compared without accessing labels related to inner TP nodes  . For instance, TwigX-Guide combines a DataGuide to the region encoding labeling scheme BIB002 . Version Tree is an annotated DataGuide in which labels include a version number for nodes of the same type (e.g., all book nodes) BIB001 . Combined to the Dewey ID labeling scheme, it supports a matching algorithm called TwigVersion. Finally, QueryGuide labels DataGuide nodes with Dewey ID lists and is part of the S 3 matching method  . All three approaches have been experimentally shown to perform matching faster than previous holistic algorithm such as TwigStack and TJFast.