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

• 作者: 丁维龙 王菁 赵卓峰 韩燕波
• 来源期刊: 西安交通大学学报
• 关键词: 数据流 极值聚集 抽样
• 年，卷（期）: 2012,（11）
• 所属期刊栏目: 服务计算
• 页码范围: 106-111
• 分类号: TP309
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	韩燕波	北方工业大学云计算研究中心	44	770	13.0	27.0
3	赵卓峰	北方工业大学云计算研究中心	27	288	9.0	16.0
4	丁维龙	北方工业大学云计算研究中心	16	78	4.0	8.0
7	王菁	北方工业大学云计算研究中心	16	46	4.0	6.0