Effective Space Usage Estimation for Sliding-Window Skybands

Skyline query computes all the “best” elements which arenot dominated by any other elements and thus is very importantfor decision-making applications. Recently, it is generalizedto skyband query and a k-skyband query returnsthose elements dominated by no more than k, of other elements.To incorporate the skyband operator into the stream enginefor monitoring skybands over sliding windows, space usageestimation for skyband operator becomes a critical issue inthe query optimizer. In this paper, we firstly introduce theskyband sketch as the cost model. Based on the cost model,we propose an approach for estimating the space usage ofskyband operator over sliding windows of data streams underthe assumptions of statistical independence across dimensions,no duplicate values over each dimension, and dimensiondomains totally ordered. Experiments verify thatour approaches can estimate the space usage effectively overarbitrarily distributed data. To the best of our knowledge,this is the first work that attempts to address the issue andproposes effective approaches to solve it