Existing keyword search algorithms over uncertain XML need to traverse the uncertain XML document and the algorithms need to compare strings frequently when executing,this leads to a waste of time.To solve this problem,we propose an extended inverted index-based keyword search algorithm named PrE for uncertain XML.The extended inverted index effectively store the related information of uncertain XML nodes,and the dynamic hash table and the number coding list can be initialised easily according to the extended inverted index.During the execution the PrE uses integer comparison instead of the string comparison.Theoretical analysis and experiment results all show that the PrE is an efficient XML keyword search algorithm.%现有的不确定XML关键字查询算法均需遍历不确定XML文档,并且算法在执行过程中需要频繁的字符串比较,造成时间浪费。针对上述问题,提出基于扩展倒排索引的不确定XML关键字查询算法PrE。扩展倒排索引有效地存储了不确定XML文档中节点的相关信息,根据扩展倒排索引即可初始化动态哈希表和序号编码链表,并且PrE算法在执行过程中利用整数的比较代替了字符串的比较。理论分析与实验结果表明,PrE算法是一种高效的不确定XML关键字查询算法。
展开▼