描述性图查询设计及其在MapReduce框架中的实现

来源 :北京大学 | 被引量 : 0次 | 上传用户:nimakule119
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
随着社交网络分析、生物信息网络分析、交通导航等新兴应用的快速增长,不同领域出现了规模庞大、内部结构复杂、查询需求多样的大图数据。传统的单机计算模式难以满足大图数据管理需求,利用分布式框架来对大图进行管理成为不可避免的趋势。尽管现有的分布式计算框架能够减轻用户实现图查询的代价,但是对于普通用户来说,在分布式环境中编写复杂的图操作程序仍然是非常困难的。此外,为了提高分布式程序的执行性能,用户不得不对底层分布式平台进行深入的研究和学习。  为了减轻用户利用分布式框架管理大图的负担,本文扩展了传统的Datalog查询,设计了一种描述性的图查询语言GLog,用户通过GLog可以简洁地表达查询任务。GLog查询引擎会将用户的查询翻译成一系列MapReduce作业,并提交给Hadoop平台运行。本文的主要贡献如下:  1.设计了一种能够结合关系数据与图数据二者优势的数据模型RG(Relational-Graph)表。基于RG表设计了一种描述性图查询语言GLog,GLog保持了传统Datalog语言的简洁性,同时增加了对嵌套数据和显示数据流控制的支持,还引入了更多的内嵌函数。  2.提出了一种将GLog查询翻译为一系列MapReduce作业的方法。该方法首先根据GLog规则在RG表上定义了一系列操作,然后为查询建立执行计划,最后根据翻译模版将查询计划翻译为MapReduce作业。  3.设计了一系列优化翻译规则来减少翻译生成的MapReduce作业数目。在翻译过程中,通过合并操作以及重写迭代过程可以显著地减少作业数目,提高查询执行的效率。  4.实现了基于Hadoop平台的原型系统,并在人工图和真实图数据上进行了大量测试。  实验结果表明,本文提出的GLog语言不仅能够简洁地表达多种图分析任务,而且还具有良好的性能和可拓展性。  
其他文献
支持向量机是近些年发展起来的一种新的机器学习的方法。它以统计学习理论为基础,能够较好的解决小样本的学习问题。由于其出色的学习和推广性能,支持向量机已经被应用到许多方
网络技术的迅速发展,给人们的工作、生活带来便利,但网络攻击事件频繁发生、网络病毒肆意泛滥,各种不安全的因素所带来负面影响日益强烈.电子邮件服务作为网络应用最广、最早
软硬件协同设计是嵌入式系统设计的一种方法,形式化分析和验证方法作为软硬件协同设计方法的重要部分得到了广泛的研究和应用.作为IEEE标准,Verilog HDL硬件描述语言被广泛应
随着能源日益紧缺,节能已成为国家和企业的迫切要求。建筑能耗作为“三大能耗”之一,即是能耗的重要部分,也是污染的主要来源。建筑能源管控系统对整个建筑的所有公用机电设备,包
数字信息资源的加工和整理是数字图书馆建设的一个重要方面,为了使大量的文本型文献以一个更加有效的方式组织和利用,自动标引的概念被提出.自动标引技术可以自动提取表示文
随着智能卡应用的不断推广,不同行业、不同领域对智能卡的需求都日益增加,仅仅适用于某一种应用的单应用卡已不再能够满足实际应用的需求.这是因为,为了实现多种应用用户不得
论文主要对协作型防火墙的包过滤和通信安全进行设计与实现.包过滤是防火墙的基本功能,通信安全是防火墙进行网络安全保护的前提条件.论文通过下面的方法,设计与实现协作型防
随着中国加入WTO和2008年奥运会的临近,我国政府的职能需要由管理型向服务型过渡,电子政务成为中国政务改革最核心的内容之一。综合资源信息服务平台作为政府部门面向公众提供
利用离线大数据统计分析的方法进行自然语言处理任务的研究是目前非常有潜力的一种研究范式,尤其是Google,Twitter等大公司在这类应用上的成功经验,引领了目前大数据研究的浪潮
该文主要进行了一幅未知文件格式的军用数字地图的逆向工程分析,并在此基础上开发出了基于MFC的ActiveX地图控件.该文针对所要分析的地图的特殊性,利用国内数字地图通用和专