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

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

作　　者：胡东明 刘旭敏[1] 徐维祥[2] Hu Dongming;Liu Xumin;Xu Weixiang(College of Information Engineering,Capital Normal University,Beijing 100048,China;College of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

机构地区：[1]首都师范大学信息工程学院,北京100048 [2]北京交通大学交通运输学院,北京100044

出　　处：《计算机测量与控制》2018年第8期238-242,共5页Computer Measurement &Control

基　　金：国家自然科学基金(61672002);北京市长城学者项目(CIT&TCD20170322)

摘　　要：针对传统Top-k连接查询算法在处理海量数据时的时效问题,提出一种基于MapReduce框架的负载均衡的并行Top-k连接查询算法(P-TKJ);使用直方图形式来存储数据,有助于提高CPU的利用率;同时融入了提前终止策略和磁盘数据的选择性访问,以便提高对HDFS数据访问的性能;另外,融入了数据过滤和基于最长处理时间优先(LPT)算法的负载均衡策略来减少和均衡Reduce任务,以此设计出高效的并行Top-k连接算法;一个集群实验结果表明,该方法能够有效缩短算法的执行时间。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,data filtering and load-balancing strategies based on the longest processing time priority（LPT）algorithm are incorporated to reduce and equalize reduce tasks,so that to design an efficient parallel Top-k connection algorithm.A cluster experiment shows that this method can shorten the execution time of the algorithm effectively.

关 键 词：Top-k连接查询 MAPREDUCE框架 数据过滤 负载均衡 执行时间 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]