Distance-based Representative Skyline.
Yufei Tao (CUHK), Ling Ding (CUHK), Xuemin Lin (UNSW), Jian Pei (SFU)
ICDE 2009
Guohua LI

This paper maybe the hardest one in today’s seminar.
[Background]
Review of Skyline
Given a set D of multidimensional points skyline consists of the points that are not dominated by any other points.
X Dominates Y means X is smaller than Y in all dimensions.
In another word, skyline point implys that there at least one dimension of this point is smaller than others while other dimensions not.

What’s the k-representive skyline?
In this paper, it is defined by Representation Error — the maximum value of non-representive skyline point to its nearest skyline point.
Given Skyline S={s_1,s_2,…,s_n}
In 2-D space, the optimal substurue is obvious. We devide the skyline into two parts – one part consists of the first (k-1) representive skyline, another part consist of the kth skyline and its neighours.
The kth skyline
the other consists of the last one.
[Intuition]
For every non-representive skyline point, there is a nearby representive skyline point.
[Solution]
DP in 2D case.