论文部分内容阅读
数据溯源(Data Provenance)是对目标数据衍演变过程的追溯、重现与展示。由于溯源系统通过监控系统调用,收集文件和进程之间的依赖关系,数据溯源在追踪数据的演变及验证数据的可信性等方面具有独特的优势,数据溯源被广泛应用于多种领域。为了保证数据的可溯源性,现有溯源系统的溯源数据涵盖了规模巨大的细粒度依赖和生成关联,因而溯源数据的规模往往远大于目标数据。规模巨大的溯源数据不仅严重降低了溯源查询的效率,使其存储、计算和管理成本激增,还因数据关联过于复杂、细密,使溯源结果的理解和从中获取关键溯源特征更加困难,因而极大降低了数据溯源的质量。针对这一问题,本文从溯源数据粗粒度化角度出发,通过对溯源数据进行聚类,将细粒度的溯源数据与溯源关联组合成粗粒度溯源数据,并保持数据的关键溯源特征,以此实现对目标数据的高效溯源。为此,本文的主要工作包括:(1)提出了基于节点中心性的溯源数据全局聚类方法。该方法首先定义节点中心性的计算方法,通过比较有直接依赖关系的节点的中心性,衡量相邻节点间相似度,实现有语义意义的溯源数据全局聚类;最后基于划分结果,实现溯源概括图的粗粒度溯源。(2)提出了基于节点疏离性的溯源数据局部聚类方法。该方法首先定义了节点疏离性的计算方法,从目标节点出发广度优先遍历溯源图,筛选出与目标节点关系紧密的节点,实现关键数据的局部聚类。(3)由于时间戳属性体现了溯源数据的溯源热度,本文提出基于时间序列的溯源数据可变粒度聚类方法。该方法首先给出一种时域划分方法,在基于中心性的溯源数据全局聚类结果的基础上,合并位于同一时域内的簇,实现基于时域的溯源数据可变粒度聚类。本文创新性主要体现在:(1)提出基于节点中心性的溯源数据全局聚类方法。与已有方法相比,该方法实现了具有语义意义的溯源数据全局聚类。(2)提出基于节点疏离性的溯源数据局部聚类方法。该方法可有效过滤掉与目标节点具有较大疏离性的溯源数据,保留具有强关联特征的溯源数据,有效地实现了溯源数据的粗粒度化。(3)提出基于时域的溯源数据可变粒度聚类方法。通过合理划分时域,在不同时域内对节点的聚类粒度调整,实现对不同热度的溯源数据可变粒度聚类。本文的实验数据是PASS模型的标准溯源数据集。实验验证了本文提出的溯源数据聚类方法的可行性与有效性。