The Continuous Skyline Computation on Update Data Streams
Yan Jia · Computer Engineering and Science · 2008
In this paper, we address the continuous skyline computation problem, and consider a new scenario named update stream where the First-In-First-Out rule (which is the basic and important feature of traditional sliding window models)does not hold, which leads to the existing algorithms’ inapplicability. The problem is formally described; a Basic Update-stream Skyline Monitoring algorithm (BUSM) is raised and analyzed; a novel grid-indexed data structure is presented, and then a Grid-based Update-stream Skyline Monitoring algorithm (GUSM) is proposed, which makes use of the characteristics where the deletion and addition operations appear simultaneously in update streams, and represents the influence region by grids for the previous elimination. Analytical and experimental results show that the proposed approaches perform well on the continuous skyline computation over update data streams.