一种使用简化预排序的k-支配Skyline查询算法

K-Dominant Skyline Computation Using Simplified Presort

近年来,Skyline查询在多目标决策、数据挖掘、数据库可视化等方面得到广泛应用.然而在高维空间环境下,skyline查询因为返回的结果集过大而不能提供有用的信息.因此,学术界提出了k-支配skyline查询的概念.它通过弱化数据点之间的支配关系,使数据点间更容易产生支配关系,从而使结果集的大小保持在一个合适的范围内.现有k-支配skyline查询算法分为建立索引和不建立索引两种类型.其中不建立索引的算法在高维空间,反相关数据和渐近输出等方面表现比较差,而基于索引的算法花费大量时间去建立索引,整体性能都不高.本文提出一种基于简化预排序的k-支配skyline查询算法(SPA),实现用O(n)的时间复杂度对数据进行简化预排序.理论论证和实验数据都显示了SPA算法远比国内外现有的最好算法更加高效.

Skyline query has been widely used for multi-criteria decision making, data mining, etc. However, by increasing the number of attributes, the probability that a point dominates another one is reduced significantly. As a result, the number of skyline points becomes too numerous to provide any useful information. Recently, k-dominant skyline query has been introduced, which can reduce the number of retrieved points by relaxing the definition of dominance. Existing k-dominant skyline query algorithms are divided into no indexing and index based types. The no indexing algorithm performs poorly on high dimensional space and anti-correlated data. And the index-based algorithm spends a lot of time to build the index. The overall efficiency is not high. In this paper, we propose a simplified pre-sorted algorithm （ SPA ） to solve the problem of k-dominant skyline computation. Theoretical arguments and experi- mental data show that the SPA algorithm is more efficient than all of the existing methods.