Efficient processing of multiple continuous skyline queries over a data stream

Abstract

Skyline queries are widely used in applications that support multi-criteria decision making and analysis. Given a set of data objects, the skyline query returns the objects that are not dominated by others. An object o is said to "dominate" another object o` if o is not worse than o` on all the dimensions and o is strictly better than o` on at least one dimension. Due to the recent growth of applications supporting multi-preference analysis and decision making, skyline computation has received considerable attention. Although skyline computation has been studied extensively for static data, there has been relatively less work on data streams. Recently, a few methods have been proposed to process a single continuous skyline query over a data stream. However, efficient techniques that can handle multiple skyline queries have not been much considered. In this dissertation, we propose a new method, called FAST, for processing multiple continuous skyline queries over a data stream. Since a data stream is often unbounded, a query over a data stream is generally specified with a sliding window. FAST is mainly for processing multiple continuous queries, where each query is associated with a sliding window. FAST uses a filtering technique that can early discard an object that will not be a member of any future skyline of continuous queries, and uses a discriminant that can efficiently determine which objects in memory are skyline objects for which queries. We present that the proposed method FAST can compute skylines of multiple continuous queries very efficiently. Through extensive experiments, we show the high performance and great scalability of the proposed method.