资源描述：
《可重写循环滑动窗口：面向高效在线数据流处理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、http://www.paper.edu.cn可重写循环滑动窗口：面向高效的在线数据流处理李俊奎，王元珍华中科技大学数据库与多媒体研究所，湖北武汉(430074)E-mail：jkltk2000@126.com摘要：滑动窗口是在线数据流处理中的重要技术和基础设施。针对当前基于向量模型的滑动窗口存在滑动过程中需要移动过多数据，而导致效率不高的问题，提出一种可重写循环的滑动窗口技术。该技术在滑动过程中不移动数据，而是采用重写的方式来完成数据更新，并且它能够与当前滑动窗口无缝集成。理论分析和实验对比表明，该技术有显著的效率提升
2、，能够高效地应用于实际的数据流处理。关键词：在线数据流，滑动窗口，可重写，循环中图分类号：TP3311.引言数据流(DataStream)是一串实时、连续和有序的数据序列。数据流在实际生活中广泛存[5]在，典型应用有互联网流量、传感器网络数据、电话记录、大气温度数据以及大量实时的[2]商业数据等，当前对数据流的处理已成为一个研究热点。处理数据流具有新的挑战，这些挑战可以简单概括为“在线、量大、高速、未知、一遍”。在线：数据在线到达而非已静态存储；量大：数据流的瞬时数据量巨大；高速：数据随着流的推进而快速变化；未知：数据流
3、的数据流速和大小未知；一遍：一旦流中的数据被处理过，将被丢弃或被离线存储，再次处理则相当困难甚至几乎不现实。尽管流数据可以看作是无限的，但是实际的计算都是在流数据一个较小的子集上进行，[6]即存在一个窗口的概念。窗口在流数据上不断滑动，窗口内的数据则不断得到处理。目前[1]典型的滑动窗口实现都基于向量模型，这种模型的一个问题是随着窗口的滑动，需要移动窗口内的数据，把新数据移入窗口，旧数据移出窗口。本文则提出一种可重写循环的滑动窗口方法，该方法采用对窗口数据的重写完成数据更新，在窗口滑动的过程中并不需要移动数据，从而提高了
4、系统的处理效率。另外该方法可以与当前的滑动窗口实现无缝集成，应用该方法不会影响到已实现的流数据处理系统上层应用。本文其余部分如下组织：第2节讨论当前基于向量模型的滑动窗口实现；第3节提出可重写循环的滑动窗口技术；实验结果以及实验分析在第4节给出；最后在第5节总结全文，并指出未来的进一步工作。2.基于向量模型的滑动窗口2.1相关定义定义1数据流是一串按照时间顺序无限到达的元组Ttt=,,...，其中ti(1≥)是数据12i基金项目:国家发展与改革委员会“安全智能数据整合平台开发及产业化”项目（项目编号[2005]538号）
5、-1-http://www.paper.edu.cn流中标识(采用显式时间戳或隐式到达时间点标识)为i处的数据。为简便处理，本文统一采用隐式到达时间点作为数据流的数据标识，但使用显式时间戳并不影响文中讨论。定义2滑动窗口在数据流上滑动一个大小为ww(0>)的窗口，窗口内数据Ssss=,,...,构成流数据的一个瞬时抽样，w称为窗口宽度。01w−1定义3格局滑动窗口内数据的一次状态/组织形式称为一个格局，位置为iiw(0≤≤−1)的数据格局可以用三元组Pi()=<>lengthheadi,,表示，其中：length为滑动窗
6、口内数据量；head为滑动窗口末端标记；i为滑动窗口内的位置下标。2.2基于向量模型的滑动窗口技术(1)基本思想当前数据流上的滑动窗口都基于向量模型实现，该向量模型将滑动窗口建模为一个向量。随着窗口的移动，靠近向量末端的数据向前移，覆盖前面的数据，新的数据则加入到向量末端，从而完成数据更新。(2)形式化描述该模型可以形式化表示为：VectorSW=<>wlengthheadf,,,，òw为滑动窗口宽度；òlength为当前窗口的数据量；òhead为滑动窗口数据末端的标记，新数据放置在该位置；òf为滑动窗口的格局变换函数：
7、f:'PP→，它决定了在新数据到来时滑动窗口中已存在数据的格局变化。在向量模型中，f的定义如表1所示。表1向量模型滑动窗口格局变换函数(nil、new分别表示不记录格局和新格局)f(,<>lengthheadi,
8、lengthih=eadnewhead<lengthheadi,
9、length=w)ih<>eadih=eadnew(3)模型分析从表1可以看出，基于向量模型的滑动窗口技术分为两个阶段：窗口未满和
10、窗口已满阶段。在窗口未满阶段，随着窗口的滑动，窗口不移出数据，新数据进入窗口的head位置，同时更新length和head。在窗口已满阶段，随着窗口的滑动，窗口内的第1个数据被移出，其它数据则前移，覆盖前序数据，新数据进入窗口的末端位置(w−1)。此时length值固定为w，head值则固定为w−1，表示新数据都在窗
