Research on dynamic skyline query processing over data streams

Skyline query is a typical mulit-objective optimization problem. Dynamic Skyline is an important variant of skyline operator. Given a query point q, dynamic skyline query can return the tuples which are close to q in all the dimensions. Comparing with the skyline query, dynamic skyline can return the result flexibly by changing locations of the query point q. In this paper, we focus on the dynamic skyline query problem over the data stream, which plays a very important role in the multi-criteria decision making. To solve this problem efficiently, firstly, we propose a combined index structure to manage the data in the data stream. The combined index structure contains two parts: the whole data are managed by a hierarchical division structure; the data in the leaf division are managed by an inverted index structure. This combined index structure has some advantages, such as be updated fast, have high filtering capacity and be suitable for arbitrary data distributions. It can accelerate the speed of update operation over the data stream and improve the performance of dynamic skyline calculation. Secondly, based on this combined index, we propose the basic dynamic skyline query algorithm over data streams (BDS² for short), which can quickly compute the dynamic skyline by maintaining a small amount of data. However, BDS² has a long delay when dealing with some updates. In order to calculate the dynamic skyline stably over the data stream and avoid a sharp increase in calculation when updating some points, we propose the improved dynamic skyline query algorithm over data stream (IDS² for short). Finally, we verify the effectiveness of our proposed algorithms through a series of experiments.