Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-29038-1_14
Title: Top-down SLCA computation based on list partition
Authors: Zhou, J.
Bao, Z.
Chen, Z.
Lan, G.
Lin, X.
Ling, T.W. 
Issue Date: 2012
Source: Zhou, J.,Bao, Z.,Chen, Z.,Lan, G.,Lin, X.,Ling, T.W. (2012). Top-down SLCA computation based on list partition. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 7238 LNCS (PART 1) : 172-184. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-29038-1_14
Abstract: In this paper, we focus on efficient processing of a given XML keyword query based on SLCA semantics. We propose an efficient algorithm that processes all nodes in the set of inverted Dewey label lists in a top-down way. Specifically, our method recursively divides the set of initial Dewey label lists into a set of minimum nontrivial blocks (MNBlocks), where a block consists of a set of Dewey label lists and corresponds to an XML tree. The "minimum" means that for a given block, none of its sub-blocks corresponds to a subtree that contains all keywords of the given query; the "nontrivial" means that no block can contain an empty list. Based on these MNBlocks, our method produces all qualified results by directly outputting the LCA node of all nodes in each MNBlock as a qualified SLCA node. During processing, our method can intelligently prune useless keyword nodes according to the distribution of all nodes in a given block. Our experimental results verify the performance advantages of our method according to various evaluation metrics. © 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/41795
ISBN: 9783642290374
ISSN: 03029743
DOI: 10.1007/978-3-642-29038-1_14
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

3
checked on Jan 17, 2018

Page view(s)

64
checked on Jan 14, 2018

Google ScholarTM

Check

Altmetric


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