The semantics and approximation for the skyline operator

The skyline operator of a $d$-dimensional dataset, which returns the points that are not dominated by any other point on all dimensions,has been well recognized its importance in preference queries and multi-criteria decision making applications. Many existing algorithms have been developed to improve the efficiency in computing the exact skyline objects in the full space. However, few previous work involves the following problems: (1) Why and in which subspaces is (or is not) an object in the skyline? (2) How to approximate the skyline objects in a reasonable way? (3) Can the notion of skyline operator facilitate other database operators? (4) How could skyline be computed efficiently over multiple relational tables? In this work, we explore the semantics of skyline in subspaces, study the approximate skyline objects in databases, apply the notion of skyline to the efficient processing of other database operations such as ranked queries, and propose solutions to implement skyline operator on multiple relations. We develop a class of novel and efficient methods to fulfill these tasks in large databases. A comprehensive performance study on both synthetic datasets and real datasets demonstrates that our proposed methods are not only efficient but also effective.