一种大域数据流中缺失值的填充方法

• 作者: 刘奇志 张剡 柏文阳 赵飞
• 来源期刊: 南京大学学报（自然科学版）
• 学科: 工学
• 关键词: 大域数据流 不确定性 缺失值填充 最小计数概要
• 年，卷（期）: 2011,（1）
• 页码范围: 32-39
• 分类号: TP311
• 语种: 中文

摘要

在网络流量监控等数据流应用场景中,数据流中的IP地址等属性的值域往往很大,对于连续到达的数据流,管理系统一般不存储全体数据集,而是维护一个较小规模的数据概要.对于这类大域数据流中的缺失数据,难以采用邻近值填充等传统方法进行填充,也不能轻易删除.最小计数概要是一种轻量级的数据流概要,适合大域数据流的概要维护.本文基于最小计数概要及其维护技术,提出最小频率概要,并根据这两种概要填充大域数据流中的缺失数据.该填充方法首先设计一组两两独立的Hash函数族,将一段时间内大域数据流的属性值(如网络流量)映射并累加到非大域二维表数据结构中,形成大域数据流的计数概要(如一段时间内网络总流量),与此同时,在二维表中存储计数概要伴随的频率概要(即数据流到达次数,如数据包的个数),然后根据最小计数概要与最小频率概要之比对大域数据流的缺失值(如某个数据包的流量)进行填充.采用模拟大域数据集在通用软硬件环境下进行大量实验,结果表明,基于最小计数/频率概要的填充方法可获得较高的精度,而且填充误差随数据属性值定义域的变化呈非单调性变化,另外,随着数据量的增加,填充误差虽然越来越大,但是变化越来越缓慢,最终趋于一个稳定值.对于给定误差参数ε,本文设计的填充算法时空界限为1/ε,部分应用的时间界限为1.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张剡	南京大学软件新技术国家重点实验室计算机科学与技术系	12	102	5.0	10.0
2	柏文阳	南京大学软件新技术国家重点实验室计算机科学与技术系	33	262	8.0	15.0
3	赵飞	南京大学软件新技术国家重点实验室计算机科学与技术系	4	20	2.0	4.0
4	刘奇志	南京大学软件新技术国家重点实验室计算机科学与技术系	9	17	3.0	4.0