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

Skyline Algorithm for Data Stream Based on Nearest Neighbor Filtering

作　　者：王艳杰[1] 薛安荣[1] 吴正寅[1] 

机构地区：[1]江苏大学计算机科学与通信工程学院,江苏镇江212013

出　　处：《计算机工程》2011年第21期43-45,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60773049);江苏大学高级人才启动基金资助项目(09JDG041)

摘　　要：在Skyline查询算法中,Lazy算法的数据处理能力较弱。针对该问题,利用最近邻过滤的思想,提出改进的NNSC算法。在预处理阶段,利用欧氏距离定义一个阈值,如果新插入数据对象的欧氏距离大于阈值,提前处理该对象,以提高算法利用率,减少资源的消耗。实验结果证明,NNSC可降低时空复杂度,对于正相关数据,性能提升效果明显。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算法 NNSC算法 最近邻过滤 欧氏距离 

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