杨艳艳，赵 雷，杨季文

(苏州大学计算机科学与技术学院，江苏 苏州 215006)

1 概述

轮廓(skyline)查询返回所有不被支配的对象的集合，它在多条件决策、用户偏好分析等系统中具有重要的意义。随着数据采集和处理技术的不断进步，人们对数据不确定性的认识也逐步的深入，skyline查询应用场景被进一步扩展以支持不确定数据的分析与挖掘，针对不确定数据的概率 skyline查询近几年得到了学者们的广泛关注。

与传统意义上的skyline查询不同，在不确定数据中，对象以一个概率存在，对象能否成为skyline查询结果，不仅取决于对象本身的信息，还与对象存在的概率紧密相关。而且，在现实生活中，不同的用户可能有不同的兴趣和偏好，往往需要在不同的子空间上处理skyline查询。因此，研究不确定数据子空间上的概率skyline查询有着非常重要的现实意义。

本文在连续概率 skyline轮廓查询(Continuous Probabilistic Skyline Query in Subspaces, CPSQS)算法的基础上，提出一种基于网格索引结构的概率skyline查询算法。

2 相关研究

文献[1]将skyline计算引入到数据库领域，提出BNL算法和D&C算法。在数据库领域研究初期，主要针对静态大数据量的 skyline及其变体计算。文献[2]提出 SFS算法，主要思想是先将数据集按照某个单调函数预排序，再通过单边扫描数据集有效计算skyline。文献[3]针对NN算法的不足之处，提出BBS算法并从理论上证明该算法I/O最优。

文献[4]研究基于滑动窗口的连续skyline查询，分别设计出Lazy和Eager2个算法框架。文献[5]提出Subsky算法，采用维度压缩的方案将多维的数据对象压缩成一维的值，利用B树结构对压缩后的结果建立索引，可快速返回任意子空间上的skyline查询结果。……