Abstract: As an important variant of Skyline query, reverse Skyline query over uncertain data streams has become a hot topic recently. However, existing standalone algorithm can’t cope with data streams with highspeed, high data dimensions, large sliding 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.

Key words: reverse Skyline query, uncertain data streams, parallel processing, dispatch strategy