Improved random sampling algorithms for sliding windows over weighted streaming data

Computer Engineering and Applications ›› 2007, Vol. 43 ›› Issue (25): 18-20.

• 博士论坛 • Previous Articles Next Articles

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

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

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

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

通讯作者: 张龙波

Abstract

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

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

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

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

[1]	WANG Junhong, GUO Yahui. Imbalanced Data Stream Classification Algorithm for Dynamic Data Chunk [J]. Computer Engineering and Applications, 2021, 57(13): 124-129.
[2]	ZHOU Yu, ZHU Wenhao, FANG Qian, BAI Lei. Survey of Outlier Detection Methods Based on Clustering [J]. Computer Engineering and Applications, 2021, 57(12): 37-45.
[3]	XU Jiazhen, LI Ting, YANG Wei. Person Re-Identification by Multi-Scale Local Feature Selection [J]. Computer Engineering and Applications, 2020, 56(2): 141-145.
[4]	XU Qingyan, HE Li, ZHU Hongxi. Improved Detection Method of Concept Drift Based on the Hoeffding Inequality [J]. Computer Engineering and Applications, 2020, 56(19): 55-61.
[5]	HU Yang, HU Xuegang, LI Peipei. Fast Short Text Data Stream Classification Method Based on Spark [J]. Computer Engineering and Applications, 2020, 56(14): 138-147.
[6]	YANG Yao, FU Kechang, JIANG Tao, ZHANG Guoliang, LIU Jiajia, MENG Yi. AGV Path Planned with Heuristic RRT [J]. Computer Engineering and Applications, 2020, 56(12): 125-133.
[7]	CHEN Qiulian, JIANG Huanyu, ZHENG Yijun. Summary of Rapidly-Exploring Random Tree Algorithm in Robot Path Planning [J]. Computer Engineering and Applications, 2019, 55(16): 10-17.
[8]	SONG Yao1，2，3, SUN Xiaojuan1，2，3, HU Yuxin1，2，3, LEI Bin1，2，3, LU Xiaojun4. Quick-View Processing Method for Remote Sensing Data Based on Stream Computing [J]. Computer Engineering and Applications, 2019, 55(10): 77-82.
[9]	LUO Yidi, JIANG Hua, WANG Huijiao, WANG Xin. Anomaly detection algorithm of Argo profile based on Sliding Window and ARMA [J]. Computer Engineering and Applications, 2018, 54(19): 254-260.
[10]	LIU Weilun, ZHANG Hengyang, ZHENG Bo, ZHAO Wei. Statistical prediction mechanism for channel occupancy in airborne ad hoc network [J]. Computer Engineering and Applications, 2018, 54(15): 78-83.
[11]	WEI Zijin1，2，3, XIAO Li2，3. Parallel out-of-core model simplification algorithm based on improved vertex clustering [J]. Computer Engineering and Applications, 2018, 54(13): 181-190.
[12]	LIU Xiao, LIU Huiping, JIN Cheqing. Approximate solution for ER-Topk query upon uncertain data stream [J]. Computer Engineering and Applications, 2017, 53(4): 98-105.
[13]	HAN Chong1, YUAN Yingshan2, MEI Tao2, GENG Huiling2. Data stream outlier detection algorithm based on K-means [J]. Computer Engineering and Applications, 2017, 53(3): 58-63.
[14]	SHI Yingzhong 1, 2, CAO Jianfeng2, DENG Zhaohong1, JIANG Yizhang1. Flexible drift support vector machines for data stream classification [J]. Computer Engineering and Applications, 2017, 53(23): 118-122.
[15]	HEI Shanshan1, WANG Xiaoqin2. Block sliding window channel estimation algorithm based on LMMSE [J]. Computer Engineering and Applications, 2017, 53(16): 79-83.

Improved random sampling algorithms for sliding windows over weighted streaming data

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics