Fast ELCA computation for keyword queries on XML data
Fast ELCA computation for keyword queries on XML data
复制标题
DOI：
10.1145/1739041.1739107
复制
发表时间：
2010-03
期刊：
影响因子：
--
通讯作者：
Rui Zhou;Chengfei Liu;Jianxin Li
中科院分区：
文献类型：
--
作者：
Rui Zhou;Chengfei Liu;Jianxin Li
关键词搜索由于便于传达用户的查询意图而被集成到许多应用程序中。最近，回答XML数据的关键字查询引起了web和数据库社区的关注，因为这项研究的成功将使用户从学习复杂的XML查询语言（如XPath/XQuery）和/或了解所查询XML数据的底层模式中解脱出来。因此，可以更容易地发现XML数据中的信息。为了对XML数据上回答关键字查询的结果进行建模，提出了许多基于LCA（最低共同祖先）的概念。本文主要研究ELCA （Exclusive LCA）语义，该语义最早由Guo等人提出，后来由Xu和Papakonstantinou命名。我们提出了一种名为哈希计数的算法来有效地找到elca。我们的分析表明，Hash Count算法的复杂度为0 (kd|S1|)，其中k为关键字的个数，d为所查询XML文档的深度，|S1|为最稀有关键字出现的频率。这种复杂性是目前已知的最好结果。我们还在真实的DBLP数据集上评估了该算法，并将其与最先进的算法进行了比较。实验结果证明了哈希计数算法在实际应用中的优越性。
Keyword search is integrated in many applications on account of the convenience to convey users' query intention. Recently, answering keyword queries on XML data has drawn the attention of web and database communities, because the success of this research will relieve users from learning complex XML query languages, such as XPath/XQuery, and/or knowing the underlying schema of the queried XML data. As a result, information in XML data can be discovered much easier. To model the result of answering keyword queries on XML data, many LCA (lowest common ancestor) based notions have been proposed. In this paper, we focus on ELCA (Exclusive LCA) semantics, which is first proposed by Guo et al. and afterwards named by Xu and Papakonstantinou. We propose an algorithm named Hash Count to find ELCAs efficiently. Our analysis shows the complexity of Hash Count algorithm is O(kd|S1|), where k is the number of keywords, d is the depth of the queried XML document and |S1| is the frequency of the rarest keyword. This complexity is the best result known so far. We also evaluate the algorithm on a real DBLP dataset, and compare it with the state-of-the-art algorithms. The experimental results demonstrate the advantage of Hash Count algorithm in practice.