连续K-支配SKYLINE查询算法研究.pdf

连续 K-支配 SKYLINE 查询算法研究 摘要
连连连续续续 K-支支支配配配 SKYLINE 查查查询询询算算算法法法研研研究究究
摘摘摘 要要要
近年来，skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛
应用。然而在高维空间环境下，skyline查询因为返回的结果集过大而不能提供有用
的信息。因此，学术界提出了k-支配skyline查询的概念。它通过弱化对“支配”的定
义，使数据点间更容易产生支配关系，从而使结果集的大小保持在一个合适的范围
内。在静态 k-支配 skyline 查询问题上，现有算法要么存在建立索引开销太大问题；
要么在高维空间中存在过多重复计算问题。而在连续 k-支配 skyline 查询方面，现有
算法中剪枝方式和分治策略都存在删除数据点后 维护困难的问题。
本文通过分析现有算法存在的缺点，结合 k-支配 skyline 查询的内在特性，分
别在静态 k-支配 skyline 查询和连续 k-支配 skyline 查询这两个方面提出了新的算法。
本文的主要贡 献可以分为以下几点：
(1)提出了不支配关系的概念。两个支配能力弱的数据点之间不容易发生支配关
系；两个支配能力强的数据点之间也不容易发生支配关系。本文通过计算数据点的
支配能力，然后 使数据点只和有可能与自己互相支配的数据点进行比较，避免与不
可能产生支配关系的数据点进行不必要的比较，从而节省了大量的计算时间。
(2)针对建立索引和不建立索引两类算法在进行静态 k-支配 skyline 查询上存在的
问题，本文提出了一种基于简化预排序的 k-支配 skyline 查询算法。该算法的核心思
想是引入平均数据点，并通过与之比较把各个数据点按支配能力大小进行分块，之
后 根据支配能力值对各分块进行排序。这样的排序不仅大幅度降低了预排序的时间，
而且也很大程度减少了数据点间无意义的比较。
(3)提出了准 skyline 点的概念。在连续 k-支配 skyline 查询问题上，由于维护传
统 skyline 点需要很大的计算量，所以使用传统 skyline 点来进行剪枝并不是很好的
策略。本文提出的准 skyline 点的概念，准 skyline 数据集比传统 skyline 数据集更易
于维护，并且其能发挥传统 skyline 数据集所具有的剪枝效果。因此引入准 skyline 思
想能够很大提高 k-支配 skyline 查询效率。
(4)提出了保留支配关系的方法。由于在连续 k-支配 skyline 查询问题上，任何数
据点的更新都有可能影响到数据集的 k-支配 skyline 点。如果每次数据点更新都重
新计算 k-支配 skyline 点是效率低下的。本文通过保留数据点之间一些重要的支配
关系，当数据更新时能够很快的找到需要唤醒的数据点，从而提高了算法的时间效
率。
I
摘要 连续 K-支配 SKYLINE 查询算法研究
最后 ，通过理论分析和模拟实验使本文提出的新算法和现有算法进行比较，并
进一步使本文提出的新算法应用到真实数据环境中，理论论证和实验数据都显示本
文提出的新算法都比国内外现有算法更加高效。
关键词： Skyline、 k-支配 skyline 、查询、多目标决策
作 者： 黄荣跃
指导教师： 赵 雷
II
Research on continuous