摘要：本文考虑＂更新数据流＂场景下的连续Skyline计算问题。在该环境下,数据不再满足＂先进先出＂特性,使得传统基于滑动窗口数据流上的连续Skyline计算方法不再适用。在对问题进行了形式化描述后,本文提出了基本算法BUSM,在分析其不足的基础上提出了一种网格索引数据结构,基于该结构提出了GUSM算法。该算法利用了更新数据流中删除和添加操作成对同时出现的特性,以网格为单位表示影响区域并进行快速排除预处理。理论分析和实验结果证明了上述方法在更新数据流上连续计算Skyline的有效性。

关键词：skyline 更新数据流 网格索引数据结构 

单位：国防科技大学计算机学院 湖南长沙410073