云平台下图数据处理技术

针对Hadoop云平台下MapReduce计算模型在处理图数据时效率低下的问题,提出了一种类似谷歌Pregel的图数据处理计算框架--MyBSP.首先,分析了MapReduce的运行机制及不足之处;其次,阐述了MyBSP框架的结构、工作流程及主要接口;最后,在分析PageRank图处理算法原理的基础上,设计并实现了基于MyBSP框架的PageRank算法.实验结果表明,基于MyBSP框架的图数据处理算法与基于MapReduce的算法相比,迭代处理的性能提升了1.9~3倍.MyBSP算法的执行时间减少了67%,能够满足图数据高效处理的应用前景.     

基于分布式平台的大数据分析处理系统

设计并实现基于分布式平台的大数据分析处理系统,基于Spark平台用以处理大规模时间序列数据。系统框架主要分为存储层、算子层和算法层。在存储层,系统基于HDFS和Hive完成对大规模时间序列数据的组织和索引。在算子层,系统为用户提供了Spark平台上时间序列数据常用的基本操作,并允许用户直接使用这些算子实现自定义的时间序列相关处理算法。在算法层,系统实现Spark平台中一些常用的时间序列分析算法,包括时间序列相似度查询、聚类和预测,用户可以直接使用这些算法进行时间序列分析。通过对系统性能和功能的测试,验证了该系统的可行性和实用性。     

大数据处理平台比较与分析

虽然以MapReduce和Hadoop分布式系统(HDFS)为核心的Hadoop已在大规模数据密集的商业领域成功应用,但是对于多个并行操作之间重用工作数据集却表现不佳。作为对其的一种补充,本文介绍了Spark。首先介绍Hadoop的MapReduce与HDFS基本概念与设计思想,然后介绍了Spark的基本概念与思想,并且着重介绍了弹性分布式数据集RDD,并通过实验证明和分析对比了Hadoop与Spark。     

基于MapReduce的并行聚类算法设计与实现

针对目前聚类算法对大数据处理效率较低的问题,研究云平台上高效并行化的聚类算法十分必要。在HDFS分布式文件系统基础上,设计一种并行聚类算法P-ISODATA,利用MapReduce编程框架的执行机制将传统ISODATA聚类算法并行化,并在Map阶段之后加入Combine阶段以减少网络传输开销,进一步提高执行效率。实验从著名UCI机器学习库上选取若干数据集作为测试数据,分析了新并行算法P-ISODATA性能,结果表明基于P-ISODATA算法具有优良的加速比、数据伸缩率和扩展率,可以有效地应用于大规模数据的处理。     

基于并行图计算的社区划分方法

以图计算形式研究社交网络由来已久,但对于如何提升图计算应用于大规模社交网络的计算速度和扩展性,一直是研究的难点。谱图论的应用为社交网络在图计算方面的研究带来新的研究热点,谱图分割为社交网络社区划分带来基于结构的支撑。为了解决谱图论在处理大规模社交网络时存在计算缓慢、内存溢出等问题,本文提出了谱聚类改进算法结合矩阵方式在并行环境下的处理方法。首先,利用Spark对网络数据进行并行化预处理,将社交网络以图结构表示,再将图转化为Spark分布式稀疏矩阵。然后,将谱聚类改进算法在Spark环境下,实现并行化社交网络社区快速划分,并以分布式方式持久化存储源数据、中间计算数据和计算结果,提高图计算在社交网络中的可靠性。最后,通过实验证明并行化图计算方法能有效提高计算速度和扩展性,支持大规模社交网络的挖掘分析,实现并行算法下高并发、高吞吐的特点。     

基于二维划分的杰卡德相似系数批量计算效率优化

随着互联网用户及内容的指数级增长,大规模数据场景下的杰卡德相似系数计算对算法的效率提出了更高的要求。为提高算法的执行效率,对MapReduce架构下的算法执行缺陷进行了分析,结合Spark适用于迭代型及交互型任务的特点,基于二维划分算法将算法从MapReduce平台移植到Spark平台;并通过参数调整、内存优化等方法进一步提高了算法的执行效率。两组数据集分别在3组不同规模的集群上的实验结果表明,与MapReduce相比,Spark平台下的算法执行效率提高了4倍以上,能耗效率提升了3倍以上。     

基于Spark的MapReduce相似度计算效率优化

随着互联网的用户及内容呈指数级增长,大规模数据场景下的相似度计算对算法的效率提出了更高的要求。为提高算法的执行效率,对MapReduce架构下的算法执行缺陷进行了分析,结合Spark适于迭代型及交互型任务的特点,基于二维划分算法将算法从MapReduce平台移植到Spark平台;同时,通过参数调整、内存优化等方法进一步提高算法的执行效率。通过2组数据集分别在3组不同规模的集群上的实验表明,与MapReduce相比,在Spark平台下算法的执行效率平均提高了4.715倍,平均能耗效率只有Hadoop能耗的24.86%,能耗效率提升了4倍左右。     

基于HDFS+Spark的时空大数据存储与处理——以智慧无锡时空大数据为例

海量时空数据的高效存储、读写、处理与分析是当前地理信息科学领域的研究热点。本文对目前主流大数据技术产品进行了选取和融合,开展了基于HDFS+Spark的时空大数据存储、处理分析等方面的研究和探讨,以智慧无锡时空信息云平台为应用对象,搭建了一套时空大数据存储处理的集群平台,并通过具体应用实验,得到了时空数据存储、处理、挖掘的响应时间及可视化展示结果,证实了HDFS+Spark集群计算平台在解决时空大数据存储、处理、挖掘方面的有效性。     

MR-GSpar:一种基于MapReduce的大图稀疏化算法

图的稀疏化是图聚类分析中数据预处理的关键操作,已得到广泛的关注.针对图数据日益普及、规模不断增大的现状,提出了一种基于MapReduce的面向大规模图的稀疏化算法,即MR-GSpar算法.该算法在MapReduce并行计算框架的基础上,通过对传统的最小哈希(Minhash)算法的并行化改造,使其可在分布式的集群环境中实现对大规模图数据的高效稀疏化处理.真实数据集上的实验表明了该算法的可行性与有效性.     

云环境下基于数据流的k-means聚类算法

k-means算法是一种 最常用的基于划分的聚类算法。传统的集中式k-means算法已不能适应当前呈爆炸式增长的数据规模,设计分布式k-means算法成为了目前亟需解决的问题。现有分布式k-means算法基于MapReduce计算框架且没有考虑初始聚类中心的影响。由于每个MapReduce任务均需要读写分布式文件系统,导致MapReduce不能有效表达多个任务之间的依赖关系,因此提出了一种基于数据流的计算框架,该框架建立在MapReduce之上,将数据处理过程按照数据流图建模。在该框架的基础上,提出了一种高效的k-means算法,它采用基于多次采样的初始聚类中心选取方法来实现负载均衡及减少迭代次数。实验结果表明,该算法的可扩展性较好,且效率比现有算法高。     

云计算中Hadoop技术研究与应用综述

Hadoop作为当今云计算与大数据时代背景下最热门的技术之一,其相关生态圈与Spark技术的结合一同影响着学术发展和商业模式。首先介绍了Hadoop的起源和优势,阐明相关技术原理,如MapReduce,HDFS,YARN,Spark等;然后着重分析了当前Hadoop学术研究成果,从MapReduce算法的改进与创新、HDFS技术的优化与创新、二次开发与其它技术相结合、应用领域创新与实践4个方面进行总结,并简述了国内外应用现状。而Hadoop与Spark结合是未来的趋势,最后展望了Hadoop未来研究的发展方向和亟需解决的问题。     

基于开源Hadoop的矢量空间数据分布式处理研究

为实现大规模矢量数据的高性能处理,在开源项目Hadoop基础上,设计与开发了一个基于MapReduce的矢量数据分布式计算系统。根据矢量空间数据的特点,通过分析Key/Value数据模型及GeoJSON地理数据编码格式,构建了可存储于Hadoop hdfs的矢量数据Key/Value文本文件格式;探讨矢量数据的MapReduce计算过程,对Map数据分片、并行处理过程及Reduce结果合并等关键步骤进行了详细阐述;基于上述技术,建立了矢量数据分布式计算原型系统,详细介绍系统组成,并将其应用于处理关中地区1∶10万土地利用矢量空间数据,取得较好效果。     

An efficient parallel algorithm of N-hop neighborhoods on graphs in distributed environment

N-hop neighborhoods information is very useful in analytic tasks on large-scale graphs, like finding clique in a social network, recommending friends or advertising links according to one’s interests, predicting links among websites and etc. To get the N-hop neighborhoods information on a large graph, such as a web graph, a twitter social graph, the most straightforward method is to conduct a breadth first search (BFS) on a parallel distributed graph processing framework, such as Pregel and GraphLab. However, due to the massive volume of message transfer, the BFS method results in high communication cost and has low efficiency. In this work, we propose a key/value based method, namely KVB, which perfectly fits into the prevailing parallel graph processing framework and computes N-hop neighborhoods on a large scale graph efficiently. Unlike the BFS method, our method need not transfer large amount of neighborhoods information, thus, significantly reduces the overhead on both the communication and intermediate results in the distributed framework.We formalize the N-hop neighborhoods query processing as an optimization problem based on a set of quantitative cost metrics of parallel graph processing. Moreover, we propose a solution to efficiently load only the relevant neighborhoods for computation. Specially, we prove the optimal partial neighborhoods load problem is NP-hard and carefully design a heuristic strategy. We have implemented our algorithm on a distributed graph framework- Spark GraphX and validated our solution with extensive experiments over a number of real world and synthetic large graphs on a modest indoor cluster. Experiments show that our solution generally gains an order of magnitude speedup comparing to the state-of-art BFS implementation.     

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

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

基于Spark Streaming的流式并行文本校对

互联网的高速发展催生了海量网络文本,这对传统的串行文本校对算法提出了新的性能挑战。尽管近年来文本自动校对任务受到了较多关注,但相关研究工作多集中于串行算法,鲜有涉及校对的并行化。文中首先对串行校对算法进行泛化,给出一种串行校对的通用框架,然后针对串行校对算法处理大规模文本存在的耗时长的不足,提出3种通用的文本校对并行化方法:1)基于多线程的线程并行校对,它基于线程池的方式实现段落和校对功能的同时并行;2)基于Spark MapReduce的批处理并行校对,它通过RDD并行计算的方式实现段落的并行校对;3)基于Spark Streaming流式计算框架的流式并行校对,它通过将文本流的实时计算转为一系列小规模的基于时间分片的批处理作业,有效避免了固定开销,显著缩短了校对时延。由于流式计算兼有低时延和高吞吐的优势,文中最后选用流式校对来构建并行校对系统。性能对比实验表明,线程并行适合校对小规模文本,批处理并行适合大规模文本的离线校对,流式并行校对有效减少了约110s的固定时延,相比批处理校对,采用Streaming计算框架的流式校对取得了极大的性能提升。     

Spark环境下的并行模糊C均值聚类算法

针对聚类算法需要处理数据集的规模越来越大、时效性要求越来越高,对算法的大数据适应能力和性能要求更高的问题,提出一种在Spark分布式内存计算平台下的模糊C均值(FCM)算法Spark-FCM。首先对矩阵通过水平分割实现分布式存储,不同向量存储在不同节点;然后基于FCM算法的计算特点,设计了分布式和缓存敏感的常用矩阵操作,包括乘法、转置和加法等;最后基于矩阵操作和Spark平台特点,设计了Spark-FCM算法,主要数据结构采用分布式矩阵存储,具有节点间数据移动少和每个步骤分布式计算特点。通过在单机和集群环境下测试,算法具有良好的可扩展性,并可以适应大规模数据集,算法性能与数据量成线性关系,集群环境下性能比单机提高2~3倍。     

基于MapReduce模型的推测执行优化算法

作为数据中心大规模处理框架,MapReduce集群包含成百上千个节点,多采用推测执行的方法来有效解决并行计算中的掉队任务。针对集群中实时性需求较高并且任务量较小的目标作业,提出基于MapReduce模型的推测执行优化算法,其目的是在满足实时性需求的基础上尽量减少目标作业的完成时间。首先通过分析任务模型和时间模型,引入数学0-1规划模型,求得整体作业的完成时间最小;然后设计可以在多项式复杂度内完成的启发式算法,目的是在可用资源允许的范围内尽量逼近最优值;最后通过大量实验模拟验证算法的执行效果。     

基于子模式的关系数据到图数据ETL方法研究

图数据库在解决多层关系查询、社区发现等问题时性能优于关系数据库。然而目前大量的数据以关系数据的形式存储,如何高效完整地进行关系数据到图数据的ETL,即抽取、转换、加载,是图数据库应用领域研究的重要问题。国内外对该问题有了一些研究,但存在转换后的图数据质量不高、转换效率低、转换结果不利于分布式存储等问题。因此,提出基于子模式的关系数据到图数据ETL方法,改进原有ETL方法的流程和算法。该方法将关系数据库模式拆分为若干个子模式,并行进行ETL。不仅提高了ETL的效率,转换结果能满足图数据的分布式存储要求,也可以作为Spark GraphX计算框架的基础数据。最后,使用Java EE和Neo4j开发了原型系统,并进行了实验验证。结果表明,改进后的ETL方法获得了较已有方法更好的转化性能。