基于余弦函数局部特征的时间衰变模式

doi:10.3724/SP.J.1087.2012.00313

计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 313-316.DOI: 10.3724/SP.J.1087.2012.00313

基于余弦函数局部特征的时间衰变模式

樊海宽¹,²,³,刘奇志²,³

1. 国防科学技术大学计算机学院，长沙 410073
2. 南京大学计算机科学与技术系，南京 210093
3. 南京大学软件新技术国家重点实验室，南京 210093

收稿日期:2011-06-17 修回日期:2011-07-28 发布日期:2012-02-23 出版日期:2012-02-01
通讯作者: 刘奇志
作者简介:樊海宽(1988-)，男，江苏徐州人，硕士研究生，主要研究方向:无线网络；
刘奇志(1971-)，女，安徽芜湖人，副教授，博士，CCF会员，主要研究方向：高性能数据管理。

Time decay mode based on degressive cosine ramp

FAN Hai-kuan¹,²,³,LIU Qi-zhi³,⁴

1. College of Computer, National University of Defense Technology, Changsha Hunan 410073, China
2. Department of Computer Science, Nanjing University, Nanjing Jiangsu 210093, China
3. State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing Jiangsu 210093, China
4. Department of Computer Science, Nanjing University, Nanjing Jiangsu 210093, China

Received:2011-06-17 Revised:2011-07-28 Online:2012-02-23 Published:2012-02-01
Contact: LIU Qi-zhi

摘要/Abstract

摘要： 数据流具有无限增长的特征，目前的计算系统无法在线处理整个数据集，只能在有限空间内对部分数据进行处理。为了能够得到尽可能合理的结果，数据流系统常常采用单调递减函数由数据的时间戳来确定数据的权值，根据权值选择数据。广泛使用的单调函数是指数函数和多项式函数，但它们存在衰变速度太快或太慢等问题。提出一种新的时间衰变模式——使用余弦函数的局部衰变速度介于指数和多项式之间的特征来确定数据的权值。实验结果显示相对于指数和多项式衰变，局部余弦衰变具有衰变速度合理、参数易于确定、适用于乱序数据流等优势。

关键词: 数据流, 时间衰变模式, 余弦函数, 乱序数据流, 前向衰变模型

Abstract: Unlimited growth is one of the main characteristics of data stream. Current computing systems can only process a portion of data instead of the full data set online because of the limited memory and space. In order to obtain reasonable results, decay functions are often used in data stream systems to map the weights of data from timestamps. Monotonic decay functions such as exponential and polynomial functions are widely used, but they decay too fast or too slowly. In this paper, a new decay mode based on cosine function whose decay speed is between exponential function and polynomial function was proposed. The experimental results show that compared to exponential and polynomial decay modes, the degressive cosine ramp decays more reasonably and it is easy to appoint the parameter but also applicable to out-of-order data stream.

Key words: data steam, time decay model, cosine function, out-of-order data stream, forward decay model

中图分类号:

TP311.13

樊海宽刘奇志. 基于余弦函数局部特征的时间衰变模式[J]. 计算机应用, 2012, 32(02): 313-316.

FAN Hai-kuan LIU Qi-zhi. Time decay mode based on degressive cosine ramp[J]. Journal of Computer Applications, 2012, 32(02): 313-316.

参考文献

[1]COHEN E,STRAUSSAT M. Maintaining time-decaying stream aggregates[J]. Journal of Algorithms, 2006,59(1): 19-36. [2]CORMODE G, KORN F, TIRTHAPURA S. Exponentially decayed aggregates on data streams[C]// Proceedings of the 2008 IEEE 24th International Conference on Data Engineering. Washington, DC: IEEE Computer Society,2008: 1379-1381. [3]CORMODE G, TIRTHAPURA S, XU BOJIAN. Time-decaying sketches for robust aggregation of sensor data[J]. SIAM Journal on Computing, 2009, 39(4): 1309-1339. [4]CORMODE G, TIRTHAPURA S, XU BOJIAN. Time-decayed correlated aggregates over data streams[J]. Statistical Analysis and Data Mining， 2009, 2(5): 294-310. [5]BABCOCK B, BABU S, DATAR M, et al. Models and issues in data stream systems[C]// Proceedings of the 21st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2002: 1-16. [6]CORMODE G, SHKAPENYUK V, SRIVASTAVA D,et al. A practical time decay model for streaming systems[EB/OL].[2011-04-23]. http://www.research.att.com/people/Cormode_Graham/library/publications/CormodeShkapenyukSrivastavaXu09.pdf. [7]MADNICK S E, WANG R Y, LEE Y W, et al. Overview and framework for data and information quality research[J]. ACM Journal of Data and Information Quality, 2009, 1(1): 1-22. [8]BABCOCK B, DATAR M, MOTWANI R. Sampling from a moving window over streaming data[C]// Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. New York: ACM, 2002: 633-634. [9]DATAR M, GIONIS A, INDYK P, et al. Maintaining stream statistics over sliding windows[J]. SIAM Journal on Computing, 2002, 31(6): 1794-1813. [10]CORMODE G, KORN F, TIRTHAPURA S. Time-decaying aggregates in out-of-order streams[C]// Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. New York: ACM, 2008: 89-98. [11]PHILLIP B, TIRTHAPURA S. Distributed streams algorithms for sliding windows[C]// Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures. New York: ACM, 2002: 63-72.

[1]	尹春勇, 张帼杰. 面向分布式漂移数据流的集成分类模型[J]. 计算机应用, 2021, 41(7): 1947-1955.
[2]	郭帅, 苏旸. 基于数据流的加密流量分类方法[J]. 计算机应用, 2021, 41(5): 1386-1391.
[3]	樊仲欣. 基于数据流的聚类趋势分析算法[J]. 计算机应用, 2020, 40(8): 2248-2254.
[4]	苏振宇, 宋桂香, 刘雁鸣, 赵媛. 服务器管理控制系统威胁建模与应用[J]. 计算机应用, 2019, 39(7): 1991-1996.
[5]	龚鸣清, 叶煌, 张鉴, 卢兴敬, 陈伟. 基于ARMv8架构的面向机器翻译的单精度浮点通用矩阵乘法优化[J]. 计算机应用, 2019, 39(6): 1557-1562.
[6]	孙小涓, 石涛, 胡玉新, 佟继周, 李冰, 宋峣. 基于流式计算的空间科学卫星数据实时处理[J]. 计算机应用, 2019, 39(6): 1563-1568.
[7]	张译天, 于炯, 鲁亮, 李梓杨. 大数据流式计算框架Heron环境下的流分类任务调度策略[J]. 计算机应用, 2019, 39(4): 1106-1116.
[8]	韩萌, 丁剑. 数据流频繁模式挖掘综述[J]. 计算机应用, 2019, 39(3): 719-727.
[9]	李梓杨, 于炯, 卞琛, 鲁亮, 蒲勇霖. 基于流网络的流式计算动态任务调度策略[J]. 计算机应用, 2018, 38(9): 2560-2567.
[10]	肖成龙, 林军, 王珊珊, 王宁. 面向高层次综合的自定义指令自动识别方法[J]. 计算机应用, 2018, 38(7): 2024-2031.
[11]	袁泉, 郭江帆. 新型含噪数据流集成分类的算法[J]. 计算机应用, 2018, 38(6): 1591-1595.
[12]	程玉胜, 陈飞, 王一宾. 基于粗糙集的数据流多标记分布特征选择[J]. 计算机应用, 2018, 38(11): 3105-3111.
[13]	刘备, 谭新明, 曹文彬. Spark Streaming动态资源分配策略[J]. 计算机应用, 2017, 37(6): 1574-1579.
[14]	李梓杨, 于炯, 卞琛, 王跃飞, 鲁亮. 基于负载感知的数据流动态负载均衡策略[J]. 计算机应用, 2017, 37(10): 2760-2766.
[15]	付晨, 钟诚, 叶波. MapReduce并行加速数据流多模式相似性搜索[J]. 计算机应用, 2017, 37(1): 37-41.

基于余弦函数局部特征的时间衰变模式

Time decay mode based on degressive cosine ramp

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics