数据流上约束的子空间Skyline计算

Constrained Subspace Skyline Computing over Data Streams

在数据流环境下,此前有关Skyline计算的研究涉及到滑动窗口上全空间Skyline的维护或子空间Skyline的计算,未考虑到满足约束条件的子空间Skyline计算。在首次研究数据流上约束的子空间Skyline渐进计算问题中,给出了具有良好渐进性的约束的子空间Skyline计算算法—CSSC,该算法首先通过增量维护滑动窗口中元组之间的非多余支配关系来计算约束的Skyline,然后在此基础上,将文献[8]中介绍的子空间Skyline计算方案引入到约束条件下,从而实现约束的子空间Skyline的计算。

In data stream environment, previous works about Skyline computing sought to maintain full space Skylines or compute subspace Skylines over sliding window. No one has considered the problem of computing constrained subspace Skylines over sliding window. In this paper, we first study constrained subspace Skyline computing over data streams. A novel algorithm, called CSSC, is proposed in this paper. It is a well progressive algorithm to compute all the constrained full space Skylines firstly by incrementally maintaining the non-redundant dominance relationships of tuples over sliding window, and then based on this, the technique of subspace Skyline computing in [8] is introduced into constraint to compute constrained subspace Skylines.