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

Approximate Skyline Query Processing Algorithms over Uncertain Contexts

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

In recent years skyline query is an important aspect for queries on uncertain data.Skyline queries are usually associated with users＇ preferences and the preferences are depend on users＇ current contexts.For most contexts are from sensing devices,uncertainty is along with users＇ contexts.In this paper,approximate skyline query processing algorithms over uncertain contexts based on heuristic methods and M onte Carlo sampling mechanisms are proposed for the first time.First,possible world semantics model is utilized to model uncertain contexts as well as uncertain contextual preferences,and skyline query semantics based on uncertain contexts are provided.After that,for exact skyline algorithm is a #P-hard problem,two heuristic skyline algorithms,LHSA and CT,are proposed to reduce the number of possible world instances not contributing to final skyline query results.To improve the efficiency of skyline query processing under user specified precision,two-phase M onte Carlo approximate algorithm PM A and improved two-phase M onte Carlo approximate algorithm M PM A are proposed.Finally,extensive experimental results showthat LHSA and CT algorithms can reduce the number of possible world instances to a large extent and the proposed PM A and M PM A algorithms perform more efficiently than heuristic algorithms while M PM A algorithm is prior to PM A.