Efficient processing of multiple continuous skyline queries over a data stream

Abstract

Given a set of data objects, the skyline query returns the objects that are not dominated by others. 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 paper, we propose a new method, called FAST, for processing multiple continuous skyline queries over a data stream. 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.