File(s) under permanent embargo
Top-down SLCA computation based on list partition
conference contribution
posted on 2023-05-23, 08:58 authored by Zhou, J, Bao, Z, Chen, Z, Lan, G, Lin, X, Ling, TKIn 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.
History
Publication title
Database Systems for Advanced Applications Part IEditors
S-G Lee, Z Peng, X Zhou, Y-S Moon, R Unland, J YooPagination
172-184ISBN
978-3-642-29037-4Department/School
School of Information and Communication TechnologyPublisher
Springer-VerlagPlace of publication
Berlin, GermanyEvent title
The 17th International Conference on Database Systems for Advanced Applications 2013Event Venue
Busan, South KoreaDate of Event (Start Date)
2012-04-15Date of Event (End Date)
2012-04-18Rights statement
Copyright 2012 SpringerRepository Status
- Restricted