TwigList: Make twig pattern matching fast
- Publication Type:
- Journal Article
- Citation:
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2007, 4443 LNCS pp. 850 - 862
- Issue Date:
- 2007-01-01
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2013002369OK.pdf | 498.32 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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, Twig2 Stack was proposed to overcome this problem using hierarchical-stacks to further reduce the merging cost. But, due to the complex hierarchical-stacks Twig2 Stack used, Twig2 Stack 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. © Springer-Verlag Berlin Heidelberg 2007.
Please use this identifier to cite or link to this item: