Please use this identifier to cite or link to this item:
Title: Indexing for progressive skyline computation
Authors: Eng, P.-K. 
Ooi, B.C. 
Tan, K.-L. 
Keywords: B+-tree index
Issue Date: 2003
Citation: Eng, P.-K., Ooi, B.C., Tan, K.-L. (2003). Indexing for progressive skyline computation. Data and Knowledge Engineering 46 (2) : 169-201. ScholarBank@NUS Repository.
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.
Source Title: Data and Knowledge Engineering
ISSN: 0169023X
DOI: 10.1016/S0169-023X(02)00208-2
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.