Efficient subtree results computation for XML keyword queries

In this paper, we focus on efficient construction of restricted subtree （RSubtree） results for XML keyword queries on a multicore system. We firstly show that the perfor- mance bottlenecks for existing methods lie in 1） computing the set of relevant keyword nodes （RKNs） for each subtree root node, 2...

Full description

Saved in:
Bibliographic Details
Published in:Frontiers of Computer Science 2015-04, Vol.9 (2), p.253-264
Main Authors: CHEN, Ziyang, LIU, Jia, ZHAO, Xingmin, ZHOU, Junfeng
Format: Article
Language:English
Subjects:
Algorithms
Computer Science
Extensible Markup Language
Keywords
Nodes
parallel
Queries
Research Article
RKNs
RSubtree
Semantics
SLCA/ELCA
XML
关键字查询
子树
并行执行
性能瓶颈
构造算法
节点
计算结果
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we focus on efficient construction of restricted subtree （RSubtree） results for XML keyword queries on a multicore system. We firstly show that the perfor- mance bottlenecks for existing methods lie in 1） computing the set of relevant keyword nodes （RKNs） for each subtree root node, 2） constructing the corresponding RSubtree, and 3） parallel execution. We then propose a two-step generic top-down subtree construction algorithm, which computes SLCA/ELCA nodes in the first step, and parallelly gets RKNs and generates RSubtree results in the second step, where generic means that 1） our method can be used to compute dif- ferent kinds of subtree results, 2） our method is independent of the query semantics; top-down means that our method con- structs each RSubtree by visiting nodes of the subtree con- structed based on an RKN set level-by-level from left to right, such that to avoid visiting as many useless nodes as possible. The experimental results show that our method is much more efficient than existing ones according to various metrics.
ISSN:2095-2228
2095-2236
DOI:10.1007/s11704-014-3473-3