Research On Skyline Query Over Uncertain Data Streams

Skyline queries are widely used in decision making and data mining applications formulti-criteria optimization of data. However, previous works on this problem are limited tothe case where certain data is considered. Skyline computation over uncertain data streams isstill at large. Furthermore, diferent users may be interested in diferent dimensions, makingthe skyline query over uncertain data streams more complicated than before. Existing worksare hard to satisfy with the real application demands. In this thesis, we talk about skylinequery over probabilistic data streams, and the main research of this paper is as follows:Firstly, this paper makes an analysis and some optimization on SOPDS algorithm,which is a current skyline algorithm over uncertain data streams. On the one hand, wereduce the computation time by reducing the times of domination checks and the times ofselected compensation. On the other hand, we delay updating the probability of object dom-inated by other objects to improve the algorithm’s efciency.Secondly, according to the characteristic that diferent users may be interested in difer-ent dimensions, this paper proposes an algorithm(PSSQ) for probabilistic subspace skylinequery on data streams. Based on a regular grid index, there are lots of domination checks canbe avoided by using the three kinds of dominating relationship between cells. Furthermore,Based on the subtle relationship between full space and an arbitrary subspace, PSSQ canestimate the upper and lower bounds of the skyline probability of each cell in query space,in order to save the computation costs.Finally, in order to realize monitoring the skyline query result in real time, this paperdevelops an algorithm(CPSQS) for continuous probabilistic skyline query in subspaces oversliding window on uncertain data streams. The CPSQS algorithm is the expansion of PSSQ,and its initial module is basically the same as PSSQ algorithm. In the maintaining process ofCPSQS, we reduce the maintaining time by dividing all cell into two parts, they are influencearea and free area respectively.Our research has significance on the application of skyline query in user-preference sys-tem, multi-criteria decision making system and data mining as well as visualization. Nowa-days, as uncertain data management are receiving more and more attention, our research canpromote the application of the skyline query under the uncertain data environment.