图数据搜索引擎Trinity中正则表达式匹配子系统的设计与实现

发布时间：2017-10-28 01:21

  本文关键词：图数据搜索引擎Trinity中正则表达式匹配子系统的设计与实现

  更多相关文章： 图数据 图模式匹配 正则表达式 分布式算法 查询优化

【摘要】：在许多大规模图数据的应用领域当中,找出图中路径上节点之间满足的某种限制是非常有必要的。利用正则表达式强大的描述序列模式的能力,本文中,定义图模式匹配的一种特殊形式:正则表达式在大规模图上的查询匹配。在这个查询中,用正则表达式表示节点之间所满足的限制。本文的研究将有利于查找图中满足某种限制的路径,只要这种路径可以用正则表达式表示。本课题是基于微软亚洲研究院分布式图引擎Trinity,Trinity是一个分布式大规模图处理引擎,从底层支持强类型的随机存储和通用计算,在大规模集群上,分布式的随机存储提供全局地址和高效的键值存储,通过随机存储,Trinity保证了在大规模分布式的数据集上对数据进行高效的随机访问。本论文研究内容包括对正则表达式的处理、图的生成器的研究、查询优化算法、分布式匹配算法的设计与实现。通过对yacc的分析,实现了对正则表达式的处理,处理后的形式能很好的适应分布式环境。处理后的形式更容易在图上进行匹配。通过对Power Low类型的图的研究实现了图生成器。依靠图生成器,实现了手工建造大规模图数据。通过对查询优化模型的构建实现了基于代价估计的查询优化方法,依靠此优化方法大幅提高了系统运行效率。通过对物理操作的实现,完成了大规模集群环境下的分布式算法,依靠这些分布式匹配算法,完成了图上的模式匹配。实验数据证明,本论文中的正则表达式匹配已经满足了实时查询的需要。
【关键词】：图数据 图模式匹配 正则表达式 分布式算法 查询优化
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第1章 绪论9-15
• 1.1 课题背景及研究的目的和意义9
• 1.2 国内外研究现状分析9-13
• 1.2.1 正则表达式对于数据抽象的研究9-10
• 1.2.2 图数据的研究现状10-13
• 1.3 本论文主要研究内容和结构13-15
• 1.3.1 本论文主要研究内容13-14
• 1.3.2 论文的结构14-15
• 第2章 正则表达式匹配系统需求分析与总体设计15-26
• 2.1 系统工作流程分析15-20
• 2.2 功能需求分析20-23
• 2.2.1 正则表达式处理需求分析20-21
• 2.2.2 数据生成需求分析21
• 2.2.3 数据提取需求分析21-22
• 2.2.4 索引构建需求分析22
• 2.2.5 正则表达式匹配需求分析22
• 2.2.6 查询优化需求分析22-23
• 2.2.7 结果提取需求分析23
• 2.3 非功能性需求分析23
• 2.4 系统总体设计23-25
• 2.5 本章小结25-26
• 第3章 正则表达式匹配系统详细设计26-51
• 3.1 正则表达式处理26-32
• 3.1.1 构建分析结构27-28
• 3.1.2 数据预处理28-29
• 3.1.3 数据转化29-31
• 3.1.4 分析提取31-32
• 3.2 数据生成32-38
• 3.2.1 改进的Rmat算法33-34
• 3.2.2 分布式数据生成34-38
• 3.3 数据提取38-40
• 3.3.1 数据预处理38-39
• 3.3.2 生成数据模型39-40
• 3.3.3 数据转化40
• 3.4 索引构建40-42
• 3.4.1 构建索引模型40-41
• 3.4.2 数据模型训练41-42
• 3.5 正则表达式匹配42-45
• 3.5.1 非闭包匹配算法42-44
• 3.5.2 闭包匹配算法44-45
• 3.5.3 算法复杂度分析45
• 3.6 查询优化45-48
• 3.6.1 代价估计模型构建46-47
• 3.6.2 动态规划算法47-48
• 3.6.3 查询运行时优化48
• 3.7 结果提取48-50
• 3.7.1 过滤器构建49
• 3.7.2 独立数据同步49-50
• 3.7.3 远程数据同步50
• 3.8 本章小结50-51
• 第4章正则表达式匹配系统的实现51-75
• 4.1 正则表达式处理51-54
• 4.1.1 构建分析结构51-52
• 4.1.2 数据预处理52
• 4.1.3 数据转化52-54
• 4.1.4 分析提取54
• 4.2 数据生成54-60
• 4.3 数据提取60-62
• 4.3.1 数据预处理60-61
• 4.3.2 生成数据模型61-62
• 4.3.3 数据转化62
• 4.4 索引构建62-65
• 4.4.1 构建索引模型63
• 4.4.2 数据模型训练63-65
• 4.5 正则表达式匹配65-68
• 4.5.1 非闭包算法65-68
• 4.5.2 闭包算法68
• 4.6 查询优化68-71
• 4.6.1 基于代价估计的查询优化69-71
• 4.6.2 系统运行时优化71
• 4.7 结果提取71-74
• 4.7.1 过滤器构建71-72
• 4.7.2 独立数据同步72-73
• 4.7.3 远程数据同步73-74
• 4.8 本章小结74-75
• 第5章 正则表达式匹配系统测试75-90
• 5.1 系统测试内容75
• 5.2 表达式处理模块测试内容75-76
• 5.3 数据生成模块测试内容76-82
• 5.4 表达式匹配模块测试内容82-87
• 5.5 查询优化模块测试内容87-88
• 5.6 与现有研究成果的对比88
• 5.7 本章小结88-90
• 结论90-92
• 参考文献92-98
• 致谢98-99
• 个人简历99

【相似文献】

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

1 孟岩;;一夫当关——《精通正则表达式》书评[J];程序员;2007年08期

2 路个的;;请个伙伴,助你成长为正则表达式高手[J];电脑爱好者;2008年23期

3 余晟;;正则表达式随笔[J];程序员;2008年03期

4 李国晶;王景强;;浅析正则表达式[J];科技资讯;2010年04期

5 马永萍;;正则表达式及其应用[J];电脑编程技巧与维护;2012年04期

6 侯秀红;董峰;;Visual Basic 6.0中正则表达式的应用[J];郑州轻工业学院学报;2005年04期

7 杨树林;;正则表达式在网络教学系统中的应用[J];北京印刷学院学报;2005年04期

8 黄晓春;孟岩;;理解正则表达式(下)[J];程序员;2007年06期

9 魏蓉;王文忠;仲兰芬;;正则表达式在现代汉语语法处理中的应用[J];阴山学刊(自然科学版);2007年04期

10 李丽莉;李娅;周琪云;;正则表达式在网络信息监控分析系统中的应用[J];信息技术;2008年04期

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

1 管杰裕;;正则表达式在气象信息处理中的应用[A];2005年广西气象学会学术年会论文集[C];2005年

2 刘琪;牛文静;;正则表达式在恶意代码动态分析中的应用[A];2009通信理论与技术新发展——第十四届全国青年通信学术会议论文集[C];2009年

3 王辉;丁明君;杨进;;正则表达式在企业信息管理开发中的应用[A];2010年MIS/S&A学术交流会议论文集（中国造船工程学会学术论文集）[C];2010年

4 田珂;赵国鸿;;利用TCAM与正则表达式对邮件协议进行二次识别的思想研究[A];第十六届计算机工程与工艺年会暨第二届微处理器技术论坛论文集[C];2012年

5 李佳;魏更宇;胡楠;王枞;杨义先;;基于特征自生成的畸形SIP信令检测算法[A];2010通信理论与技术新发展——第十五届全国青年通信学术会议论文集（下册）[C];2010年

6 周小甲;周庆利;;中文病历文本中时间信息自动标注[A];2011年浙江省医学会医学工程学分会第九届学术年会论文汇编[C];2011年

7 周小甲;周庆利;;中文病历文本中时间信息自动标注[A];浙江生物医学工程学会第九届年会论文汇编[C];2011年

中国重要报纸全文数据库 前1条

1 彭福祥 张钧;ASP.NET基本数值处理技巧[N];计算机世界;2006年

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

1 彭坤杨;基于TCAM的高速可扩展的正则表达式匹配技术[D];中国科学技术大学;2013年

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

1 李哲夫;正则表达式在电信业务处理中的应用研究[D];暨南大学;2008年

2 范慧萍;基于正则表达式的协议识别研究与实现[D];国防科学技术大学;2007年

3 段海生;基于正则表达式的深度包压缩算法研究[D];西安电子科技大学;2010年

4 姜英杰;支持正则表达式的文本匹配优化算法[D];东北大学;2012年

5 张洁坤;时空高效的正则表达式匹配算法研究[D];湖南大学;2010年

6 张娜;基于正则表达式的深度包检测研究[D];华东师范大学;2007年

7 刘鹏;面向存储的正则表达式匹配算法研究[D];解放军信息工程大学;2010年

8 刘俊超;基于正则表达式的应用层协议识别技术研究[D];国防科学技术大学;2008年

9 蒋俐峗;基于多步投机的正则表达式匹配算法的研究[D];湖南大学;2011年

10 金军航;面向深度包检测的存储高效的正则表达式匹配算法研究[D];湖南大学;2010年

，

本文编号：1106049