Dominant skyline query processing

Abstract

A skyline query retrieves from a data set, tuples that are not dominated by any other tuples with respect to a set of dimensions. In this thesis, we explored two interesting skyline variants. The first variant, called the dominant skyline queries, retrieves skyline tuples that dominate at least t other tuples. It is used to refine a large set of results to a smaller and more interesting set. The second variant, called the tier-based skyline queries, retrieves a??skylinea?? points from tier 1 to tier k, where tier-k points are skyline points with tier-1 to tier-(k-1) points eliminated from the input. It is meaningful when the skyline result set is too small. We proposed several algorithms to solve these two variants respectively. We have also conducted extensive experiments to study their performance. Through the experiments, we identified some interesting trends and tradeoffs of these algorithms.