数据流上高效计算子空间Skyline的算法

被引：8

作者：

孙圣力

黄震华

李金玖

郭建奎

朱扬勇

机构：

[1] 复旦大学计算机与信息技术系

来源：

计算机学报 | 2007年 / 08期

关键词：

Skyline计算; 数据流; 子空间Skyline; 网格索引; 增量方法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

081202 ;

摘要：

流数据处理和多维空间中子空间上Skyline的计算是近年来数据管理与数据挖掘领域的研究热点.此前相关工作只专注于滑动窗口上Skyline的维护问题,未涉及到滑动窗口中子空间Skyline的计算.文中提出了一个基于网格索引的高效维护滑动窗口上Skyline的算法,以此为基础采用自顶向下的方式通过两个阶段增量式地返回目标子空间上的结果;开发的多个剪枝策略和启发式优化方法显著地提高了全空间Skyline的维护以及子空间Skyline的计算效率.理论分析和实验结果表明:与同类算法相比,文中提出的StreamSubsky算法以极少的时间开销就能输出第一个结果,并且算法具有良好的可扩展性.

引用

页码：1418 / 1428

页数：11

共 4 条

[1]

On the average number of maxi ma in a set of vec-tors. Buchta C. Information Processing Letters . 1989

[2]

Space/Ti me trade-offs in hash coding with al-lowable errors. Bloom B H. Communications of the ACM . 1970

[3]

SKYPEER:Efficient subspace skyline computation over dis-tributed data//Proceedings of the ICDE. Vlachou A,Doulkeridis C,Kotidis Y,Vazirgiannis M. . 2007

[4]

Summary cache:A scalable wide-area web cache sharing protocol. Fan L,Cao P,Al meida J,Broder A Z. . 1998

← 1 →