论文部分内容阅读
云计算是一种全新的IT服务模式,向大量用户透明地提供按需、弹性、高效用的多租户服务。云计算凭借其超大规模存储能力、超大规模分布式并行计算能力、较高的可靠性和可用性等特点赢得了科学界和工业界广泛关注并在其大力推动下,取得了巨大的发展。与此同时一个全新的互联网服务模式SNS (Social Networking Sites,社交网站)也得到迅速发展,一大批社交网站如Renren、Facebook等快速崛起。每天这些网站都会产生大量的用户数据,如何从这些用户数中发现具有商业价值的深层次有用信息日益成为这些网站重点关注的方向。SNA (Social Network Analysis,社会网络分析)是解决上述问题的有效手段,并成为众多学者研究的重点。但是现代SN (Social Network,社会网络)往往都是几百万甚至上千万的超大规模数据集,如何处理大规模的社会网络数据集成为传统的社会网络分析面临的一个较为严峻的挑战。为了对海量数据集进行社会网络分析,本文提出了X-RIME:种将强大的云计算平台Hadoop和社会网络分析法相结合的大规模社会网络分析工具,具有良好的扩展性和通用性。构建在HDFS (HADOOP Distributed File System, HADOOP分布式文件系统)之上的X-RIME数据模型以及构建在HADOOP MapReduce编程模型之上的X-RIME算法模型使X-RIME同时具备了海量数据的存储与处理能力。与此同时,基于X-RIME数据模型和算法模型开发的X-RIME算法库包含十几种MapReduce化的分布式社会网络分析算法,这些算法可以部署在成百上千台普通PC机上,是X-RIME大规模社会网络分析的核心。X-RIME算法库中的分布式MST (Minimum Spanning Tree,最小生成树)算法是社会网络分析法中较为重要的算法,在计算最优传递问题方面有着广泛的应用。本文首先对X-RIME的总体架构进行介绍,接着对X-RIME中数据模型和算法模型的设计与实现进行介绍,然后对X-RIME算法库中最为复杂和重要的分布式最小生成树算法的设计与实现进行介绍,最后给出X-RIME中分布式最小生成树算法的功能测试情况。