期刊名称：Bulletin of the Technical Committee on Data Engineering
出版年度：2009
卷号：32
期号：04
出版社：IEEE Computer Society
摘要：Given an integer k, a diverse skyline contains the k skyline points that best describe the tradeoffs (among
different dimensions) offered by the full skyline. This paper gives an overview of the latest results on
this topic. Specifically, we first describe the state-of-the-art formulation of diverse skylines. Then, we
explain several algorithms for finding a diverse skyline, where the objective is to save cost by avoiding
the computation of the entire skyline. In particular, we will discuss a polynomial-time algorithm in 2D
space that returns the exact result, the NP-hardness of the problem in dimensionality at least 3, and an
approximate solution with good quality guarantees.
