Efficient Computation of Reverse Skyline on Data Stream

Reverse skyline queries have been proved very useful in business location, environmental monitoring and some other applications. In this paper, we consider reverse skyline queries processing on data stream, which provides continuous, high-speed data elements. Specifically, we consider the latest objects in the sliding window. The challenge is that it is difficult to maintain a multidimensional index (for example, R-tree) in a dynamic dataset. Focusing on this challenge, we propose an algorithm with a DC-tree as index and effective pruning methods to reduce the search space of query processing and the cost of index maintaining. Extensive experiments show that our algorithms are efficient and effective for on-line reverse skyline query.