李俊丽

(晋中学院 计算机科学与技术系，山西 晋中 030619)

0 引 言

随着大数据时代的到来，数据量以惊人的速度增长。大数据应用的出现给数据处理带来了巨大的挑战[1,2]，越来越多的高效并行计算平台，如MapReduce[3]和Spark[4-6]，被广泛采用来处理大数据。互信息是对两个随机变量之间共享的信息量的度量。互信息的计算量很大，特别对于处理大规模的类别数据。互信息可以广泛应用于数据挖掘[7,8]算法中。为了提高互信息计算的效率，Spark内存计算模型是最好的选择，但要面对Spark数据倾斜的性能优化问题。针对Spark中的数据倾斜问题，近年来提出了很多算法和模型。例如，文献[9]提出了Spark平台上基于特征分组的并行离群挖掘算法。SCID算法[10]设计了一种Pond-sampling算法来收集数据分布信息，并对总体数据分布进行估计。在数据划分过程中，SCID实现了Bin-packing算法对Map任务的输出进行桶状处理。此外，在分区过程中，还会进一步切割大型分区。SP-Partitioner算法[11]将到达的批次数据作为候选样本，在系统抽样的基础上选择样本，预测中间数据的特征。该方法根据预测结果生成参考表，指导下一批数据的均匀分布。文献[12]优化了笛卡尔(笛卡儿积)算子。由于计算笛卡尔积需要连接操作，因此可能会出现数据倾斜。文献[13]提出了SASM(Spark adaptive skew mitigation)，通过将大分区迁移到其它节点，同时平衡各任务之间的大小，来缓解数据倾斜问题。与这些现有的方法不同，DVP算法针对文献[9]中并行互信息计算中出现的数据倾斜问题进行研究和改进。DVP算法探索了数据虚拟划分，其中虚拟前缀附加在一个大分区中的所有键之前，然后是一个辅助散列。……