基于状态空间搜索的不确定轮廓查询算法  

An Uncertain Skyline Query Algorithm Based on State Space Searching

作　　者：信俊昌[1] 黄健美[1] 王国仁[1] 公丕臻[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2010年第3期338-341,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(60773221;60773219);国家高技术研究发展计划项目(2006AA09Z139;2007AA01Z192;2009AA01Z150);中央高校基本科研业务专项资金资助项目(N090304007)

摘　　要：针对阈值轮廓查询忽略了轮廓的整体性,只考虑单个对象成为轮廓中对象的现象,深入地研究了不确定数据库中的轮廓查询处理技术.首先,提出了将对象集合作为整体考虑其轮廓概率的不确定轮廓查询的定义;其次,通过对其性质的分析,提出了基于状态空间搜索的基本的不确定轮廓算法(BUS);接着,通过进一步分析,在BUS算法的基础上,增加了有效的过滤策略,提出了改进的不确定轮廓算法(IUS).实验结果表明,加入了改进策略的IUS算法明显优于BUS算法,验证了改进策略的有效性.The skyline query processing technique about an uncertain databases is discussed in depth because only a single object is considered as the constitution of skyline with the integrality ignored in the threshold query of the whole skyline.A new concept of uncertain skyline query is therefore redefined gathering all the skyline objects as a whole in view of probability.A state space searching based on BUS（basic uncertain skyline）query algorithm is proposed after analyzing its properties.Then,a novel algorithm IUS（improved uncertain skyline）is given through efficient filtering strategy to improve BUS.Experimental results showed that the performance of IUS is obviously superior to BUS,thus verifying the effectiveness of improving strategy.

关 键 词：不确定性 轮廓 存在概率 状态空间 可能世界 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]