Efficient Processing of XML Pattern Matching: A String Matching-based Approach
| dc.contributor.author | Jiaheng LU | en_US |
| dc.contributor.author | Tok Wang LING | en_US |
| dc.date.accessioned | 2004-10-21T14:28:52Z | en_US |
| dc.date.accessioned | 2017-01-23T06:59:46Z | |
| dc.date.available | 2004-10-21T14:28:52Z | en_US |
| dc.date.available | 2017-01-23T06:59:46Z | |
| dc.date.issued | 2004-02-01T00:00:00Z | en_US |
| dc.description.abstract | In this paper, we propose a new approach of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database is labeled with a variation of Dewey ID labeling scheme, namely Extended Dewey ID. The unique feature of this labeling scheme is that from the label of an element alone, we can use finite state transducers (FST) to derive the names of elements along the path from the root to this element. This feature enables us to directly reduce XML path pattern matching into string matching. We then develop a holistic twig join algorithm, called TwigComPath. The algorithm is quite different from the previous strategies in that it solves XML pattern matching problem by string matching and comparing instead of binary relationship matching and stitching. Furthermore, our algorithm only needs to visit the labels of elements that satisfy the leaf node predicates in a twig (or path) pattern; hence, it has performance advantages over the methods that need to visit the labels of all nodes in the pattern. Finally, we provide experimental results to demonstrate the perform-ance benefits of our proposed approaches. | en_US |
| dc.format.extent | 779398 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1442 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TRA2/04 | en_US |
| dc.title | Efficient Processing of XML Pattern Matching: A String Matching-based Approach | en_US |
| dc.type | Technical Report | en_US |