Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-29038-1_9
Title: Fast result enumeration for keyword queries on XML data
Authors: Zhou, J.
Bao, Z.
Chen, Z.
Ling, T.W. 
Issue Date: 2012
Source: Zhou, J.,Bao, Z.,Chen, Z.,Ling, T.W. (2012). Fast result enumeration for keyword queries on XML data. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7238 LNCS (PART 1) : 95-109. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-29038-1_9
Abstract: In this paper, we focus on efficient construction of tightest matched subtree (TMSubtree) results for keyword queries on XML data based on SLCA semantics, where "matched" means that all nodes in a returned subtree satisfy the constraint that the set of distinct keywords of the subtree rooted at each node is not subsumed by that of any of its sibling node, while "tightest" means that no two subtrees rooted at two sibling nodes can contain the same set of keywords. Assume that d is the depth of a given TMSubtree, m is the number of keywords of a given query Q, we proved that if d ≤ m, a matched subtree result has at most 2m! nodes; otherwise, the size of a matched subtree result is bounded by (d - m + 2)m!. Based on this theoretical result, we propose a pipelined algorithm to construct TMSubtree results without rescanning all node labels. Experiments verify the benefits of our algorithm in aiding keyword search over XML data. © 2012 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/40571
ISBN: 9783642290374
ISSN: 03029743
DOI: 10.1007/978-3-642-29038-1_9
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

6
checked on Jan 10, 2018

Page view(s)

59
checked on Jan 19, 2018

Google ScholarTM

Check

Altmetric


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