文章基本信息

标题：Diversity in Skylines
本地全文：下载
作者：Yufei Tao
期刊名称：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. Speciﬁcally, we ﬁrst describe the state-of-the-art formulation of diverse skylines. Then, we explain several algorithms for ﬁnding 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.