论文部分内容阅读
随着互联网的发展与普及，传统的数据库技术已不能满足海量数据分析处理的新要求。连接是数据分析的重要手段，对大规模数据进行预处理，可以减少连接时不必要的处理开销。然而现有的基于MapReduce的连接预处理需要对数据集进行多次遍历，对于大规模数据集而言磁盘的开销很大，其更适合于对等式连接进行预处理，因此不能满足不等式连接预处理的需要。 基于MapReduce的不等式连接预处理方法（PPM），只需要对数据集进行一次读取并分析，可以减少不等式连接map阶段的输出，从而节省网络通信的数据量。PPM方法结合MapReduce编程模型的特点，在预处理的map阶段统计每个数据块的连接属性值的范围，在reduce阶段得到各个数据集连接属性的最小值和最大值，并根据它们的大小关系生成过滤状态表，并得到相应的过滤区间。在不等式连接的map阶段，忽略不符合过滤区间范围的记录，只传输符合条件的记录。同时，设计了基于集群感知的任务分配方法，根据不等式连接的开销模型和集群环境对任务完成效率的影响，得到一个当前环境下使得开销模型最小的Reduce任务数量。 实验结果表明，相比于没有引入预处理方法的不等式连接的处理时间，预处理方法的额外开销在4％之内；与基于直方图统计的M-Bucket-I算法相比较，使用基于PPM的1-Bucket-Theta算法的不等式连接作业的完成时间平均降低了34％。预处理方法在数据集的交集不为全集的情况下，能有效地过滤冗余数据；在数据集之间交集为空的情况下能直接节省整个不等式连接作业的开销。