Date Added: Aug 2009
The authors consider external algorithms for skyline computation without pre-processing. Their goal is to develop an algorithm with a good worst case guarantee while performing well on average. Due to the nature of disks, it is desirable that such algorithms access the input as a stream (even if in multiple passes). Using the tools of randomness, proved to be useful in many applications, the authors present an efficient multi-pass streaming algorithm, RAND, for skyline computation. As far as the authors are aware, RAND is the first randomized skyline algorithm in the literature.