Business Intelligence Investigate

Randomized Multi-Pass Streaming Skyline Algorithms

Download now Free registration required

Executive Summary

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.

  • Format: PDF
  • Size: 280.8 KB