3FO:基于过滤的一种Skyline查询算法  

3FO: A Filtering-Based Algorithm for Skyline Query

作　　者：田中彬[1] 马志新[1] 李廉[1] 杨曙光[1] 

机构地区：[1]兰州大学信息科学与工程学院,兰州730000

出　　处：《微计算机信息》2008年第27期163-165,154,共4页Control & Automation

基　　金：网络计算的作业调度方法研究(60473095);颁发部门:国家自然科学基金委员会信息科学二处(原计算机科学学科)

摘　　要：Skyline查询是从一个给定的数据集上返回所有不被其它点支配的点的集合。本文主要针对二维和三维空间上Skyline查询结果的单调性特点提出了一种新的3FO算法,它通过NN过滤、最小值覆盖过滤和单调性过滤三次过滤操作,删除非Skyline点数据,可以快速地返回全部的Skyline点。实验结果表明,该算法比传统算法在相同数据集上平均性能提高2-3倍,是一种高效的算法。The Skyline query returns a set of points that is not dominated by any other points from a given dataset. This paper advances a 3FO-algorithm by examining the monotonic property of the data obtained by applying Skyline query on the 2-D and the 3- D spaces respectively. Three passes of filtering are used to efficiently separate Skyline points from those of not, they are NN-fihering, mini-value covering filtering and monotonic filtering. Empirical results have shown the efficiency that the performance of this algorithm on a certain dataset is 2 to 3 times better on average than traditional ones.

关 键 词：数据挖掘 SKYLINE查询 过滤 支配 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]