基于本体和邻居信息的知识图谱查询算法研究

摘要

目前，关于知识图谱的查询研究多是基于节点标签的子图匹配。由于节点标签是实体的名称或属性等自身信息，不能体现节点间的语义信息，这导致查询得到的结果语义相关度不高。同时，因为知识图谱多是大规模的数据集，导致存储成本过高。
　　针对上述问题，本文提出了一种基于本体和邻居信息的知识图谱查询算法OAN(Ontology And Neighborhood)。整个查询过程主要从减少图存储空间的压缩技术、提高查询效率的索引技术、提高结果语义相关性查询这三方面展开研究的。
　　首先，本文提出并设计了一种基于双向关系的图压缩技术。压缩的核心思想是通过判断节点间的本体类型是否相同对节点进行划分，同时判断多条边之间是否满足双向关系，若满足，则将这些边进行压缩。通过图压缩，可以将原始图转化成一个更小规模的概要图，节省内存空间。
　　其次，本文提出了一种基于图签名的索引算法。这个索引由两层签名组成，上层是节点的基本信息签名，下层是上层节点对应的邻居信息签名，目标图中所有节点的两层签名构成了整个图的签名索引。通过这个索引能提前移除一些不匹配节点，提高过滤阶段的查询效率。
　　之后，本文在这个索引的基础上提出了一个基于本体和邻居信息的查询算法。在过滤阶段，算法设计了一种同时考虑节点本体信息和图结构信息的相似度度量方法，由此可以提高结果集的语义相关性。在剪枝阶段，提出一种边信息检测方法来去除那些不满足匹配条件的查询节点候选集，并根据最终候选集对目标图剪枝，从而减少了目标图的规模，加快了验证阶段的查询速度。在验证排序阶段，验证候选集中子图是否满足边标签同构，并计算满足要求的结果的总语义相似度，给每个结果打分后进行排序，返回最终相似度高的前k个结果集。
　　最后，在Yago等三个开放数据集上做实验，并且和已有的相关算法进行对比。通过分析实验结果得出，本文所提出的方法无论是在图压缩和索引的优化性能，还是图查询算法的精确度和有效性方面都有所提高。

目录

声明

致谢

摘要

1 引言

1．1 研究背景及意义

1．2 研究现状

1．2．1 基于SI的算法研究

1．2．2 基于FTV的算法研究

1．2．3 知识图谱查询算法研究

1．3 论文研究内容

1．4 章节介绍

2 知识图谱查询技术

2．1 图查询相关理论

2．2 知识图谱查询技术

2．2．1 基于RDF的查询算法

2．2．2 基于标签的查询算法

2．2．3 基于本体的查询算法

2．3 查询优化技术

2．3．1 图压缩技术

2．3．2 基于特征的索引技术

2．3．3 基于非特征的索引技术

2．4 本章小结

3 基于双向关系的图压缩设计

3．1 相关研究及概念

3．2 GCBR压缩算法设计

3．2．1 图压缩算法设计

3．2．2 复杂度分析

3．3 GCBR压缩算法的实验和分析

3．3．1 实验环境

3．3．2 实验数据集

3．3．3 图压缩率分析

3．3．4 压缩时间

3．4 本章小结

4 基于签名的索引设计

4．1 GiS索引研究

4．2 IBS索引算法设计

4．2．1 算法设计概述

4．2．2 索引构建算法设计

4．2．3 复杂度分析

4．3 IBS算法的实验与分析

4．3．1 索引的构建时间

4．3．2 索引的规模大小

4．3．3 索引的可伸缩性分析

4．4 本章小结

5 基于本体和邻居的查询算法设计

5．1 OAN算法框架

5．2 算法各阶段描述

5．2．1 过滤阶段

5．2．2 剪枝阶段

5．2．3 同构排序阶段

5．3 算法复杂度分析

5．4 OAN查询算法的实验和分析

5．4．1 实验环境及数据集

5．4．2 精确度分析

5．4．3 灵活性分析

5．4．4 可扩展性分析

5．4．5 优化性能分析

5．5 本章小结

6．1 总结

6．2 展望

参考文献

作者简历及攻读硕士学位期间取得的研究成果

学位论文数据集