Australian Computer Society
In the last decade, skyline queries have been extensively studied for different domains because of their wide applications in multi-criteria decision making and search space pruning. A skyline query returns all the interesting points in a multi-dimensional data set that are not dominated by any other point with respect to all dimensions. However, real world data sets are seldom complete, i.e. data points often have missing values in one or more dimensions. Traditional skyline query processing algorithms developed for complete data cannot be easily adapted for such situations because of the non-transitive and potentially cyclic nature of dominance relation that arises in the case of incomplete data.