Indexing for progressive skyline computation

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