Research On Reverse Skyline Query Over Uncertain Data Stream

Skyline query has important applications in multi-criteria decision making, database visualization, etc. As an important variant of Skyline, reverse Skyline query has important application value too. Data stream with uncertainty exists widely in real world, thus reverse Skyline query over uncertain data stream has significant applications. However, existing algorithm has some deficiencies, the time performance of which is not high enough and can not cope with extreme situation like large sliding window or high-dimensionality. To resolve these, two novel algorithms are proposed in this paper. The main contributions of this paper are as follows:Firstly, a novel stand-alone algorithm named RSUDS is proposed to process reverse Skyline query over uncertain data stream. RSUDS designs a new index structure based on grid-partitioning and Z–curve, based on which RSUDS adopts some heuristic optimization strategies. These strategies can minimize the relationship test number between two objects, which will ultimately enhance the response speed of query.Secondly, a parallel algorithm named PRSUDS is proposed to handle the problem that stand-alone algorithms can not process reserve Skyline query efficiently when the sliding window is too big or the dimensionality of data is too high. PRSUDS adopts angle-based dispatch strategy to assign task to peer nodes, meanwhile each node adopts the grid index and some heuristic optimization strategies proposed in RSUDS to optimize local processing.Thirdly, massive experiments on synthetic datasets are conducted to verify the performance of RSUDS and PRSUDS. The results show that RSUDS has better time performance than existing algorithm, and PRSUDS can handle the circumstances like large sliding window or high-dimensionality efficiently. The achievements prove that our research can meet the needs of real applications.