Please use this identifier to cite or link to this item:
https://doi.org/10.1109/TKDE.2010.126
DC Field | Value | |
---|---|---|
dc.title | Extended XML tree pattern matching: Theories and algorithms | |
dc.contributor.author | Lu, J. | |
dc.contributor.author | Ling, T.W. | |
dc.contributor.author | Bao, Z. | |
dc.contributor.author | Wang, C. | |
dc.date.accessioned | 2013-07-04T07:39:14Z | |
dc.date.available | 2013-07-04T07:39:14Z | |
dc.date.issued | 2011 | |
dc.identifier.citation | Lu, J., Ling, T.W., Bao, Z., Wang, C. (2011). Extended XML tree pattern matching: Theories and algorithms. IEEE Transactions on Knowledge and Data Engineering 23 (3) : 402-416. ScholarBank@NUS Repository. https://doi.org/10.1109/TKDE.2010.126 | |
dc.identifier.issn | 10414347 | |
dc.identifier.uri | http://scholarbank.nus.edu.sg/handle/10635/39331 | |
dc.description.abstract | As business and enterprises generate and exchange XML data more often, there is an increasing need for efficient processing of queries on XML data. Searching for the occurrences of a tree pattern query in an XML database is a core operation in XML query processing. Prior works demonstrate that holistic twig pattern matching algorithm is an efficient technique to answer an XML tree pattern with parent-child (P-C) and ancestor-descendant (A-D) relationships, as it can effectively control the size of intermediate results during query processing. However, XML query languages (e.g., XPath and XQuery) define more axes and functions such as negation function, order-based axis, and wildcards. In this paper, we research a large set of XML tree pattern, called extended XML tree pattern, which may include P-C, A-D relationships, negation functions, wildcards, and order restriction. We establish a theoretical framework about "matching cross" which demonstrates the intrinsic reason in the proof of optimality on holistic algorithms. Based on our theorems, we propose a set of novel algorithms to efficiently process three categories of extended XML tree patterns. A set of experimental results on both real-life and synthetic data sets demonstrate the effectiveness and efficiency of our proposed theories and algorithms. © 2006 IEEE. | |
dc.description.uri | http://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1109/TKDE.2010.126 | |
dc.source | Scopus | |
dc.subject | algorithms | |
dc.subject | Query processing | |
dc.subject | tree pattern | |
dc.subject | XML/XSL/RDF | |
dc.type | Article | |
dc.contributor.department | COMPUTER SCIENCE | |
dc.description.doi | 10.1109/TKDE.2010.126 | |
dc.description.sourcetitle | IEEE Transactions on Knowledge and Data Engineering | |
dc.description.volume | 23 | |
dc.description.issue | 3 | |
dc.description.page | 402-416 | |
dc.description.coden | ITKEE | |
dc.identifier.isiut | 000286207900007 | |
Appears in Collections: | Staff Publications |
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.