paper(4)《Efficient Computation of Reverse Skyline Queries》阅读笔记
注意:本文中关于1.如何选取sample样本点的 2.对于多维的贪心算法还没清楚
主要工作
- 根据BBS算法提出BBRS算法
- 提出增强方法:RSSA算法,节省存储开支,作为一种预先计算的近似值
主要概念
-
global skyline集
由所有点中未被任何一个其他点全局支配点的点集组成
若p1全局支配p2关于q,需要满足:
(1)p1和p2在q的同一块(n维情况下q有2d块)
(2)p1支配p2 -
BBS算法
首先计算global skyline集,然后对其中的每个点做窗口查询,看q是不是它的dynamic skyline点 -
DDR(p)和DADR(p)的图示
核心算法
- RSSA
预先计算出每个点的DDR和DADR,当查询点给出后,看查询点在global skyline中的点的哪一个区域
(1)计算每个点的Dynamic skyline ,存储正在磁盘
(2)得到了查询点q之后,计算其global skyline,查询这其中的每个点,例如s,若q是在DADR(s)中,那么q是RSL(s);若q在DDR(s)中,q不是RSL(s). - 近似dynamic skyline方法:
衡量DDR和DADR时,采用少量样本点而不是全部,从而降低存储开销
(1)为了节省存储空间超线性的问题选取,只每个点的少量(常数k)dynamic skyline点于disk中,这样得到一个不精确的分界,如上图b所示,然后若q是在DADR(s)中,那么q是RSL(s);若q在DDR(s)中,q不是RSL(s).若q在上图中白色部分,则需要进行细致
(2)先判断p的右上窗格中有没有别的点,若没有,再判断四个窗格中,如图所示。若都没有,则是dynamic skyline点
整个算法过程如图所示
实验评估
这篇文章的实验评估比较有趣
主要用BBRS和RSSA算法进行对比
对比方面:
剪枝程度和查询窗口大小
10:不同数据分布的两种算法复杂度比较
11:不同数据集中的global skyline和最重的reverse skyline数量对比
13:不同维度下两种算法的比较