TwigList - Make Twig Pattern Matching Fast

Springer Verlag
Publication Type:
Journal Article
Lecture Notes in Computer Science, 2007, DSAA, 4443 (1), pp. 850 - 862
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002369OK.pdf498.32 kB
Adobe PDF
Twig pattern matching problem has been widely studied in recent years. Give an XML tree t. A twig-pattern matching query, Q, represented as a query tree, is to find all the occurrences of such twig pattern in t. Previous works like HolisticTwig and TJFast decomposed the twig pattern into single paths from root to leaves, and merged all the occurrences of such path-patterns to find the occurrences of the twig-pattern matching query, Q. Their techniques can effectively prune impossible path-patterns to avoid producing a large amount of intermediate results. But they still need to merge path-patterns which occurs high computational cost. Recently, Twig2Stack was proposed to overcome this problem using hierarchical-stacks to further reduce the merging cost. But, due to the complex hierarchical-stacks Twig2Stack used, Twig2Stack may end up many random accesses in memory, and need to load the whole XML tree into memory in the worst case. In this paper, we propose a new algorithm, called TwigList, which uses simple lists. Both time and space complexity of our algorithm are linear with respect to the total number of pattern occurrences and the size of XML tree. In addition, our algorithm can be easily modified as an external algorithm. We conducted extensive experimental studies using large benchmark and real datasets. Our algorithm significantly outperforms the up-to-date algorithm.
Please use this identifier to cite or link to this item: