Abstract: The parallel Skyline query over probabilistic data streams,as an important aspect of big data analysis,plays an important role in various applications.To deal with the problem that the query results may be incorrect and interrupted,due to various faults occurred in the process of parallel Skyline queries over probabilistic streams,a replication-based fault-tolerant distributed parallel Skyline query scheme named REPS was proposed.Specifically,the compute nodes are also regarded as the replication nodes,and a layer-alternation strategy for replica placement is proposed in REPS.Thus,the lost data can be recovered efficiently by selecting the replicas with high priority.Moreover,the processes of fault detection,data recovery and query recovery are throughout the whole query updating process,in order to reduce the communication and computation overhead and achieve rapid fault-tolerant parallel query processing.Extensive experimental results demonstrate that REPS method not only has high efficiency when no failure occurs or a single node fails,but also can maintain a high processing rate and meet the query requirement even when multiple failures occur.

Key words: Probabilistic Skyline,Fault-tolerant queries,Data streams,Parallel queries,Big data