Show simple item record

dc.contributor.authorLi, Jiang
dc.contributor.authorWang, Junhu
dc.contributor.editorHaritsa, JR
dc.contributor.editorKotagiri, R
dc.contributor.editorPudi, V
dc.date.accessioned2017-05-03T14:22:25Z
dc.date.available2017-05-03T14:22:25Z
dc.date.issued2008
dc.date.modified2010-08-30T07:02:43Z
dc.identifier.issn0302-9743
dc.identifier.doi10.1007/978-3-540-78568-2_46
dc.identifier.urihttp://hdl.handle.net/10072/26126
dc.description.abstractTwig pattern matching plays a crucial role in XML data processing. TwigStack [2] is a holistic twig join algorithm that solves the problem in two steps: (1) finding potentially useful intermediate path solutions, (2) merging the intermediate solutions. The algorithm is optimal when the twig pattern has only //-edges, in the sense that no useless partial solutions are generated in the first step (thus expediting the second step and boosting the overall performance). However, when /-edges are present, a large set of useless partial solutions may be produced, which directly downgrades the overall performance. Recently, some improved versions of the algorithm (e.g., TwigStackList and iTwigJoin) have been proposed in an attempt to reduce the number of useless partial solutions when /-edges are involved. However, none of the algorithms can avoid useless partial solutions completely. In this paper, we propose a new algorithm, TwigBuffer, that is guaranteed to completely avoid the useless partial solutions. Our algorithm is based on a novel strategy to buffer and manipulate elements in stacks and lists. Experiments show that TwigBuffer significantly outperforms previous algorithms when arbitrary /-edges are present.
dc.description.peerreviewedYes
dc.description.publicationstatusYes
dc.format.extent138386 bytes
dc.format.mimetypeapplication/pdf
dc.languageEnglish
dc.language.isoeng
dc.publisherSpringer
dc.publisher.placeGermany
dc.relation.ispartofstudentpublicationN
dc.relation.ispartofpagefrom554
dc.relation.ispartofpageto561
dc.relation.ispartofjournalLecture Notes in Computer science
dc.relation.ispartofvolume4947
dc.rights.retentionY
dc.subject.fieldofresearchcode280108
dc.titleTwigBuffer: Avoiding Useless Intermediate Solutions Completely in Twig Joins
dc.typeJournal article
dc.type.descriptionC1 - Articles
dc.type.codeC - Journal Articles
gro.facultyGriffith Sciences, School of Information and Communication Technology
gro.rights.copyright© 2008 Springer. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. The original publication is available at www.springerlink.com
gro.date.issued2008
gro.hasfulltextFull Text
gro.griffith.authorWang, John


Files in this item

This item appears in the following Collection(s)

  • Journal articles
    Contains articles published by Griffith authors in scholarly journals.

Show simple item record