基于图覆盖的大数据全比较数据分配算法

doi:10.3969/j.issn.1000-3428.2018.04.003

计算机工程

所属专题：大数据专题；

基于图覆盖的大数据全比较数据分配算法

高燕军¹,张雪英¹,李凤莲¹,田玉楚^1,2

(1.太原理工大学信息工程学院,山西晋中 030600;2.昆士兰科技大学电机工程及计算机科学学院,澳大利亚布里斯班4001)

收稿日期:2017-03-10 出版日期:2018-04-15 发布日期:2018-04-15
作者简介:高燕军(1990—),男,硕士,主研方向为大数据、分布式计算;张雪英(通信作者),教授、博士、博士生导师;李凤莲,教授、博士;田玉楚,教授、博士、博士生导师。
基金资助:
山西省研究生联合培养基地人才培养项目(2017JD16);山西省优秀人才科技创新项目(201605D211021);2016年太原理工大学教改项目(24)。

Data Allocation Algorithm for Large Data with All-to-all Comparison Based on Graph Covering

GAO Yanjun¹,ZHANG Xueying¹,LI Fenglian¹,TIAN Yuchu ^1,2

(1.College of Information Engineering,Taiyuan University of Technology,Jinzhong,Shanxi 030600,China; 2.School of Electrical Engineering and Computer Science,Queensland University of Technology,Brisbane 4001,Australia)

Received:2017-03-10 Online:2018-04-15 Published:2018-04-15

摘要/Abstract

摘要： 在对大数据全比较问题进行分布式处理的过程中,现有的数据分配策略较少考虑比较任务和数据之间的特殊依赖关系,导致存储效率下降、任务分配不均衡。为此,提出基于图覆盖的数据分配算法。通过理论分析将大数据全比较的数据分配问题归纳为图覆盖问题,在此基础上构造图覆盖的最优解,根据特解分配数据。实验结果表明,与基于Hadoop的数据分配策略相比,该算法可确保比较任务具有100%的数据本地性,使节点之间达到负载均衡,并且提高存储节约率和整体计算性能。

关键词: 分布式计算, 大数据, 全比较, 数据分配, 图覆盖

Abstract: In the process of distributed processing of all-to-all comparison problem for large data,the existing data allocation strategies think less of the special dependency between the comparison task and the data,which lead to the low storage efficiency and imbalanced task allocation.Aiming at this problem,a Data Allocation Algorithm Based on Graph Covering(DAABGC) is proposed.Firstly,the problem of data allocation for large data is summarized as the problem of graph covering by theoretical analysis.Then,the optimal solution of several graph covering is constructed successfully and the data are allocated according to the special solution.Experimental results show that,compared with the Hadoop-based data allocation strategy,the proposed algorithm ensures that the comparison task has 100% data locality and load balancing between nodes.It also improve storage saving rate and overall computing performance.

Key words: distributed computing, big data, all-to-all comparison, data allocation, graph covering

中图分类号:

TP301.6

高燕军,张雪英,李凤莲,田玉楚. 基于图覆盖的大数据全比较数据分配算法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2018.04.003.

GAO Yanjun,ZHANG Xueying,LI Fenglian,TIAN Yuchu. Data Allocation Algorithm for Large Data with All-to-all Comparison Based on Graph Covering[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2018.04.003.

http://www.ecice06.com/CN/Y2018/V44/I4/17

参考文献

参考文献［1］ZHANG Y F,TIAN Y C,KELLY W,et al.Application of simulated annealing to data distribution for all-to-all comparison problems in homogeneous systems［C］//Proceedings of ICONIP’15.Berlin,Germany:Springer,2015:683-691. ［2］HAO B,QI J,WANG B.Prokaryotic phylogeny based on complete genomes without sequence alignment［J］.Modern Physics Letters B,2011,17(3):91-94. ［3］PHILLIPS P J,FLYNN P J,SCRUGGS T,et al.Overview of the face recognition grand challenge［C］//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C.,USA:IEEE Computer Society,2005:947-954. ［4］SKABAR A,ABDALGADER K.Clustering sentence-level text using a novel fuzzy relational clustering algorithm［J］.IEEE Transactions on Knowledge and Data Engineering,2013,25(1):62-75. ［5］丁三军,薛宇,王朝霞,等.基于模糊数据挖掘的虚拟环境主机故障预测［J］.计算机工程,2015,41(11):202-206. ［6］WONG A K,LEE E S.Aligning and clustering patterns to reveal the protein functionality of sequences［J］.IEEE/ACM Transactions on Computational Biology and Bioinformatics,2014,11(3):548-560. ［7］FAISAL F E,ZHAO H,MILENKOVIC T,et al.Global network alignment in the context of aging［J］.IEEE/ACM Transations on Computational Biology and Bioinformatics,2015,12(1):40-52. (下转第27页) (上接第22页) ［8］KRISHNAJITH A P D,KELLY W,HAYWARD R,et al.Managing memory and reducing I/O cost for correlation matrix calculation in bioinformatics［C］//Proceedings of IEEE Symposium on Computational Intelligence in Bioinfor-matics and Computational Biology.Washington D.C.,USA:IEEE Press,2013:36-43. ［9］ANATHTHA P D K,KELLY W,TIAN Y C.Optimizing I/O cost and managing memory for composition vector method based on correlation matrix calculation in bioinformatics［J］.Current Bioinformatics,2014,9(3):234-245. ［10］ZHANG Y F,TIAN Y C,KELLY W,et al.A distributed com-puting framework for all-to-all comparison problems［C］//Proceedings of IECON’14.Washington D.C.,USA:IEEE Press,2014:2499-2505. ［11］ALTSCHUL S F,GISH W,MILLER W,et al.Basic local alignment search tool［J］.Journal of Molecular Biology,1990,215(3):403-410. ［12］THOMPSON J D,GIBSON T J,HIGGINS D G.Multiple sequence alignment using ClustalW and ClustalX［EB/J］.Current Protocols in Bioinformatics,2002,2(3). ［13］栾亚建,黄翀民,龚高晟,等.Hadoop平台的性能优化研究［J］.计算机工程,2010,36(14):262-263. ［14］CHEN Q,WANG L,SHANG Z.MRGIS:a MapReduce-enabled high performance workflow system for GIS［C］//Proceedings of the 4th IEEE International Conference on e-science.Washington D.C.,USA:IEEE Computer Society,2008:646-651. ［15］程苗,陈华平.基于Hadoop的Web日志挖掘［J］.计算机工程,2011,37(11):37-39. ［16］GILLETT B E,MILLER L R.A heuristic algorithm for the vehicle-dispatch problem［J］.Operations Research,1974,22(2):340-349. ［17］LIN S,KERNIGHAN B W.An effective heuristic algorithm for the TSP［J］.Operations Research,1973,21(2):498-516. ［18］THITE S.On covering a graph optimally with induced subgraphs［J］.Computing,2006,44(1):1-6. ［19］KRISHNAJITH A P D,KELLY W,HAYWARD R,et al.Managing memory and reducing I/O cost for correlation matrix calculation in bioinformatics［C］//Proceedings of IEEE Symposium on Computational Intelligence in Bioinformatics and Computational Biology.Washington D.C.,USA:IEEE Press,2013:36-43. 编辑金胡考

[1]	王新迪, 杨夙, 张思源, 罗午阳, 李杰, 刘辉. 基于时空大数据与卫星图像的城市火灾风险预测[J]. 计算机工程, 2023, 49(6): 242-249.
[2]	张基, 谢在鹏, 毛莺池, 徐媛媛, 朱晓瑞, 李博文. MapReduce框架下结合分布式编码计算的容错算法[J]. 计算机工程, 2021, 47(4): 173-179.
[3]	郭威, 谢光伟, 张帆, 李敏. 一种分布式存储系统拟态化架构设计与实现[J]. 计算机工程, 2020, 46(6): 12-19.
[4]	王芝辉, 王晓东. 基于神经网络的文本分类方法研究[J]. 计算机工程, 2020, 46(3): 11-17.
[5]	张海军, 陈映辉. 基于类图像处理与向量化的大数据脚本攻击智能检测[J]. 计算机工程, 2020, 46(3): 129-137,143.
[6]	王重仁, 王雯, 佘杰, 凌晨. 融合深度神经网络的个人信用评估方法[J]. 计算机工程, 2020, 46(10): 308-314.
[7]	白玲玲, 宁振虎, 薛菲, 杨永丽. 隐马尔可夫模型在恶意域名检测中的应用[J]. 计算机工程, 2019, 45(9): 161-168.
[8]	赵宝琦, 李卫东, 邹佳恒, 林韬, 颜田. 基于MPI的分布式数据处理系统[J]. 计算机工程, 2019, 45(7): 20-25.
[9]	张璐, 朱海婷. 一种高效的分布式水军群组检测算法[J]. 计算机工程, 2019, 45(7): 6-12.
[10]	张玺君, 袁占亭, 张红, 高玮军, 张恩展. 交通轨迹大数据预处理方法研究[J]. 计算机工程, 2019, 45(6): 26-31.
[11]	钱雪忠,姚琳燕. 面向稀疏高维大数据的扩展增量模糊聚类算法[J]. 计算机工程, 2019, 45(6): 75-81.
[12]	任良育,赵成萍,严华. 基于任务复制与冗余消除的多核调度算法[J]. 计算机工程, 2019, 45(5): 59-65.
[13]	蒋猛,禹明刚,王智学. 多策略自适应大规模本体映射算法[J]. 计算机工程, 2019, 45(3): 14-19.
[14]	张伟,王志杰. 分布式环境下时态大数据的连接操作研究[J]. 计算机工程, 2019, 45(3): 20-25,31.
[15]	高军,黄献策. 基于Hadoop平台的相关性权重算法设计与实现[J]. 计算机工程, 2019, 45(3): 26-31.

选择文件类型/文献管理软件名称

选择包含的内容

基于图覆盖的大数据全比较数据分配算法

Data Allocation Algorithm for Large Data with All-to-all Comparison Based on Graph Covering

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

基于图覆盖的大数据全比较数据分配算法

Data Allocation Algorithm for Large Data with All-to-all Comparison Based on Graph Covering

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价