DC-Tree: An Algorithm for Skyline Query on Data Streams

摘要

Skyline query asks for a set of interesting points that are non-dominated by any other points from a potentially large set of data points and has become research hotspot in database field. Users usually respect fast and incremental output of the skyline objects in reality. Now many algorithms about skyline query have been developed, but they focus on static dataset, not on dynamic dataset. For instance, data stream is a kind of the dynamic datasets. Stream data are usually in large amounts and high speed; moreover, the data arrive unlimitedly and consecutively. Also, the data are variable thus they are difficult to predict. Therefore, it is a grim challenge for us to process skyline query on stream data. Real-time control and strong control management are required to capture the characteristic of data stream, because they must settle data updating rapidly. To this challenge, this paper proposes a new algorithm: DC-Tree. It can do skyline query on the sliding window over the data stream efficiently. The experiment results show that the algorithm is both efficient and effective.