Abstract: Skyline query processing over uncertain data streams has attracted considerable attention recently. The traditional centralized stream processing algorithms can hardly process Skyline query of massive data. On the other side, cloud computing provides great opportunities for distributed and parallel Skyline query processing with its massive computing resources and effective storage management manners. Motivated by the above facts, this paper proposes a parallel Skyline over uncertain data streams algorithm (PSUDS) by partitioning the sliding window. This algorithm is able to parallelize the Skyline processing over uncertain data streams to solve the performance problems within the traditional centralized stream processing algorithms. Massive experiments demonstrate that the proposed algorithm has good parallel scalability.

Key words: uncertain data, data stream, Skyline, sliding window, parallel query, cloud computing

摘要： 不确定数据流上的Skyline查询技术逐步引起研究者的关注，传统的集中式流处理算法难以满足海量数据的查询需求，并且云计算所提供的海量计算资源和有效的存储管理模式，为研究并行Skyline查询技术提供了充足的条件。基于上述事实，提出了一种不确定数据流上的并行Skyline查询算法（parallel Skyline over uncertain data streams，PSUDS）。该算法通过交叉划分滑动窗口的方式，将集中式流查询转化为并行处理，以并行执行的方式来解决集中式算法处理性能不足的问题。大量实验结果表明，该算法具有较好的并行可扩展性。

关键词: 不确定数据, 数据流, Skyline, 滑动窗口, 并行查询, 云计算