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

丁维龙 1; 3; 韩燕波 1; 2; 王菁 1; 赵卓峰 1

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- 时间滑动窗口上数据流极值聚集的空间优化
- A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows
- 西安交通大学学报 2012年46卷第11期页码：106-111
- 作者机构：
  
  1. 北方工业大学云计算研究中心,北京,100041
  2. 中国科学院计算技术研究所,北京,100190
  3. 中国科学院研究生院,北京,100049
- 作者简介：
- 基金信息：
  
  : 2012-06-30. 作者简介: 丁维龙(1983-),男,博士生;韩燕波(通信作者),男,教授,博士生导师. 基金项目: 国家自然科学基金资助项目(60970132,61003294)
- DOI：
  中图分类号： TP309
- 网络首发：2012-11-10，
  
  纸质出版：2012
- 稿件说明：
移动端阅览
丁维龙 1, 3, 韩燕波 1, 等. 时间滑动窗口上数据流极值聚集的空间优化[J]. 西安交通大学学报, 2012,46(11):106-111.

A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows[J]. 2012, 46(11): 106-111.
丁维龙 1, 3, 韩燕波 1, 等. 时间滑动窗口上数据流极值聚集的空间优化[J]. 西安交通大学学报, 2012,46(11):106-111. DOI：

A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows[J]. 2012, 46(11): 106-111. DOI：

摘要

传统的数据流极值聚集方法在极端情形下为获得连续的精确解

会因维护大量候选项而导致巨大的内存开销

为此文中提出了一种时间滑动窗口上内存有界的极值聚集方法.在候选项数量达到指定阈值时

该方法随机抽样新到达窗口的数据

使得内存维护有限数量的候选项

连续返回极值近似解.设计了一种空间有界的摘要数据结构REx-link

可以在有界的内存中基于随机抽样进行维护

实现时间滑动窗口上的数据流极值聚集.从理论上证明了随机算法的出错概率存在上界

并通过仿真实验分析了算法的返回结果与精确解的近似程度.分析表明

计算精度和空间开销的折中是实际应用可接受的.

Abstract

A space-bounded extreme aggregation of data stream is proposed over time-based sliding window to reduce the vast space of traditional methods under the worst cases. When the number of candidates reaches a given threshold

the method would randomly sample the new arrival tuples in the window to maintain limited candidates and continuously return approximate extremes. A space-bounded synopsis structure REx-link is designed to maintain extreme candidates by random sampling in memory

and to implement extreme aggregation over time-based sliding window. It is proved that an upper bound for the error probability of the random algorithm exists. Comprehensive experiments are performed to analyze the accuracy between returned results and exact solutions

and the results show that the tradeoff between the accuracy and the space overhead is acceptable in practice.

关键词

Keywords

references

CUGOLA G, MARGARA A. Processing flows of information: from data stream to complex event processing [R]. Politecnico di Milano, Italy: Dip. di Electronica e Informazione, 2010.

RAJARAMAN A, ULLMAN J. Mining of massive datasets [M]. Cambridge, UK: Cambridge University Press, 2011.

LIU Zhenyu, SIA K C, CHO J. Cost-efficient processing of MIN/MAX queries over distributed sensors with uncertainty [C]∥Proceedings of the 2005 ACM Symposium on Applied Computing. New York, USA: ACM, 2005: 634-641.

SILBERSTEIN A, MUNAGALA K, YANG Jun. Energy-efficient monitoring of extreme values in sensor networks [C]∥Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data. New York, USA: ACM, 2006: 169-180.

DENG Hanlin, ZHANG Baoxian, LI Cheng, et al. MAX-MIN aggregation in wireless sensor networks: mechanism and modeling [J]. Wireless Communications and Mobile Computing, 2010, 12: 615-630.

PENG Xiaoming, HE Yanxiang, TIAN Li. Communication reduction for continuous extreme values monitoring over distributed data streams [C]∥Proceedings of the Workshop on Power Electronics and Intelligent Transportation System. Washington, DC, USA: IEEE Computer Society, 2008: 181-187.

CORMEN T, LEISERSON C, RIVEST R, et al. Introduction to algorithms [M]. Cambridge, MA, USA: The MIT Press, 2001.

杨清宇, 孙凤伟, 张曌,等.利用测地线距离的改进谱聚类算法. 2012, 46(8): 1-7.

司刚全, 娄勇, 张寅松.鲁棒最小二乘支持向量机及其在软测量中的应用. 2012, 46(8): 15-21.

梁炎明, 刘丁.规则递归T-S模糊模型及其辨识方法. 2012, 46(8): 54-58.

黄伯虎, 张海宾, 王小兵,等.移动环境中的位置依赖连续轮廓查询. 2012, 46(6): 79-86.

陈衡,钱德沛,伍卫国,等.传感器网络基于邻居信息量化的能量平衡路由. 2012, 46(4): 1-6.

张慧,韩崇昭,闫小喜.概率假设密度滤波的谱聚类目标状态提取方法. 2012, 46(2): 1-5.

丁要军,蔡皖东.采用两阶段策略模型(KTSVM)的P2P流量识别方法. 2012, 46(2): 45-50.

聂艳明,李战怀,陈群.针对不确定射频识别数据流的改进概率推导方法. 2011, 45(12): 45-52.

薛峰,周亚东,高峰,等.一种突发性热点话题在线发现与跟踪方法. 2011, 45(12): 64-69.

刘弹,杨景明,罗爱玲.具有全局聚类的多属性离散化算法. 2011, 45(9): 1-5.

王羡慧,覃征,张选平,等.采用仿射传播的聚类集成算法. 2011, 45(8): 1-6.

彭柳青,张军英.一种鲁棒的子空间聚类算法. 2011, 45(6): 13-19.

张熠卓,徐光华,梁霖,等.利用增量式非线性流形学习的状态监测方法. 2011, 45(1): 64-68.

史宝全,梁晋,张晓强,等.特征保持的点云精简技术研究. 2010, 44(11): 37-40.

赵海祥,伍卫国,赵增,等.一种应用于远程并行程序调试系统的新型消息聚集机制. 2009, 43(10): 27-31.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

超临界水异常区域热力学特性研究

混合电解槽阵列协同的风光耦合制氢系统双层多目标优化

张角凹坑气膜孔对双层壁气膜冷却特性的影响

超临界二氧化碳向心透平轮背间隙内风阻损失及流动特性研究

隧道内燃料电池汽车氢气泄漏扩散特性及影响因素