面向大规模RDF数据的关键词查询方法研究
发布时间:2021-03-03 17:15
资源描述框架(Resource Description Framework,简称RDF)是语义Web中所使用的基本标记语言,在知识的组织与管理和社会网络应用中广泛应用。RDF数据的规模随着语义Web应用的发展而增大。RDF数据具有典型的图特征,含有复杂的结构信息,以及大量的文本信息。可见,如何在大规模RDF数据上进行高效的关键词查询是当前研究的热点之一。针对已有研究在查询执行效率和结果质量方面存在的不足,提出了基于近似组斯坦纳树的大规模RDF数据关键词查询方法RAGS。RAGS将RDF上的关键词查询映射为组斯坦纳树问题,然后通过将组斯坦纳树问题规约为最小斯坦纳树问题进行求解。针对经典的最小斯坦纳树算法是非规约安全的问题,提出了改进方法,并分析了算法的时间复杂度和近似比性能。为了使大规模RDF数据上的关键词查询具有更友好的用户体验,设计了最短路径三元组倒排索引结构,通过离线预先计算全源最短路径的方式,改善在线查询的实时性;提出基于升序排列生成树算法的top-k查询方法,以便更快的为用户返回准确结果。考虑到对于大规模RDF数据而言,索引构建时间也是系统的主要瓶颈。提出基于整体同步并行计算模...
【文章来源】:东北大学辽宁省 211工程院校 985工程院校 教育部直属院校
【文章页数】:64 页
【学位级别】:硕士
【文章目录】:
摘要
ABSTRACT
第1章 绪论
1.1 引言
1.2 研究现状
1.3 挑战与研究内容
1.4 论文结构与安排
第2章 相关工作
2.1 半结构化和结构化数据上的关键词查询
2.1.1 XML文档上的关键词搜索
2.1.2 关系数据库上的关键词查询
2.1.3 RDF数据上的关键词查询
2.2 组斯坦纳树和最小斯坦纳树问题
2.2.1 最小斯坦纳树问题
2.2.2 组斯坦纳树问题
2.3 分布式大规模图处理技术
2.3.1 基于MapReduce的大规模图处理
2.3.2 基于BSP的大规模图处理
2.4 本章小结
第3章 基于近似组斯坦纳树的RDF数据关键词查询方法
3.1 问题定义
3.2 方法概述
3.3 RDF图变换
3.4 近似组斯坦纳树
3.4.1 组斯坦纳树问题规约为最小斯坦纳树问题
3.4.2 基于DNH最小斯坦纳树启发算法的近似组斯坦纳树求解
3.5 本章小结
第4章 面向大规模RDF数据关键词查询的改进方法
4.1 最短路径三元组倒排索引
4.2 TOP-K查询
4.3 基于BSP的分布式算法
4.4 本章小结
第5章 实验设计与分析
5.1 实验设计
5.1.1 实验环境
5.1.2 测试数据集
5.1.3 实验评价标准
5.2 实验结果分析
5.2.1 索引时间开销和空间开销
5.2.2 查询响应时间比较
5.2.3 查询效果分析
5.2.4 k值对top-k查询响应时间的影响
5.2.5 基于BSP的分布式算法性能
5.3 本章小结
第6章 结论与展望
6.1 结论
6.2 未来展望
参考文献
致谢
攻读硕士学位期间参与的项目
【参考文献】:
期刊论文
[1]云计算环境下的大规模图数据处理技术[J]. 于戈,谷峪,鲍玉斌,王志刚. 计算机学报. 2011(10)
[2]KREAG:基于实体三元组关联图的RDF数据关键词查询方法[J]. 李慧颖,瞿裕忠. 计算机学报. 2011(05)
[3]XML数据的查询技术[J]. 孔令波,唐世渭,杨冬青,王腾蛟,高军. 软件学报. 2007(06)
[4]细粒度语义网检索[J]. 吴刚,唐杰,李涓子,王克宏. 清华大学学报(自然科学版). 2005(S1)
[5]并行计算模型在集群环境下的适应性[J]. 宋安军,彭勤科,胡保生. 计算机工程. 2003(18)
博士论文
[1]RDF图数据管理的关键技术研究[D]. 吴刚.清华大学 2008
本文编号:3061627
【文章来源】:东北大学辽宁省 211工程院校 985工程院校 教育部直属院校
【文章页数】:64 页
【学位级别】:硕士
【文章目录】:
摘要
ABSTRACT
第1章 绪论
1.1 引言
1.2 研究现状
1.3 挑战与研究内容
1.4 论文结构与安排
第2章 相关工作
2.1 半结构化和结构化数据上的关键词查询
2.1.1 XML文档上的关键词搜索
2.1.2 关系数据库上的关键词查询
2.1.3 RDF数据上的关键词查询
2.2 组斯坦纳树和最小斯坦纳树问题
2.2.1 最小斯坦纳树问题
2.2.2 组斯坦纳树问题
2.3 分布式大规模图处理技术
2.3.1 基于MapReduce的大规模图处理
2.3.2 基于BSP的大规模图处理
2.4 本章小结
第3章 基于近似组斯坦纳树的RDF数据关键词查询方法
3.1 问题定义
3.2 方法概述
3.3 RDF图变换
3.4 近似组斯坦纳树
3.4.1 组斯坦纳树问题规约为最小斯坦纳树问题
3.4.2 基于DNH最小斯坦纳树启发算法的近似组斯坦纳树求解
3.5 本章小结
第4章 面向大规模RDF数据关键词查询的改进方法
4.1 最短路径三元组倒排索引
4.2 TOP-K查询
4.3 基于BSP的分布式算法
4.4 本章小结
第5章 实验设计与分析
5.1 实验设计
5.1.1 实验环境
5.1.2 测试数据集
5.1.3 实验评价标准
5.2 实验结果分析
5.2.1 索引时间开销和空间开销
5.2.2 查询响应时间比较
5.2.3 查询效果分析
5.2.4 k值对top-k查询响应时间的影响
5.2.5 基于BSP的分布式算法性能
5.3 本章小结
第6章 结论与展望
6.1 结论
6.2 未来展望
参考文献
致谢
攻读硕士学位期间参与的项目
【参考文献】:
期刊论文
[1]云计算环境下的大规模图数据处理技术[J]. 于戈,谷峪,鲍玉斌,王志刚. 计算机学报. 2011(10)
[2]KREAG:基于实体三元组关联图的RDF数据关键词查询方法[J]. 李慧颖,瞿裕忠. 计算机学报. 2011(05)
[3]XML数据的查询技术[J]. 孔令波,唐世渭,杨冬青,王腾蛟,高军. 软件学报. 2007(06)
[4]细粒度语义网检索[J]. 吴刚,唐杰,李涓子,王克宏. 清华大学学报(自然科学版). 2005(S1)
[5]并行计算模型在集群环境下的适应性[J]. 宋安军,彭勤科,胡保生. 计算机工程. 2003(18)
博士论文
[1]RDF图数据管理的关键技术研究[D]. 吴刚.清华大学 2008
本文编号:3061627
本文链接:https://www.wllwen.com/guanlilunwen/ydhl/3061627.html