Efficient subtree results computation for XML keyword queries  

作　　者：Ziyang CHEN 

机构地区：[1]School of Information Science and Engineering, Yanshan University, Hebei 066004, China [2]Environmental Management College of China, Hebei 066004, China [3]The Key Laboratory for Computer Virtual Technology and System Integration of HeBei Province, Yanshan University, Hebei 066004, China

出　　处：《Frontiers of Computer Science》2015年第2期253-264,共12页中国计算机科学前沿（英文版）

基　　金：This work was partially supported by the National Natural Science Foundation of China （Grant Nos. 61272124, 61103139, 61472339 and 61303040）.

摘　　要：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.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.

关 键 词：XML SLCA/ELCA RSubtree RKNs PARALLEL 

分 类 号：TP311.131[自动化与计算机技术—计算机软件与理论] TP334.2[自动化与计算机技术—计算机科学与技术]