关键词: Skyline 更新数据流 网格索引数据结构

Abstract:

In this paper, we address the continuous skyline computation problem, and consider a new scenario named update stream where the First-In-First-Out rul  e （which is the basic and important feature of traditional sliding window models） does not hold, which leads to the existing algorithms＇ inapplicabil  lity. The problem is formally described; a Basic Updatestream Skyline Monitoring algorithm （BUSM） is raised and analyzed; a novel grid-indexed data st  tructure is presented, and then a Grid-based Update-stream Skyline Monitoring algorithm （GUSM） is proposed, which makes use of the characteristics whe ere the deletion and addition operations appear simultaneously in update streams, and represents the influence region by grids for the previous eliminat ion. Analytical and experimental results show that the proposed approaches perform well on the continuous skyline computation over update data streams.

Key words: Skyline, update data stream, grid-indexed data structure