论文部分内容阅读
随着数据获取方式的多样性,数据挖掘和机器学习使用的数据集规模越来越大。而随着时间的推移,在大规模数据集的基础上,新的数据也在不停的加入进来,同时,数据集中已有的记录也会被修改或者删除,即数据集发生增量变,由此导致上一次挖掘出的结果过时。数据集一般发生增量变化时,我们需要对整个数据集重新进行挖掘,得到实时结果,由此浪费大量的计算资源。为了提高效率,使用增量处理技术解决数据发生增量变化是一个有效的方法。增量处理技术是使用上一次计算保存的状态,只重新处理发生增量变化的数据。MapReduce是现流行的并行处理大数据的框架,由于其简单易用成为主流处理大数据的工具。但是MapReduce不支持增量处理数据,需要重新处理整个数据才能得到实时结果。在本论文,我们提出增量处理技术,并在MapReduce上扩展,实现incr-MapReduce计算模型。本文主要贡献如下：(1)本文提出了在key-value层面上做增量计算的方法,并设计了一种新的文件模型MRBGraph,保存细粒度的计算状态。Incr-MapReduce根据增量数据从MRBGraph文件中匹配记录,做增量计算并更新MRBGraph文件。(2)提出增量处理技术,incr-MapReduce计算模型上不但支持批处理算法做增量计算,而且支持迭代算法做增量计算。incr-MapReduce做迭代算法的增量计算时,从上一次计算的收敛结果开始做增量迭代计算,同时使用变化传播控制技术,能有效控制下一次迭代参与增量计算的记录的范围。(3)由于incr-MapReduce在做增量计算时,MRBStore需要频繁从MRBGraph文件中读取数据和更新MRGraph文件。本文使用了索引和缓冲优化技术,减少操作MRBGraph文件的I/O次数。本文使用真实数据集,在incr-MapReduce、MapReduce、Haloop和iMapReduce四个框架上执行PageRank, GIMV、KMeans和Apriori算法,展示incr-MapReduce的性能。同时通过实验验证incr-MapReduce的优化成果。