Fast Result Enumeration for Keyword Queries on XML Data
Fast Result Enumeration for Keyword Queries on XML Data
复制标题
DOI：
10.5626/jcse.2012.6.2.127
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
Junfeng Zhou;Ziyang Chen;Xian Tang;Z. Bao;T. Ling
中科院分区：
文献类型：
--
作者：
Junfeng Zhou;Ziyang Chen;Xian Tang;Z. Bao;T. Ling
在本文中，我们重点关注基于SLCA语义的XML数据关键字查询的最紧密匹配子树（TMSubtree）结果的高效构建，其中“匹配”意味着返回子树中的所有节点满足以下约束：以每个节点为根的子树的不同关键字集不被其任何兄弟节点的子树所包含，而“最紧密”意味着以两个兄弟节点为根的两个子树不能包含相同的关键字集。假设d是给定TMSubtree的深度，m是给定查询Q的关键字数量，我们证明如果d≤m，则匹配的子树结果最多有2m！节点；否则，匹配子树结果的大小以 (d−m+2)m! 为界。基于这一理论结果，我们提出了一种流水线算法来构造 TMSubtree 结果，而无需重新扫描所有节点标签。实验验证了我们的算法在帮助 XML 数据上进行关键字搜索方面的优势。
In this paper, we focus on efficient construction of tightest matched subtree (TMSubtree) results for keyword queries on XML data based on SLCA semantics, where "matched" means that all nodes in a returned subtree satisfy the constraint that the set of distinct keywords of the subtree rooted at each node is not subsumed by that of any of its sibling node, while "tightest" means that no two subtrees rooted at two sibling nodes can contain the same set of keywords. Assume that d is the depth of a given TMSubtree, m is the number of keywords of a given query Q, we proved that if d≤m, a matched subtree result has at most 2m! nodes; otherwise, the size of a matched subtree result is bounded by (d−m+2)m!. Based on this theoretical result, we propose a pipelined algorithm to construct TMSubtree results without rescanning all node labels. Experiments verify the benefits of our algorithm in aiding keyword search over XML data.