Mathematical Problems in Engineering
Volume 2010 (2010), Article ID 828035, 15 pages
Research Article

Effective Space Usage Estimation for Sliding-Window Skybands

1School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
2College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China

Received 1 February 2010; Accepted 24 March 2010

Academic Editor: Ming Li

Copyright © 2010 Lijun Chen et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Skyline query computes all the “best” elements which are not dominated by any other elements and thus is very important for decision-making applications. Recently, it is generalized to skyband query and a k-skyband query returns 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 operator becomes a critical issue in the query optimizer. In this paper, we firstly introduce the skyband sketch as the cost model. Based on the cost model, we propose an approach for estimating the space usage of skyband operator 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 approaches 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 the issue and proposes effective approaches to solve it.