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

Fill absent values in massive domain data stream

作　　者：赵飞[1] 刘奇志[1] 张剡[1] 柏文阳[1] 

机构地区：[1]南京大学软件新技术国家重点实验室计算机科学与技术系,南京210093

出　　处：《南京大学学报（自然科学版）》2011年第1期32-39,共8页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(60775046)

摘　　要：在网络流量监控等数据流应用场景中,数据流中的IP地址等属性的值域往往很大,对于连续到达的数据流,管理系统一般不存储全体数据集,而是维护一个较小规模的数据概要.对于这类大域数据流中的缺失数据,难以采用邻近值填充等传统方法进行填充,也不能轻易删除.最小计数概要是一种轻量级的数据流概要,适合大域数据流的概要维护.本文基于最小计数概要及其维护技术,提出最小频率概要,并根据这两种概要填充大域数据流中的缺失数据.该填充方法首先设计一组两两独立的Hash函数族,将一段时间内大域数据流的属性值(如网络流量)映射并累加到非大域二维表数据结构中,形成大域数据流的计数概要(如一段时间内网络总流量),与此同时,在二维表中存储计数概要伴随的频率概要(即数据流到达次数,如数据包的个数),然后根据最小计数概要与最小频率概要之比对大域数据流的缺失值(如某个数据包的流量)进行填充.采用模拟大域数据集在通用软硬件环境下进行大量实验,结果表明,基于最小计数/频率概要的填充方法可获得较高的精度,而且填充误差随数据属性值定义域的变化呈非单调性变化,另外,随着数据量的增加,填充误差虽然越来越大,但是变化越来越缓慢,最终趋于一个稳定值.对于给定误差参数ε,本文设计的填充算法时空界限为1/ε,部分应用的时间界限为1.To fill the absent values in massive-domain data stream,an algorithm based on Count-Min Sketch as well as Frequency-Min Sketch is proposed.In some data stream applications,such as network traffic monitoring,the domains of IP addresses and some other attributes are always massive.Data Stream Management System usually prefers to storage a sketch rather than storage the whole datasets.So it is not suitable to use traditional imputation methods to fill the absent values of the massive-domain data stream,which a...

关 键 词：大域数据流 不确定性 缺失值填充 最小计数概要 

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