时间滑动窗口上数据流极值聚集的空间优化

丁维龙　韩燕波　王菁　赵卓峰

摘要：传统的数据流极值聚集方法在极端情形下为获得连续的精确解，会因维护大量候选项而导致巨大的内存开销，为此文中提出了一种时间滑动窗口上内存有界的极值聚集方法，在候选项数量达到指定阈值时，该方法随机抽样新到达窗口的数据，使得内存维护有限数量的候选项，连续返回极值近似解，设计了一种空间有界的摘要数据结构REx-link，可以在有界的内存中基于随机抽样进行维护·实现时间滑动窗口上的数据流极值聚集，从理论上证明了随机算法的出错概率存在上界-并通过仿真实验分析了算法的返回结果与精确解的近似程度，分析表明，计算精度和空间开销的折中是实际应用可接受的。