高效的连续不确定XML数据Top-k查询算法  

An efficient algorithm of top-k inquires over continuous uncertain XML

作　　者：张晓琳[1] 郑春红[1] 刘立新[1] 吕庆[1] 

机构地区：[1]内蒙古科技大学信息工程学院,内蒙古包头014010

出　　处：《计算机工程与科学》2014年第6期1101-1107,共7页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(61163015);内蒙古自然科学基金资助项目(20080404Zd21)

摘　　要：目前,不确定XML数据的top-k查询算法中都没有处理连续不确定数据,本文提出SPCProTJFast算法,该算法改进了传统的归并算法,并结合连续不确定数据的过滤方法,实现了连续不确定XML的Top-k查询。为了避免概率下限值过小对过滤效果的影响,又提出HPCProTJFast算法,该算法推迟了对连续节点的处理,只有在获得满足概率条件的整枝路径时才对连续节点进行访问。实验表明,在执行时间以及过滤效率上,同直接处理连续不确定数据的ProTJFast算法相比,这两种算法都要更高效,并且HPCProTJFast算法的效率更高。Currently,the top k query algorithms about the uncertain XML data can not deal with continuous uncertain data.The SPCProTJFast algorithm is proposed,which improves the traditional merging algorithm,combines with continuous uncertain data filtering methods,implements the top-k query algorithm over continuous uncertain XML data.In order to avoid the impact of too small probability limit on filtering effect,the HPCProTJFast algorithm is proposed,which delays the handling of continuous types of nodes and visits the continuous nodes only when the entire twig that meets the probability condition are acquired.Experimental results show that,in terms of the execution time and the filtration efficiency,these two algorithms are more efficient than the ProTJFast algorithm that deals with continuous uncertain data directly,and the HPCProTJFast algorithm is the most efficient.

关 键 词：连续不确定 XML 归并 TOP-K 

分 类 号：TP392[自动化与计算机技术—计算机应用技术]