Efficient LCA based keyword search in xml data
Efficient LCA based keyword search in xml data
复制标题
DOI：
10.1145/1321440.1321597
复制
发表时间：
2007-11
期刊：
影响因子：
--
通讯作者：
Yu Xu;Y. Papakonstantinou
中科院分区：
文献类型：
--
作者：
Yu Xu;Y. Papakonstantinou
基于最低共同祖先（LCAs）及其修改概念的XML文档中的关键字搜索最近引起了研究兴趣[2，3，4]。在本文中，我们提出了一个高效的算法，称为索引堆栈，以找到答案的关键字查询的基础上XRank的语义LCA [2]。索引栈算法的复杂度为O（kd| S1|\log| S|其中k是查询中关键字的数量，d是树的深度，|S1| (|S|）是查询中出现频率最低（最高）的关键字。相比之下，[2]中的核心算法的最佳最差情况复杂度为O（kd| S|).我们分析和实验评估索引堆栈算法和[2]中的两个核心算法。结果表明，当查询中包含至少一个低频关键字沿着高频关键字时，索引栈算法在CPU和I/O开销方面均优于其他算法几个数量级。
Keyword search in XML documents based on the notion of lowest common ancestors (LCAs) and modifications of it has recently gained research interest [2, 3, 4]. In this paper we propose an efficient algorithm called Indexed Stack to find answers to keyword queries based on XRank's semantics to LCA [2]. The complexity of the Indexed Stack algorithm is O(kd|S1|\log|S|) where k is the number of keywords in the query, d is the depth of the tree and |S1 | (|S|) is the occurrence of the least (most) frequent keyword in the query. In comparison, the best worst case complexity of the core algorithms in [2] is O(kd|S|). We analytically and experimentally evaluate the Indexed Stack algorithm and the two core algorithms in [2]. The results show that the Indexed Stack algorithm outperforms in terms of both CPU and I/O costs other algorithms by orders of magnitude when the query contains at least one low frequency keyword along with high frequency keywords.