Stabbing the Sky: Efficient Skyline Computation over Sliding Windows

Wei Wang

University of New South Wales, Australia

Skyline computation is fundamental to many applications including multi-criteria decision making systems. In this talk, we focus on the problem of efficiently computing the skyline against the most recent N elements in a data stream seen so far. Specifically, we study the n-of-N skyline queries; that is, computing the skyline for the most recent n (forall n <= N) elements. Firstly, we developed an effective pruning technique to minimize the number of elements to be kept. It can be shown that on average storing only O((log N)^d) elements from the most recent N elements is sufficient to support the precise computation of all n-of-N skyline queries in a d-dimension space if the data distribution on each dimension is independent. Then, a novel encoding scheme is proposed, together with efficient update techniques, for the stored elements, so that computing an n-of-N skyline query in a d-dimension space takes O(log N + s) time that is reduced to O(d * loglog N + s) if the data distribution is independent, where s is the number of skyline points. Thirdly, a novel trigger based technique is provided to process continuous n-of-N skyline queries with O(delta) time to update the current result per new data element and O(log s) time to update the trigger list per result change, where delta is the number of element changes from the current result to the new result. Finally, we extend our techniques to computing the skyline against an arbitrary window in the most recent N elements. Besides theoretical performance guarantees, our extensive experiments demonstrated that the new techniques can support online skyline query computation over very rapid data streams.

About the speaker

Dr. Wei Wang is a Lecturer in the School of Computer Science and Engineering, The University of New South Wales, Australia. He is also affiliated with National ICT of Australia (NICTA). He received his Ph.D. in Computer Science from the Hong Kong University of Science and Technology in 2004. His current research interests include query processing and optimization for XML, data warehousing and OLAP, approximate query processing and data mining.