Efficient query processing for XML keyword queries based on the IDList index
Efficient query processing for XML keyword queries based on the IDList index
复制标题
基于IDList索引的XML关键字查询的高效查询处理
DOI：
10.1007/s00778-013-0313-2
复制
发表时间：
2013-05
期刊：
影响因子：
4.2
通讯作者：
Meng, Xiaofeng
中科院分区：
文献类型：
--
作者：
Zhou, Junfeng;Bao, Zhifeng;Wang, Wei;Zhao, Jinjia;Meng, Xiaofeng
在过去的十年里，基于XML数据的关键字搜索吸引了大量的研究工作，其中一个基本的研究问题是如何有效地回答给定的关键字查询w.r.t.特定的查询语义。我们发现，导致现有方法效率低下的关键因素是它们都严重存在共同的祖先重复问题。在本文中，我们提出了一种新的倒排表形式，即IDList；关键字的IDList由直接或间接包含的有序节点组成。然后，我们证明了基于最小最低公共祖先和排他最低公共祖先语义的关键字查询结果的发现可以归结为有序集相交问题，由于其在信息检索和数据库系统等领域的应用而得到了高度优化。我们提出了几种算法，在不同的方向上利用集合交集，并使用或不使用附加索引。我们进一步提出了几种基于散列搜索的算法来简化从所有涉及的IDList中寻找公共节点的操作。我们使用许多最先进的算法和几个大规模数据集进行了一系列广泛的实验。结果表明，在许多情况下，我们提出的方法比现有方法高出两个数量级。
Keyword search over XML data has attracted a lot of research efforts in the last decade, where one of the fundamental research problems is how to efficiently answer a given keyword query w.r.t. a certain query semantics. We found that the key factor resulting in theinefficiencyfor existing methods is that they all heavily suffer from thecommon-ancestor-repetitionproblem. In this paper, we propose a novel form of inverted list, namely theIDList; the IDList for keywordconsists of ordered nodes that directly or indirectly contain. We then show that finding keyword query results based on the smallest lowest common ancestor and exclusive lowest common ancestor semantics can be reduced to orderedset intersection problem, which has been heavily optimized due to its application in areas such as information retrieval and database systems. We propose several algorithms that exploit set intersection in different directions and with or without using additional indexes. We further propose several algorithms that are based on hash search to simplify the operation of finding common nodes from all involved IDLists. We have conducted an extensive set of experiments using many state-of-the-art algorithms and several large-scale datasets. The results demonstrate that our proposed methods outperform existing methods by up to two orders of magnitude in many cases.