基于最近邻过滤的数据流Skyline算法

摘要

Lazy of Skyline query algorithm is poor in data processing. So this paper proposes an improved algorithm called Nearest Neighbor-based Skyline Computation(NNSC) by using the idea of Nearest Neighbor(NN) filtering. It defines a threshold by using Euclidean distance in pre-processing stage. If the Euclidean distance of the recently inserted object is greater than which of the threshold, it will be processed ahead of time to improve the algorithm efficiency and reduce resource consumption. Experimental results show that NNSC can reduce the time and space complexity, and its performance is improved significantly for positive correlated data.%在Skyline查询算法中,Lazy算法的数据处理能力较弱.针对该问题,利用最近邻过滤的思想,提出改进的NNSC算法.在预处理阶段,利用欧氏距离定义一个阈值,如果新插入数据对象的欧氏距离大于阈值,提前处理该对象,以提高算法利用率,减少资源的消耗.实验结果证明,NNSC可降低时空复杂度,对于正相关数据,性能提升效果明显.