摘要： 在Skyline查询算法中，Lazy算法的数据处理能力较弱。针对该问题，利用最近邻过滤的思想，提出改进的NNSC算法。在预处理阶段，利用欧氏距离定义一个阈值，如果新插入数据对象的欧氏距离大于阈值，提前处理该对象，以提高算法利用率，减少资源的消耗。实验结果证明，NNSC可降低时空复杂度，对于正相关数据，性能提升效果明显。
关键词:
数据流,
Skyline算法,
NNSC算法,
最近邻过滤,
欧氏距离
Abstract: 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.
Key words:
data stream,
Skyline algorithm,
Nearest Neighbor-based Skyline Computation(NNSC) algorithm,
Nearest Neighbor(NN) filtering,
Euclidean distance
中图分类号:
王艳杰, 薛安荣, 吴正寅. 基于最近邻过滤的数据流Skyline算法[J]. 计算机工程, 2011, 37(21): 43-45.
WANG Yan-Jie, XUE An-Rong, TUN Zheng-Yin. Skyline Algorithm for Data Stream Based on Nearest Neighbor Filtering[J]. Computer Engineering, 2011, 37(21): 43-45.