An Algorithm for Multi-Extreme Queries on Sliding Windows

摘要

Processing multi-extreme value queries efficiently over data streams is important for data analysis in real-time environment. Cost-efficient processing of continuous extreme values queries over sliding windows, especially about resource sharing, is considered. Firstly, an effective storage structure to minimize the number of elements to be kept for queries is given. We prove the average the cardinality of storage structure satisfies m=O(log n), where n is the number of points contained in the widest window. Secondly, an efficient algorithm called MEVQ is proposed for continuously processing K queries with different sliding window widths. The main idea of MEVQ is to handle queries collectively by exploiting similarities and sharing resources such as computation and memory, which is more efficient than handling them separately. The link list implemented instance of MEVQ can update all k results in O(m+k) time when a new tuple arrives, where m is the cardinality of storage structure. 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 MEVQ in O(m+k) time. Theoretical analysis and experimental evidences show the efficiency of proposed approach both on storage reduction and efficiency improvement.