Resource Sharing in Continuous Extreme Values Monitoring on Sliding Windows

The problem of resource sharing in continuous extreme values monitoring (MAX or MIN) over sliding windows is considered. Firstly, an effective pruning technique called key points (KP) is developed to minimize the number of elements to be kept for all queries. It can be shown that on average the cardinality of KP satisfies M=O(logN), where N is the number of points contained in the widest window. Then an efficient algorithm called MCEQP (multi-continuous extreme queries processing algorithm) is proposed for continuously monitoring K queries with different sliding window widths. The main idea of MCEQP is to handle queries collectively by exploiting similarities and sharing resources such as computation and memory, which is more efficient than handling them separetely. 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 KP. A trigger based technique is provided to avoid frequent but unnecessary process for data expirations, and only on some special time instances, O(K) time is needed to update K results. The dynamic registration and removal of queries are also supported by MCEQP in O(M+K) time. Theoretical analysis and experimental evidences show the efficiency of the proposed approach both on storage reduction and efficiency improvement.