Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/40668
Title: Efficient processing of XML twig patterns with parent child edges: A look-ahead approach
Authors: Lu, J.
Chen, T. 
Ling, T.W. 
Keywords: Holistic twig pattern matching
XML
Issue Date: 2004
Source: Lu, J.,Chen, T.,Ling, T.W. (2004). Efficient processing of XML twig patterns with parent child edges: A look-ahead approach. International Conference on Information and Knowledge Management, Proceedings : 533-542. ScholarBank@NUS Repository.
Abstract: With the growing importance of semi-structure data in information exchange, much research has been done to provide an effective mechanism to match a twig query in an XML database. A number of algorithms have been proposed recently to process a twig query holistically. Those algorithms are quite efficient for quires with only ancestor-descendant edges. But for queries with mixed ancestor-descendant and parent-child edges, the previous approaches still may produce large intermediate results, even when the input and output size are more manageable. To overcome this limitation, in this paper, we propose a novel holistic twig join algorithm, namely TwigStackList. Our main technique is to look-ahead read some elements in input data steams and cache limited number of them to lists in the main memory. The number of elements in any list is bounded by the length of the longest path in the XML document. We show that TwigStackList is I/O optimal for queries with only ancestor-descendant relationships below branching nodes. Further, even when queries contain parent-child relationship below branching nodes, the set of intermediate results in TwigStackList is guaranteed to be a subset of that in previous algorithms. We complement our experimental results on a range of real and synthetic data to show the significant superiority of TwigStackList over previous algorithms for queries with parent-child relationships. Copyright 2004 ACM.
Source Title: International Conference on Information and Knowledge Management, Proceedings
URI: http://scholarbank.nus.edu.sg/handle/10635/40668
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

61
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.