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 ME VQ 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 ME VQ 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 onlyon some special time instances, O(k) time is needed to update kresults. 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.
data strenm sliding window multi-extrenie query resource sharing
Aiping Li Li Tian Yan Jia Peng Zou
Institute of Computer Science National University of Defense Technology ChangSha, HuNan. CHINA
国际会议
成都
英文
423-428
2010-06-23（万方平台首次上网日期，不代表论文的发表时间）