IntervalSketch:面向数据流的间隔项近似统计方法  

IntervalSketch:Approximate Statistical Method for Interval Items in Data Stream

作　　者：陈昕杨 陈翰泽 周嘉晟 黄家卿 余佳硕 朱龙隆 张栋 CHEN Xinyang;CHEN Hanze;ZHOU Jiasheng;HUANG Jiaqing;YU Jiashuo;ZHU Longlong;ZHANG Dong(College of Computer Science and Big Data,Fuzhou University,Fuzhou 350108,China;Quan Cheng Laboratory,Jinan 250100,China;Zhicheng College,Fuzhou University,Fuzhou 350002,China)

机构地区：[1]福州大学计算机与大数据学院,福州350108 [2]泉城省实验室,济南250100 [3]福州大学至诚学院,福州350002

出　　处：《计算机科学》2024年第4期4-10,共7页Computer Science

基　　金：国家重点研发计划专项(2023YFB2904000,2023YFB2904005);泉城省实验室(QCLZD202304);山东省实验室项目(SYS202201)。

摘　　要：流式数据库在数据库中的占比逐渐增加,在流式数据库的数据流中提取所需信息是一项重要任务。文中研究了数据流的间隔项,并将其应用到了网络场景中。其中间隔项指在数据流中以固定时间间隔到达的元素对,这是第一项在数据流中定义和统计间隔项的工作。为了高效统计间隔项的top-K,提出了IntervalSketch。IntervalSketch首先基于模拟退火对数据流分块以加快统计速度,其次利用Sketch进行间隔项的存储,最后通过特征分组存储策略降低Sketch存储间隔项的空间开销,提升了统计间隔项的精度。IntervalSketch在两个真实数据集上进行了大量对比实验,实验结果表明,在同样内存的情况下,IntervalSketch明显优于基线方案,其中处理时间为基线方案的1/3~1/2,平均绝对误差、平均相对误差约为基线方案的1/3。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 arriving 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 reduces the memory of storing the interval items in Sketch through the feature grouping storage strategy,which enhances the accuracy 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 数据库 数据挖掘 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]