The semantics and approximation for the skyline operator
Wen Jin · Summit (Simon Fraser University) · 2007
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.III First of all, my deep gratitude goes to my supervisor and mentor, Dr. Jiawei Han, for his continuous encouragement, guidance and support during the course of this work.His creative thinking and vision and as well as his persistence and industriousness has been inspiring me during my study and will always give me strength in my future career.I am very thankful to my supervisor, Dr. Martin Ester