IntervalSketch:面向数据流的间隔项近似统计方法
IntervalSketch:Approximate Statistical Method for Interval Items in Data Stream
陈昕杨 1陈翰泽 2周嘉晟 2黄家卿 2余佳硕 2朱龙隆 1张栋3
作者信息
- 1. 福州大学计算机与大数据学院 福州 350108;泉城省实验室 济南 250100
- 2. 福州大学计算机与大数据学院 福州 350108
- 3. 泉城省实验室 济南 250100;福州大学至诚学院 福州 350002
- 折叠
摘要
流式数据库在数据库中的占比逐渐增加,在流式数据库的数据流中提取所需信息是一项重要任务.文中研究了数据流的间隔项,并将其应用到了网络场景中.其中间隔项指在数据流中以固定时间间隔到达的元素对,这是第一项在数据流中定义和统计间隔项的工作.为了高效统计间隔项的top-K,提出了 IntervalSketch.IntervalSketch首先基于模拟退火对数据流分块以加快统计速度,其次利用Sketch进行间隔项的存储,最后通过特征分组存储策略降低Sketch存储间隔项的空间开销,提升了统计间隔项的精度.IntervalSketch在两个真实数据集上进行了大量对比实验,实验结果表明,在同样内存的情况下,Inter-valSketch 明显优于基线方案,其中处理时间为基线方案的1/3～1/2,平均绝对误差、平均相对误差约为基线方案的1/3.
Abstract
The proportion of streaming databases is gradually increasing,and extracting the required information in the data streams of streaming databases is an important task.In this paper,we study interval items which refer to pairs of elements arri-ving with a fixed interval,and apply them to network scenarios.It is the first work to define and count interval items in data streams.To efficiently count the top-K interval items,IntervalSketch is proposed.IntervalSketch firstly chunks the data stream based on simulated annealing to accelerate the statistical speed,secondly,it uses Sketch to store the interval items,and lastly re-duces the memory of storing the interval items in Sketch through the feature grouping storage strategy,which enhances the accu-racy of counting the interval items.Extensive comparative experiments are carried out on two real datasets.Experimental results show that IntervalSketch significantly outperforms the baseline solution with the same memory,and the processing time is 1/3～1/2 of the baseline solution,the average absolute error and the average relative error are 1/3 of the baseline solution.
关键词
Sketch/数据库/数据挖掘Key words
Sketch/Database/Data mining引用本文复制引用
基金项目
国家重点研发计划专项(2023YFB2904000)
国家重点研发计划专项(2023YFB2904005)
泉城省实验室项目(QCLZD202304)
山东省实验室项目(SYS202201)
出版年
2024
NETL
NSTL
万方数据