Abstract
The skyline query is used to find a set of non-dominated objects in a multi-dimensional dataset. Recently, it has been further applied on uncertain data to provide advanced analysis for some important applications, such as environmental monitoring and market analysis. Due to the uncertainty, the dominance relationship between objects becomes uncertain and comes with a probability value. Previous works define the skyline model on uncertain data as probabilistic skyline and provide query processing methods that need a probability threshold to compute the qualified skyline objects. However, it is inconvenient for the users to give a suitable probability threshold without prior knowledge. Furthermore, only full dimensional skyline queries are considered in these works. Since different users may be interested in different dimensions, sub-space skyline queries are much more practical in many applications. In this thesis, we propose a novel skyline query processing method on uncertain data, which derives the top-k objects with the highest probabilities to be in the skyline of the user-demanded subspace. It is more user-friendly for users to give a number of how many answers they want rather than a probability threshold. In our method, two strategies are developed to efficiently prune objects which are not the top-k answers, and therefore substantially save the computation cost. The first strategy filters out the objects with no opportunity to be the skyline and finds a probability upper-bound of each remaining object for further pruning. Then, the second strategy provides a tight bound for pruning objects whose probability upper-bounds are much lower than the k-th highest probability. Finally, extensive experiments with real datasets are performed to demonstrate the efficiency and scalability of our approach.