Twig Pattern Matching: A Revisit

Publication Type:
Conference Proceeding
Lecture Notes in Computer Science, LNCS 6861, 2011, pp. 43 - 50
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2011001180OK.pdf2.33 MB
Adobe PDF
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.
Please use this identifier to cite or link to this item: