ELCA evaluation for keyword search on probabilistic XML data
ELCA evaluation for keyword search on probabilistic XML data
复制标题
DOI：
10.1007/s11280-012-0166-4
复制
发表时间：
2011-10
期刊：
影响因子：
--
通讯作者：
Rui Zhou;Chengfei Liu;Jianxin Li;J. Yu
中科院分区：
文献类型：
--
作者：
Rui Zhou;Chengfei Liu;Jianxin Li;J. Yu
随着概率数据管理的发展和关键字查询的普及，如何支持概率XML数据的关键字查询成为一个很自然的问题。对于确定性XML文档的关键字查询，ELCA（Exclusive Lowest Common Ancestor）语义允许根在ELCA上的更多相关片段作为结果出现，与其他关键字查询结果语义（如SLCA）相比，ELCA语义更受欢迎。在本文中，我们研究如何评估ELCA结果的关键字查询概率XML文档。在定义概率ELCA语义的可能世界语义，我们提出了一种方法来计算ELCA概率，而不产生可能世界。然后，我们开发了一个有效的基于堆栈的算法，可以找到所有的概率ELCA结果和他们的ELCA概率为一个给定的关键字查询的概率XML文档。最后，我们实验评估所提出的ELCA算法，并比较它与SLCA对应的结果概率，时间和空间效率，和可扩展性方面。
As probabilistic data management is becoming one of the main research focuses and keyword search is turning into a more popular query means, it is natural to think how to support keyword queries on probabilistic XML data. With regards to keyword query on deterministic XML documents, ELCA (Exclusive Lowest Common Ancestor) semantics allows more relevant fragments rooted at the ELCAs to appear as results and is more popular compared with other keyword query result semantics (such as SLCAs). In this paper, we investigate how to evaluate ELCA results for keyword queries on probabilistic XML documents. After defining probabilistic ELCA semantics in terms of possible world semantics, we propose an approach to compute ELCA probabilities without generating possible worlds. Then we develop an efficient stack-based algorithm that can find all probabilistic ELCA results and their ELCA probabilities for a given keyword query on a probabilistic XML document. Finally, we experimentally evaluate the proposed ELCA algorithm and compare it with its SLCA counterpart in aspects of result probability, time and space efficiency, and scalability.