eCite Digital Repository

Top-down SLCA computation based on list partition


Zhou, J and Bao, Z and Chen, Z and Lan, G and Lin, X and Ling, TK, Top-down SLCA computation based on list partition, Database Systems for Advanced Applications Part I, 15-18 April 2012, Busan, South Korea, pp. 172-184. ISBN 978-3-642-29037-4 (2012) [Refereed Conference Paper]

Copyright Statement

Copyright 2012 Springer

DOI: doi:10.1007/978-3-642-29038-1_14


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.

Item Details

Item Type:Refereed Conference Paper
Keywords:indexing, keyword query
Research Division:Information and Computing Sciences
Research Group:Data management and data science
Research Field:Data management and data science not elsewhere classified
Objective Division:Information and Communication Services
Objective Group:Information systems, technologies and services
Objective Field:Information systems, technologies and services not elsewhere classified
UTAS Author:Bao, Z (Dr Zhifeng Bao)
ID Code:92183
Year Published:2012
Deposited By:Information and Communication Technology
Deposited On:2014-06-09
Last Modified:2015-02-12

Repository Staff Only: item control page