Title: Dynamic Dimension Indexing for Efficient Skyline Maintenance on Data Streams
Authors: Rui Liu and Dominique Li
Abstract: Skyline computation receives much attention in research and application domains, for which many algorithms have been developed during decades. However, maintaining the skyline in data streams is much challenging because of the continuous updates of skyline with respect to non stop adding of incoming tuples and removing of expired tuples. In this paper, we present a dynamic dimension indexing based approach RSS to skyline computation on high dimensional data streams, which is efficient at both count-based and time-based sliding windows regardless the dimensionality of data. Our analysis shows that the time complexity of RSS is bounded by a subset of the instant skyline, and our evaluation shows the efficiency of RSS on both of low and high dimensional data streams.
