不确定场境下近似Skyline查询处理算法

摘要：

近年来,不确定Skyline查询成为当前不确定数据查询研究的一个重要方面.Skyline查询结果通常与用户的偏好相关,而用户的偏好往往受当前场境的影响,并且现实中的场境往往来源于感知设备,具有不确定性.首次提出了不确定场境偏好可能世界语义建模下启发式算法和基于Monte Carlo思想的近似Skyline查询算法.首先,采用可能世界语义模型对不确定场境下偏好进行建模,并提出不确定场境下Skyline查询语义;其次,由于不确定场境下偏好构成的可能世界实例过于庞大,精确sky-line算法ESA是#P问题,提出LHSA和C&T两种启发式Skyline算法,从而大量裁减不满足最终结果的可能世界实例;进而,为了在保证用户指定精度的基础上提高Skyline查询效率提出了两种Monte Carlo近似算法:两阶段Monte Carlo近似算法PMA和改进的两阶段Monte Carlo近似算法MPMA;最后,通过实验对比5种算法,表明LHSA和C&T可以裁减大量可能世界实例,同时在确保精度的前提下,PMA和MPMA比启发式算法更有效,并且MPMA算法优于PMA算法.

关键词：Skyline概率、不确定场境、定量偏好、可能世界语义、Monte Carlo近似

所属期刊栏目：37

分类号：TP392(计算技术、计算机技术)

资助基金：江苏省自然科学基金项目BK20140826;中央高校基本科研业务费专项资金项目NS2015095;南京航空航天大学研究生创新基地开放基金项目KFJJ201461

在线出版日期：2016-10-25（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：670-675