看了林老师关于09年的skyline的论文,发现原来参考文献[4]和07年的有对比,所以先看看这个原文.

Skyline computation has many applications including multi-criteria decision making. In this paper, we study the problem of selecting k skyline points so that the number of points, which are dominated by at least one of these k skyline points, is maximized. We first present an efficient dynamic programming based exact algorithm in a 2d-space.
Then, we show that the problem is NP-hard when the dimensionality is 3 or more and it can be approximately solved by a polynomial time algorithm with the guaranteed approximation ratio 1 ? 1/ e . To speed-up the computation, an efficient, scalable, index-based randomized algorithm is developed by applying the FM probabilistic counting technique.
A comprehensive performance evaluation demonstrates that our randomized technique is very efficient, highly accurate, and scalable.

Skyline 计算有很多应用,包括多规则决策应用领域等.在本文中,我们研究了至少存在一个受控点的skyline点最大化的k选择问题,我们首先提出基于精确算法的2路空间有效动态程序设计.然后,证明了在3维或多维空间下这个问题是可以近似地通过保证近似率为1-1/e的多项式时间算法来解决的NP-hard问题..为了加快计算,通过FM概论计算技术开发了一个有效的,可扩展的,基于索引的优化算法.一个综合的性能指标证明了我们的优化技术是非常有效,高精确并可扩展的.