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

作     者：赵飞 刘奇志 张剡 柏文阳 Zhao Fei;Liu Qi-Zhi;Zhang Yan;Bai Wen-Yang

作者机构：南京大学软件新技术国家重点实验室计算机科学与技术系南京210093 

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

出 版 物：《南京大学学报（自然科学版）》 (Journal of Nanjing University（Natural Science）)

年 卷 期：2011年第47卷第1期

页      码：32-39页

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

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

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 

核心收录：

D　O　I：10.13232/j.cnki.jnju.2011.01.013

馆 藏 号：203118742...