带权值数据流滑动窗口随机抽样算法的改进

摘要：

通过改进加权抽样算法,结合基本窗口技术,提出了两种面向带权值数据流上连续更新滑动窗口的随机抽样算法:WRSB算法和IWRSB算法.当新的数据元组到达时,根据数据元组的权值计算出该元组的键值,根据元组键值的大小决定其是否进入样本集以及样本集中被替换的数据元组,同时设置一个系统缓冲区来保存最近到达的键值较大的部分数据元组,作为过期数据元组的后备,使算法能够有效地处理过期数据元组问题.理论分析和实验结果表明,两种算法都能有效地处理带权值数据流上连续更新滑动窗口的随机抽样问题,相比较而言,IWRSB算法具有更好的性能.

关键词：数据流、滑动窗口、概要数据结构、随机抽样算法

所属期刊栏目：43

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金60573096;山东理工大学校科研和教改项目2006KJM15

在线出版日期：2007-10-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：18-20