摘要
考虑滑动窗口数据流上的连续MAX查询问题,提出了一种存储最优的方法。该方法只需保存数据集中可能成为极大值点的部分数据(候选点集),而将所有完全不可能成为极值点的数据进行丢弃,从而可以有效降低存储开销;提出了一个动态维护候选点集的方法,当数据独立分布时,处理一个新到数据所需的时间为(log),处理数据失效的时间开销为1,其中为滑动窗口包含的全部数据数目。理论分析和实验结果表明了该方法能够适应流速很快的场景,具有较高的效率。
The problem of continuous MAX query over sliding window data streams is addressed, and an optimal storage method is proposed. Only some of data points （candidate points） need to be stored in the system, while others is discarded with correctness guarantee. An effective method is designed to maintain the candidate points set dynamically. When the data satisfies random dis- tribution, only O （log N） time is needed to process a new arriving data point, while removal of an expired point is handled in O（1） time, where Nis the number of points contained in the sliding window. Theoretical analysis and experimental result show the efficiency of proposed method.
出处
《计算机工程与设计》
CSCD
北大核心
2008年第7期1863-1864,1868,共3页
Computer Engineering and Design
