ITwigStack: An improved algorithm of XML twig pattern matching
Shi Jun-feng, Ning Pang · 2011
Finding all occurrences of a twig pattern in an XML database is a core operation for XML query algorithm. Prior work has called the function getNext(q) [1] or other functions based on the getNext function to find matching nodes. There are some useless call or return operations because returning the unmatched node to the upper procedure is useless and the call operation is may be useless after moving the cursor of the unmatched node one by one without considering whether the next element is a matching node. To solve this problem, we propose an algorithm named ITwigStack, which calls a function named IgetNext to find matching nodes. The function moves the cursor and continues to find matching nodes when it visits an unmatched node, which avoids useless return operations. And the main procedure uses the function moveCursor to move the cursor of the unmatched element, which uses a look-ahead approach to avoid the useless call of IgetNext. While it can be shown analytically that the proposed algorithm is as efficient as the existing state-of-the-art algorithms in terms of worst case I/O and CPU cost, experimental results on various datasets indicate that the proposed algorithm performs significantly better than the existing ones, especially when there are more unmatched nodes in XML tree.