Paper5《An Efficient Pruning Method to Process Reverse Skyline Queries 》(2014)阅读笔记

背景

BBRS缺点

• 过滤过程非常耗时

RSSA缺点

• 预先计算每个对象的所有天际线，并将选定数量的点存储为结果点的近似值
• 基于预计算所以需要大量的存储
• 通过近似处理可以降低一些但是增加了反向天际查询的总处理时间，因为在细化步骤中将需要更多的窗口查询

PBRS的改进

• 用两种方法连续修剪后选者，显著减少细化步骤。
• 在主存储器中保留一些必要的对象，用对象集合细化候选对象。

主要工作

• 提出了两种新的剪枝算法：
  搜索区域修剪方法（SARS）和候选对象修剪方法（COPM）。
  在数据频繁变化的情况下。该算法能够有效地处理反向天际线查询。有效的减少了在用于存储预先计算的结果的现有方法下的低效存储使用。
• 使用更有效的修剪算法。避免不必要的磁盘访问。
• 在细化步骤中。使用内存，不需要额外的磁盘访问。提前保留一组数据。

创新点

• 第一个修剪方法，显著缩小了判断区域
• 提出新的细化过滤方法，保存第二环节中淘汰掉的点，用来检验RSL中的点，得到最后的结果集

步骤

搜索区域修剪方法。

• 图a为BBRS的搜索区域。图b为该算法中由p8点提出的搜索区域。图c是被p7改变的搜索区域。
  
• 经过本文对搜索区域的进一步细化，几乎能将搜索区域减少一半。原理是，p9不会是反向天际线查询。因为p8会q支配掉。P8离p9更近。所以。只有在阴影区域内的点才有可能成为q的反向skyline查询点。
• 访问到p7的时候。p7可以进一步。对阴影区域进行缩小。这里有一个引理支持。如果点不在SA（C，q）的阴影区域，那么它不是q的reverse skyline点。

候选对象修剪方法

• 提出CA（p，q），为一种长方形来过滤RSL（q）中的点
  

细化步骤

• 本文并没有采取BBRS和RSSA中的窗口查询的方法，因为这很耗时，因为它需要对磁盘中的点进行磁盘访问。
• 本文通过留下一些被过滤的点放到内存中为ND，最后进行细化步骤查询的时候，遍历ND中元素对RSL中的点进行查询，提高速度避免磁盘访问
• 将第二组即不收任何对象支配的一组留下
• 很好的例子：
  

整个算法过程

作者的话：

我的理解：

• 所有的点都会被遍历的，但是这个算法中基本只遍历一次就可以。
• 首先看这个点能不能被全局支配。如果能。可以直接丢弃它。如果不能，进入剪枝环节，满足就放到候选集和结果集。不满足也要先留着他。放在存储器中，以便最后进行细化步骤。
• 算法基本可以分为三大块，第一大块检查是不是全局skyline，即能不能被结果集中的点支配。第二大块。是本文的主体部分，是两种修剪的方法。第三大块。是细化步骤。也是本文中进行改进的部分。
• 本文对细化步骤的改进主要是将满足第一大块但是不满足第二大块中那些被淘汰的对象，把他们存储起来，在第三大块细化步骤中用来比较。这样可以避免进行昂贵的窗口查询（BBRS和RSSA中使用的），减少耗时的磁盘读取。