A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows

您当前的位置：

首页 >

文章列表页 >

A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows

更新时间：2025-07-09

- A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows
- Vol. 46, Issue 11, Pages: 106-111(2012)
- 作者机构：
  
  1. 北方工业大学云计算研究中心,北京,100041
  2. 中国科学院计算技术研究所,北京,100190
  3. 中国科学院研究生院,北京,100049
- 作者简介：
- 基金信息：
- DOI：
  CLC： TP309
- Online First：10 November 2012，
  
  Published：2012
- 稿件说明：
移动端阅览
A Space Optimization Method to Aggregate Extremes of Data Stream over Time-Based Sliding Windows[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Fast Calculation Method for Thermal Flow Fields in Transformer Windings Based on PI-DeepONet

Effects of Steam Addition on the Swirl Combustion and Emission Characteristics of Cracked Ammonia

Review of the Application of EBSILON Software in Combined Heat and Power System Optimization

Turbulent Kinetic Energy Dissipation Mechanism of Supercritical Carbon Dioxide Leakage Flow in a Scallop Bionic Seal Cavity

Mechanism and Optimal Control Strategy for Hysteresis in Rapid Dehumidification Response of Indirect Thermal Systems in Electric Vehicles

Related Author

No data

Related Institution

No data

⁰