时间滑动窗口上数据流的极值聚集的空间优化
当前众多物联网环境下的数据处理表现为连续实时的数据流查询。针对时间滑动窗口的数据流极值聚集查询，传统方法为获得连续的精确解，在高速高并发等极端的情形下需要维护大量的极值候选值，导致较大的内存开销。本文设计实现了内存有界的摘要数据结构及其聚集算法，维护时间窗口内有限数量的极值候选，连续返回查询的近似解；并从理论上证明了算法的有效性和与精确解的近似程度。在人工和真实数据集上的仿真实验表明，算法体现了计算精度和空间开销的折中，可在内存有限的环境下达到满足实际应用的效果。
时间滑动窗口 极值查询 摘要数据结构 抽样
丁维龙 韩燕波 王菁 赵卓峰
中国科学院计算技术研究所,北京,100190;中国科学院研究生院,北京,100190;北方工业大学,北京,100041 中国科学院计算技术研究所,北京,100190;北方工业大学,北京,100041 北方工业大学,北京,100041
国内会议
西安
中文
1-8,10-10
2012-08-16（万方平台首次上网日期，不代表论文的发表时间）