Constrained Skyline Computing over Data Streams

Skyline computing has become a hot topic in the International since 2001. In data stream environment, previous works about Skyline computing only sought to maintain full space Skyline points or compute subspace Skyline points over sliding window. No one has considered the problem of computing constrained Skyline points over sliding window. For many real-word applications, however, users usually expect to receive constrained Skyline points quickly or progressively. In this paper, we study constrained Skyline computing over data streams. To the best of our knowledge, this problem has not been addressed before. The existing algorithms and their variations cannot be easily extended to support constrained Skyline computing efficiently, so a novel algorithm, called CSC, is proposed in this paper to solve this problem. It is a well progressive algorithm to incrementally maintain all the non-redundant dominance relationships of tuples over sliding window, and then compute all the constrained Skyline points.