From region encoding to extended Dewey: on efficient processing of XML twig pattern matching

dc.contributor.authorLU, Jiahengen_US
dc.contributor.authorLING, Tok Wangen_US
dc.contributor.authorCHAN, Chee-Yongen_US
dc.contributor.authorCHEN, Tingen_US
dc.date.accessioned2005-07-04T09:27:43Zen_US
dc.date.accessioned2017-01-23T06:59:35Z
dc.date.available2005-07-04T09:27:43Zen_US
dc.date.available2017-01-23T06:59:35Z
dc.date.issued2005-07-04T09:27:43Zen_US
dc.description.abstractFinding 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 ancestor-descendant (or parent-child) 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.en_US
dc.format.extent376224 bytesen_US
dc.format.extent376224 bytesen_US
dc.format.mimetypeapplication/pdfen_US
dc.format.mimetypeapplication/pdfen_US
dc.identifier.urihttps://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1814en_US
dc.language.isoenen_US
dc.relation.ispartofseriesTRA6/05en_US
dc.titleFrom region encoding to extended Dewey: on efficient processing of XML twig pattern matchingen_US
dc.typeTechnical Reporten_US
Files
Original bundle
Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
TRA6-05.pdf
Size:
367.41 KB
Format:
Adobe Portable Document Format
Description:
Loading...
Thumbnail Image
Name:
1_TRA6-05.pdf
Size:
367.41 KB
Format:
Adobe Portable Document Format
Description:
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.53 KB
Format:
Plain Text
Description: