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

《高效的连续不确定XML数据Top-k查询算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、CN43—1258／TP计算机工程与科学第36卷第6期2014年6月ISSN1007—130XComputerEngineering&ScienceV01．36，No．6，Jun．2014文章编号：1007—130X(2014)06—1101—07高效的连续不确定XML数据Top—k查询算法张晓琳，郑春红，刘立新，吕庆(内蒙古科技大学信息工程学院，内蒙古包头014010)摘要：目前，不确定xML数据的top—k查询算法中都没有处理连续不确定数据，本文提出SPCPro—TJFast算法，该算法改进了传统的归并算

2、法，并结合连续不确定数据的过滤方法，实现了连续不确定XML的Top—k查询。为了避免概率下限值过小对过滤效果的影响，又提出HPCProTJFast算法，该算法推迟了对连续节点的处理，只有在获得满足概率条件的整枝路径时才对连续节点进行访问。实验表明，在执行时间以及过滤效率上，同直接处理连续不确定数据的ProTJFast算法相比，这两种算法都要更高效，并且HPCProTJFast算法的效率更高。关键词：连续不确定；XML；归并；top—k中图分类号：TP392文献标志码：Adoi：10．3969／j．issn．1

3、007—130X．2014．06．017Anefficientalgorithmoftop一inquiresovercontinuousuncertainXMLZHANGXiao-lin，ZHENGChun—hong，LIULi—xin，LUQing(SchoolofInformationEngineering，InnerMongoliaUniversityofScienceandTechnology，Baotou014010，China)Abstract：Currently，thetop一志queryalg

4、orithmsabouttheuncertainXMLdatacannotdealwithcontinuousuncertaindata．TheSPCProTJFastalgorithmisproposed，whichimprovesthetraditionalmergingalgorithm，combineswithcontinuousuncertaindatafilteringmethods，implementsthetop—kqueryalgorithmovercontinuousuncertainXM

5、Ldata．Inordertoavoidtheimpactoftoosmallprobabil—itylimitonfilteringeffect，theHPCProTJFastalgorithmisproposed，whichdelaysthehandlingofcon—tinuoustypesofnodesandvisitsthecontinuousnodesonlywhentheentiretwigthatmeetstheprobabil—ityconditionareacquired．Experime

6、ntalresultsshowthat，intermsoftheexecutiontimeandthefiltra—tionefficiency，thesetwoalgorithmsaremoreefficientthantheProTJFastalgorithmthatdealswithcontinuousuncertaindatadirectly，andtheHPCProTJFastalgorithmiSthemostefficient．Keywords：continuousuncertain；XML；m

7、erge；top—k(PxML)是近年来研究者们提出的一种新的不确引言定数据表示方法，PXML的查询处理技术已经成为研究的热点。由于对PXML文档查询的结果是目前，在很多实际应用当中数据的不确定性是附带概率值的，而用户通常希望得到k个概率值最普遍存在的，例如传感器网络系统、信息抽取与数大的结果，因此，如何实现PXML高效的top—k查据整合系统以及科学数据管理系统等。概率XML询处理成为学者们广泛关注的话题。2011年，Li*收垂稿金日期：2012-u一13；修回日期：2013-04—10项目：国家自然科学基

8、金资助项目(61163015)；内蒙古自然科学基金资助项目(20080404Zd21)通信地：o110内蒙古包头市内蒙古科大学信息工程学院Address：SchoolofInformationEngineering，InnerMongoliaUniversityOfScienceandTlechnology，Baotou014010，’一Inner—M—ongo-li-a，’11O2Computer