Efficient Progressive Skyline Computation

TLDR

The skyline of a set of points consists of those not dominated by any other point, where dominance means being as good or better in all dimensions and better in at least one dimension. This paper focuses on retrieving the skyline from a database and introduces two novel algorithms, Bitmap and Index, for this task. Bitmap and Index compute the skyline progressively, returning interesting points as they are identified rather than requiring a full pass over the dataset. Performance studies show the algorithms deliver quick initial responses, with Index outperforming Bitmap in most cases.

Abstract

In this paper, we focus on the retrieval of a set of interesting answers called the skyline from a database. Given a set of points, the skyline comprises the points that are not dominated by other points. A point dominates another point if it is as good or better in all dimensions and better in at least one dimension. We present two novel algorithms, Bitmap and Index, to compute the skyline of a set of points. Unlike most existing algorithms that require at least one pass over the dataset to return the rst interesting point, our algorithms progressively return interesting points as they are identi ed. Our performance study further shows that the proposed algorithms provide quick initial response time with Index being superior in most cases.