Research on Cost-Efficient Processing of Continuous Extreme Queires

We address the problem of cost-efficient processing of continuous extreme queries (MAX or MIN) over distributed sliding window streams, and propose several methods for communication reduction and resource sharing among queries. Firstly, we develop an effective pruning technique to minimize the number of elements to be kept. It can be shown that on average only O(logN) key points need to be stored for exact answer of extreme query, where N is the number of points contained in the sliding window. Then we consider the distributed environment, where remote nodes delay the data transmission as late as possible, and adopt the pruning strategy to filter local stream tuples, which is quite efficient in communication reduction. Analytical analysis and experimental evidences show the efficiency of proposed approach both on storage/communication reduction and efficiency improvement.