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

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (25): 18-20.

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

张龙波^1,2，李战怀²，余敏²，蒋芸²

1.山东理工大学计算机学院，山东淄博 255049
2.西北工业大学计算机学院，西安 710072

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-01 发布日期:2007-09-01
通讯作者: 张龙波

Improved random sampling algorithms for sliding windows over weighted streaming data

ZHANG Long-bo^1,2，LI Zhan-huai²，YU Min²，JIANG Yun²

1.School of Computer Science，Shandong University of Technology，Zibo，Shandong 255049，China
2.School of Computer Science，Northwestern Polytechnical University，Xi’an 710072，China

Received:1900-01-01 Revised:1900-01-01 Online:2007-09-01 Published:2007-09-01
Contact: ZHANG Long-bo

摘要/Abstract

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

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

Abstract: The main focus in algorithms for data streams has been on efficient construction of summary structures（synopses） for
sliding windows.This paper introduces the problem of construction of summary structures（synopses） from continuous updated sliding windows over weighted streaming data and presents two improved random sampling algorithms for this problem.The presented algorithms are basic window-based random sampling algorithms，which extends the Weighted Random Sampling（WRS） algorithm to
deal with the expiration of data items from sliding windows.For every tuple，a key is calculated by its weight and a randomly-generated value.When a tuple is added to the sample or selected to delete from the sample，not only the key but also the arrival time is considered.The experimental results show that the algorithms are effective and efficient for continuous weighted streaming data processing over sliding window model.

Key words: data stream, sliding window, summary structure, random sampling algorithm

张龙波^1,2，李战怀²，余敏²，蒋芸². 带权值数据流滑动窗口随机抽样算法的改进[J]. 计算机工程与应用, 2007, 43(25): 18-20.

ZHANG Long-bo^1,2，LI Zhan-huai²，YU Min²，JIANG Yun². Improved random sampling algorithms for sliding windows over weighted streaming data[J]. Computer Engineering and Applications, 2007, 43(25): 18-20.

[1]	王俊红，郭亚慧. 面向动态数据块的非平衡数据流分类算法[J]. 计算机工程与应用, 2021, 57(13): 124-129.
[2]	周玉，朱文豪，房倩，白磊. 基于聚类的离群点检测方法研究综述[J]. 计算机工程与应用, 2021, 57(12): 37-45.
[3]	徐家臻，李婷，杨巍. 多尺度局部特征选择的行人重识别算法[J]. 计算机工程与应用, 2020, 56(2): 141-145.
[4]	徐清妍，何丽，朱泓西. 改进Hoeffding不等式的概念漂移检测方法[J]. 计算机工程与应用, 2020, 56(19): 55-61.
[5]	胡阳，胡学钢，李培培. 基于Spark的快速短文本数据流分类方法[J]. 计算机工程与应用, 2020, 56(14): 138-147.
[6]	杨瑶，付克昌，蒋涛，张国良，刘甲甲，孟易. 启发式RRT算法的AGV路径规划[J]. 计算机工程与应用, 2020, 56(12): 125-133.
[7]	宋峣1，2，3，孙小涓1，2，3，胡玉新1，2，3，雷斌1，2，3，卢晓军4. 基于流式计算的遥感卫星数据快视处理方法[J]. 计算机工程与应用, 2019, 55(10): 77-82.
[8]	郑逢斌1，朱青1，2，臧文乾2. 一种XML驱动的遥感产品生产并发数据流模型[J]. 计算机工程与应用, 2018, 54(24): 266-270.
[9]	杨融泽，柳毅. 面向异常数据流的多分类器选择集成方法[J]. 计算机工程与应用, 2018, 54(2): 107-113.
[10]	李成龙，吕鑫，李鑫. 抗基于历史轨迹预测攻击的动态K-匿名算法[J]. 计算机工程与应用, 2018, 54(2): 119-124.
[11]	罗一迪，蒋华，王慧娇，王鑫. 基于滑动窗口和ARMA的Argo剖面数据异常检测算法[J]. 计算机工程与应用, 2018, 54(19): 254-260.
[12]	刘炜伦，张衡阳，郑博，赵玮. 机载自组网信道占用统计预测机制[J]. 计算机工程与应用, 2018, 54(15): 78-83.
[13]	魏子衿1，2，3，肖丽2，3. 改进顶点聚类方法的并行核外模型简化算法[J]. 计算机工程与应用, 2018, 54(13): 181-190.
[14]	刘骁，刘辉平，金澈清. 面向不确定数据流的近似ER-Topk查询处理[J]. 计算机工程与应用, 2017, 53(4): 98-105.
[15]	韩崇1，袁颖珊2，梅焘2，耿慧玲2. 基于K-means的数据流离群点检测算法[J]. 计算机工程与应用, 2017, 53(3): 58-63.