MapReduce框架下一种负载均衡的Top-k连接查询算法

A Load Balancing Top-k Join Query Algorithm in MapReduce Framework

摘要:

针对传统Top-k连接查询算法在处理海量数据时的时效问题,提出一种基于MapReduce框架的负载均衡的并行Top-k连接查询算法(P-TKJ)。使用直方图形式来存储数据,有助于提高CPU的利用率。同时融入了提前终止策略和磁盘数据的选择性访问,以便提高对HDFS数据访问的性能。另外,提出了一种基于最长处理时间优先(LPT)算法的负载均衡策略来均衡Reduce任务,以此设计出高效的并行Top-k连接算法。一个集群实验结果表明,该方法能够有效缩短算法的执行时间。

Abstract:

For the issues that the time efficiency problem of traditional Top-k join algorithm when dealing with massive data, a load-balanced parallel Top-k join query algorithm (P-TKJ) based on MapReduce framework is proposed. It used histograms to store data helps to increase CPU utilization. An early termination strategy and disk data selective access mechanism is incorporated to improve the performance of HDFS data access. In addition, a load balancing strategy based on the longest processing time-first (LPT) algorithm is proposed to balance the Reduce tasks, so as to design an efficient parallel Top-k join algorithm. A cluster experiment shows that this method can shorten the execution time of the algorithm effectively.