Abstract:
Twig pattern matching plays a cruical role in CML query processing. In order to reduce the processing time, some exisiting holistice one-phase twig pattern matching algorithms (e.g., HolisticTwigStack [3], TwigFast [5], etc) use the core function getNext of TwigStack [2] to efectively and efficiently filter out the useless elements. However, using getNext as a filter may incur other redundant computation. We propose two apporaches, namely re-test checking and forward-to-end, which can avoid the redundant computation and can be easily applied to both holistic one-phase and two phase algorithms. The experiments show that our apporach can significantly improve the efficiency by avoiding the redundant computation.
