大规模动态演化图的存储与分析系统研究

发布时间：2017-12-18 20:29

  本文关键词：大规模动态演化图的存储与分析系统研究

  更多相关文章： 动态演化图 平台系统 图分析 图存储 分布式系统

【摘要】：图数据通过顶点和边的结构表达实体间的相互联系。图数据的分析计算技术,也称图挖掘技术,是通过分析实体间联系,获得关于实体的性质、特征等重要信息的一项技术,正广泛地应用于信息检索、社交分析、生物计算等多个领域。本文所述的图存储分析系统是支持图分析计算的平台系统。它利用抽象的编程接口支持图分析算法的高效实现,利用优化的系统设计提供高效的算法执行,从而实现超大规模的图数据分析。在大数据时代的今天,大规模图存储与分析系统及其相关技术已经成为一个重要的研究方向。 而近年来,随着社交网络媒体、移动互联网等新型应用的普及,信息的组织方式、传播方式等,正发生着新的变化——信息呈现出更为明显的动态化特征。随着这一变化,捕捉了数据时序特征的动态演化图,其数据挖掘分析的价值正受到更多的重视,并随着演化图数据分析理论研究的同步深入,逐渐成为一个新的发展趋势。然而现有的图存储与分析平台系统针对的是静态图,并不适合动态演化图。因此,本文研究问题的重点,就在于：如何针对动态演化图分析这一类新的应用,设计并实现高效的大规模存储分析系统。 我们通过分析,将动态演化图相关的应用主要总结为：(1)分析动态演化图准实时状态和(2)分析动态演化图长期变化趋势两类。前者着重于分析动态演化图的最新状态,而后者着重于分析动态演化图的长期历史变化过程。在文中,我们为这两类应用算法,设计并实现了动态演化图存储、分析系统。该系统以图数据的实时变化作为输入,产生具有全局一致性的图数据更新,并用于动态演化图准实时状态分析；同时,它会将接收到的时序数据存储下来,重新组织并用于动态演化图长期变化趋势分析。在系统的设计实现中,我们将针对动态演化图准实时状态分析和动态演化图长期变化趋势分析的两部分功能分别抽象成以下两个子问题加以解决： 一、动态演化图在线分析的系统问题。在该问题中,大量新的图数据高速产生,应用需要不断地对最新的图数据进行在线处理,从而得到准实时的分析结果。然而实现准实时分析,数据的处理延迟需要足够低。此外,在分布式环境下,还需保持动态数据访问的全局一致性,从而保证分析结果的正确性。为此,我们设计了动态演化图在线分析子系统。该子系统的架构的设计考虑了处理流程的耦合关系,对图数据存储和分析计算进行了解耦。它选用了一个“时段提交”技术来处理图更新,并为系统的计算部分提出了全新的增量计算模型,大大降低分析计算的延迟。我们完成了该系统的工程实现,并在1亿条真实推特文本数据上进行了包括争议话题探测、近似最短路径计算、用户排序等多种应用的测试。利用40台机器组成的集群,我们获得了10万每秒的推文处理速率,并保持2.5分钟以内的数据延迟,满足了我们最初设定的“远超推文的产生速率”的性能要求。 二、动态演化图离线分析的系统问题。在该问题中,系统需要保存动态演化图的长期历史数据,并支持动态演化图长期变化趋势的离线分析。相对于静态图分析处理的是单一的静态图,长时间跨度动态演化图分析面对的是多个时间点对应的一系列静态图。更大的数据量带来更高的处理开销,因而系统分析计算的性能非常重要。此外,系统还需要为动态演化图复杂多变的存取模式提供高效的访问性能,为分析性能提供保障。为此我们在文中提出了动态演化图离线分析子系统。它的副本相异数据排布技术利用数据中心多个数据备份的特点,为动态演化图不同类型的访问提供不同针对性的数据组织方式,从而在复杂多变的存取访问中获得更好的数据存取性能;利用全新的局部性感知分批调度技术——局部性分批调度,我们提高了分析计算中高速缓存的利用率并减少了数据同步的开销,极大地改善了长时间跨度动态演化图分析的整体性能。在实际大规模动态演化图进行的多项应用测试结果表明,该系统能够提供相对于目前数据库系统高达5倍的存取性能,以及相对于静态图分析平台高达10倍的性能。 综上,本论文所述的研究,为图分析平台的发展进步,特别是动态演化图数据分析平台领域,做出了积极的探索。
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP333

【共引文献】

中国期刊全文数据库 前10条

1 郎波;张博宇;;面向大数据的非结构化数据管理平台关键技术[J];信息技术与标准化;2013年10期

2 邵景峰;崔尊民;王进富;白晓波;;大数据下纺织制造执行系统的构建[J];纺织器材;2013年06期

3 张亚楠;谭跃生;;基于MapReduce的并行遮盖文本聚类算法[J];内蒙古科技大学学报;2013年03期

4 周国亮;朱永利;王桂兰;;CC-MRSJ:Hadoop平台下缓存敏感的星型联接算法[J];电信科学;2013年10期

5 刘喜文;郑昌兴;王文龙;汤刚强;;构建数据仓库过程中的数据清洗研究[J];图书与情报;2013年05期

6 杨震;徐敏捷;刘璋峰;秦达;姚晓辉;;语音大数据信息处理架构及关键技术研究[J];电信科学;2013年11期

7 潘善亮;茅琴娇;韩露;;一种基于虚拟社交化的Web服务发现方法研究[J];电信科学;2013年12期

8 王鹏;黄焱;刘峰;安俊秀;;大数据技术中计算与数据的协作机制[J];成都信息工程学院学报;2014年01期

9 杜政颉;王鹏;黄焱;郎福通;;一种基于Storm编程模型的迭代Topology方案[J];成都信息工程学院学报;2014年01期

10 范飞;黄文明;邓珍荣;;Oozie工作流在Mahout分布式数据挖掘中的应用[J];桂林电子科技大学学报;2014年01期

中国重要会议论文全文数据库 前6条

1 乔媛媛;刘芳;凌艳;尹劲松;;云计算环境下MapReduce的资源建模与性能预测[A];2013年全国通信软件学术会议论文集[C];2013年

2 徐子伟;张陈斌;陈宗海;;大数据技术概述[A];系统仿真技术及其应用学术论文集（第15卷）[C];2014年

3 Xiaoguang Han;Jigang Sun;Wu Qu;Xuanxia Yao;;Distributed Malware Detection based on Binary File Features in Cloud Computing Environment[A];第26届中国控制与决策会议论文集[C];2014年

4 陈佐旗;余柏蒗;吴健平;;基于GPU通用计算的遥感数据处理——以计算地表太阳辐射值为例[A];第十八届中国环境遥感应用技术论坛论文集[C];2014年

5 白永超;付伟;辛阳;;基于Hadoop和Nutch的分布式搜索引擎研究与仿真[A];第十九届全国青年通信学术年会论文集[C];2014年

6 李超越;徐国胜;;Hadoop公平调度算法的改进[A];第十九届全国青年通信学术年会论文集[C];2014年

中国博士学位论文全文数据库 前10条

1 刘馨月;Web挖掘中的链接分析与话题检测研究[D];大连理工大学;2012年

2 马飞;云数据中心中虚拟机放置和实时迁移研究[D];北京交通大学;2013年

3 乐承毅;企业知识与员工知识贡献度集成评价方法及应用研究[D];浙江大学;2013年

4 孙甲申;基于主题模型和随机游走的标签技术研究[D];北京邮电大学;2013年

5 张鹏;数据中心网络的流量管理和优化问题研究[D];北京邮电大学;2013年

6 孙茂华;安全多方计算及其应用研究[D];北京邮电大学;2013年

7 李健;云计算环境下最小化运营开销的调度技术研究[D];北京邮电大学;2013年

8 龚书;抽取式多文档文摘的文本表示研究[D];北京交通大学;2013年

9 张帆;认知可重构的高效能Web服务体系结构研究[D];解放军信息工程大学;2013年

10 尹莉;基础数学领域作者合作网络实证分析[D];西北大学;2013年

中国硕士学位论文全文数据库 前10条

1 耿玉娇;MapReduce中基于抽样技术的倾斜问题研究[D];大连海事大学;2013年

2 芮虎;比价购物平台中网络爬虫的设计与实现[D];华东理工大学;2013年

3 王梓;林产品贸易信息用户兴趣模型及个性化搜索[D];北京林业大学;2013年

4 牛雷;分布式多媒体平台中视频搜索技术的研究与应用[D];北京邮电大学;2013年

5 林哲;面向行业的信息融合原型系统的研究与实现[D];北京邮电大学;2013年

6 万德稳;藏文搜索和搜索结果聚类研究及系统实现[D];西南交通大学;2013年

7 阎正喜;H基金公司网上交易系统安全问题研究[D];西南交通大学;2013年

8 颜志博;基于用户反馈的关系数据库关键词搜索技术研究[D];黑龙江大学;2012年

9 张婧;面向云计算运营管理的资源预测模型[D];西北大学;2013年

10 黄佳;比较购物搜索引擎的研究与应用[D];武汉理工大学;2013年

，

本文编号：1305529