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

作     者：陈昕杨 陈翰泽 周嘉晟 黄家卿 余佳硕 朱龙隆 张栋 CHEN Xinyang;CHEN Hanze;ZHOU Jiasheng;HUANG Jiaqing;YU Jiashuo;ZHU Longlong;ZHANG Dong

作者机构：福州大学计算机与大数据学院福州350108 泉城省实验室济南250100 福州大学至诚学院福州350002 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2024年第51卷第4期

页      面：4-10页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

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

主　　题：Sketch 数据库 数据挖掘 

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