Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41414
Title: From region encoding to extended dewey: On efficient processing of XML twig pattern matching
Authors: Lu, J.
Ling, T.W. 
Chan, C.-Y. 
Chen, T. 
Issue Date: 2005
Source: Lu, J.,Ling, T.W.,Chan, C.-Y.,Chen, T. (2005). From region encoding to extended dewey: On efficient processing of XML twig pattern matching. VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases 1 : 193-204. ScholarBank@NUS Repository.
Abstract: Finding all the occurrences of a twig pattern in an XML database is a core operation for efficient evaluation of XML queries. A number of algorithms have been proposed to process a twig query based on region encoding labeling scheme. While region encoding supports efficient determination of structural relationship between two elements, we observe that the information within a single label is very limited. In this paper, we propose a new labeling scheme, called extended Dewey. This is a powerful labeling scheme, since from the label of an element alone, we can derive all the elements names along the path from the root to the element. Based on extended Dewey, we design a novel holistic twig join algorithm, called TJFast. Unlike all previous algorithms based on region encoding, to answer a twig query, TJFast only needs to access the labels of the leaf query nodes. Through this, not only do we reduce disk access, but we also support the efficient evaluation of queries with wildcards in branching nodes, which is very difficult to be answered by algorithms based on region encoding. Finally, we report our experimental results to show that our algorithms are superior to previous approaches in terms of the number of elements scanned, the size of intermediate results and query performance.
Source Title: VLDB 2005 - Proceedings of 31st International Conference on Very Large Data Bases
URI: http://scholarbank.nus.edu.sg/handle/10635/41414
ISBN: 1595931546
Appears in Collections:Staff Publications

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

Page view(s)

65
checked on Jan 13, 2018

Google ScholarTM

Check


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