Effective space usage estimation for sliding-window skybands (Q1958903)

Summary: Skyline query computes all the ``best'' elements which are not dominated by any other element and thus is very important for decision-making applications. Recently, it was generalized to skyband queries and \(k\)-skyband queries return those elements dominated by no more than \(k\) of other elements. To incorporate the skyband operator into the stream engine for monitoring skybands over sliding windows, space usage estimation for skyband operators becomes a critical issue in the query optimizer. We firstly introduce the skyband sketch as a cost model. Based on the cost model, we propose an approach for estimating the space usage of skyband operators over sliding windows of data streams under the assumptions of statistical independence across dimensions, no duplicate values over each dimension, and dimension domains totally ordered. Experiments verify that our approach can estimate the space usage effectively over arbitrarily distributed data. To the best of our knowledge, this is the first work that attempts to address this issue and proposes an effective approaches to solve it.