Cost-Efficient Processing of Continuous Extreme Queries over Distributed Data Streams

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. An efficient algorithm called MCEQP is proposed in the coordinator node for continuously monitoring K queries with different sliding window widths, and the linklist-implemented instance of MCEQP can update all K results in O(M+K) time when a new tuple arrives, where M is the cardinality of key points set corresponding to the widest window. Theoretical analysis and experimental evidences show the efficiency of proposed approach both on storage/communication reduction and efficiency improvement.