A new efficient algorithm: CacheTwig for XML twig queries

As the use of XML getting extensive, there is a popular research topic about how to find ours interested information in the XML database under a certain twig pattern. BrunoN proposed the concept of holistic twig in 2002 and brought up the algorithm of TwigStack. When processing the search which only contains ancestor-descendant relationships, this algorithm is the most superior. However, when the search contains parent-child relationships, there will come out with massive intermediate results. Trying to work out this problem, we will propose a improved twig pattern matching - cacheTwig, which is based on output detention theory. The experimental result indicates that our algorithm is not only the most superior for the queries that contains the ancestor-descendant relationships below branching nodes, and when comparing with the present algorithm, it is also highly effective when processing parent-child relationships below branching nodes.