不确定数据流上的并行反 Skyline 查询

摘要

作为Skyline查询的一种重要变体，不确定数据流上的反Skyline查询已经成为研究的热点。已有的单机算法无法应对诸如高速数据流、高数据维度、大滑动窗口等情况，相应提出并行查询处理算法PRSUDS。算法采用基于角度划分的分发策略将处理任务分发至各并行节点，给出该分发策略的正确性证明，进而设计、实现算法的并行处理框架。实验结果表明PRSUDS算法较单机算法具有更好的综合性能，更能满足数据流查询的实时性要求。%As an important variant of Skyline query , reverse Skyline query over uncertain data streams has become a hot topic re-cently.However, existing stand-alone algorithm can’t cope with data streams with high-speed, high data dimensions, large slid-ing windows, etc.A novel parallel processing algorithm named PRSUDS is proposed .PRSUDS adopts angle-partitioning-based dispatch strategy to assign processing tasks to peer nodes;the correctness of the dispatch strategy is presented .Then the design and implementation of parallel processing framework are presented .Results of massive experiments show that PRSUDS has better overall performance compared to existing algorithms .