Indexing for progressive skyline computation

Abstract

Many decision support applications are characterized by several features: (1) the query is typically based on multiple criteria; (2) there is no single optimal answer (or answer set); (3) because of (2), users are typically looking for satisficing answers; (4) for the same query, different users, dictated by their personal preferences, may find different answers meeting their needs. As such, it is important for the DBMS to present all interesting answers that may fulfill a user's need. In this paper, we focus on the set of interesting answers called the skyline. 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 indexing schemes to compute the skyline of a set of points progressively. Unlike most existing algorithms that require at least one pass over the dataset to return the first interesting point, our algorithms return interesting points gradually as they are identified. The first algorithm, Bitmap, is completely non-blocking and exploits a bitmap structure to quickly identify whether a point is an interesting point or not. The second method, Index, exploits a transformation mechanism and a B+-tree index to return skyline points in batches. Our extensive performance study shows that the proposed algorithms provide quick initial response time as compared to existing algorithms. Moreover, both schemes can also outperform existing techniques in terms of total response time. While Index is superior in most cases, Bitmap is effective when the number of distinct values per dimension is small as well as when the number of skyline points is large. © 2002 Elsevier Science B.V. All rights reserved.