1HKUST
2CityU
The skyline operator returns the "best" records according to any scoring function that is monotonic on each attribute. The presentation will consist of two parts. The first one (based on our SIGMOD 03 paper) studies skyline computation in coventional databases. We present BBS (branch-and-bound skyline), a progressive algorithm based on nearest neighbor search, which is IO optimal, simple to implement and can be efficiently applied to a variety of alternative skyline queries.
The second part of the presentation studies skylines in append-only stream environments, where query processing takes into account only the most recent tuples. Expired records (that arrived before a sliding window covering the most recent timestamps) are simply discarded. We propose algorithms that continuously monitor the incoming tuples and maintain the skyline incrementally. The algorithms utilize several interesting properties of streaming skylines in order to expunge tuples from the system as early as possible (i.e., before their expiration), and facilitate space and time efficiency.