论文部分内容阅读
随着互联网技术的蓬勃发展、网络互动社区等新兴应用的日益丰富以及企业信息化建设的高速发展,互联网社区用户数量急剧膨胀,各种新的需求和应用形式不断涌现,企业每天产生的各种不同类型的数据已从过去的GB、TB级,以爆炸性的速度增长到PB量级。并且,在互联网应用、科学计算、商业智能等数据分析任务中,通常都需要对海量数据进行计算、分析与挖掘,以获得有价值的知识和信息。由于数据规模庞大,所以绝大部分计算都需要被分布在成百甚至上千台机器上并行执行。如何在大规模集群上高效地管理、分析海量数据已成为数据管理系统所面临的最严峻的挑战。许多复杂的数据分析任务都涉及复杂的连接条件,或者需要对多个关系表进行连接,因此在云计算平台上实现高效的连接算法具有很高的现实意义。然而,云计算平台的分布性使连接运算代价过高,这是一个迫切需要解决的问题。 本文首先分析了云计算环境中已有的theta连接算法,然后针对其中的问题进行分析,并提出一种基于划分的theta连接算法。该算法利用云计算架构并行计算的优势和特点,通过将连接任务近似平均地划分为多个子连接任务,并分布到各节点上并行计算,从而最大化利用云计算平台的并行计算能力。该算法通过对连接矩阵进行适当划分以尽可能减少各节点发送、接收及输出的元组数,从而最小化theta连接算法代价。随后,本文对云计算环境中已有的多表连接算法进行分析,并提出一种基于过滤器的多表连接算法。该算法同时对多个表进行连接以避免中间结果的产生,并通过提前统计连接属性的取值分布从而减少不必要的元组复制与数据传输。在TPC-H模拟数据上的实验结果表明,本文提出的两个算法具有高效的性能及良好的可扩展性,与云计算环境中多种已有算法相比,显著提高了云计算环境中theta连接以及多表连接运算的效率。