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