存储最优的连续MAX查询方法

考虑滑动窗口数据流上的连续MAX查询问题,提出了一种存储最优的方法。该方法只需保存数据集中可能成为极大值点的部分数据(候选点集),而将所有完全不可能成为极值点的数据进行丢弃,从而可以有效降低存储开销;提出了一个动态维护候选点集的方法,当数据独立分布时,处理一个新到数据所需的时间为(log),处理数据失效的时间开销为1,其中为滑动窗口包含的全部数据数目。理论分析和实验结果表明了该方法能够适应流速很快的场景,具有较高的效率。